Semigroup

API Documentation: Semigroup

If a type A can form a Semigroup it has an associative binary operation.

trait Semigroup[A] {
  def combine(x: A, y: A): A
}

Associativity means the following equality must hold for any choice of x, y, and z.

combine(x, combine(y, z)) = combine(combine(x, y), z)

A common example of a semigroup is the type Int with the operation +.

import cats.Semigroup

implicit val intAdditionSemigroup: Semigroup[Int] = _ + _

val x = 1
val y = 2
val z = 3

Semigroup[Int].combine(x, y)
// res1: Int = 3

Semigroup[Int].combine(x, Semigroup[Int].combine(y, z))
// res2: Int = 6

Semigroup[Int].combine(Semigroup[Int].combine(x, y), z)
// res3: Int = 6

Infix syntax is also available for types that have a Semigroup instance.

import cats.syntax.all._

1 |+| 2
// res4: Int = 3

A more compelling example which we'll see later in this tutorial is the Semigroup for Maps.

import cats.syntax.all._

val map1 = Map("hello" -> 1, "world" -> 1)
val map2 = Map("hello" -> 2, "cats"  -> 3)

Semigroup[Map[String, Int]].combine(map1, map2)
// res5: Map[String, Int] = Map("hello" -> 3, "cats" -> 3, "world" -> 1)

map1 |+| map2
// res6: Map[String, Int] = Map("hello" -> 3, "cats" -> 3, "world" -> 1)

Example instances

Cats provides many Semigroup instances out of the box such as Int (+) and String (++)...

import cats.Semigroup
import cats.syntax.all._

Semigroup[Int]
// res8: Semigroup[Int] = cats.kernel.instances.IntGroup@68cad8c3
Semigroup[String]
// res9: Semigroup[String] = cats.kernel.instances.StringMonoid@290266b0

Instances for type constructors regardless of their type parameter such as List (++) and Set (union)...

Semigroup[List[Byte]]
// res10: Semigroup[List[Byte]] = cats.kernel.instances.ListMonoid@3976d8f0
Semigroup[Set[Int]]
// res11: Semigroup[Set[Int]] = cats.kernel.instances.SetSemilattice@36397054

trait Foo
Semigroup[List[Foo]]
// res12: Semigroup[List[Foo]] = cats.kernel.instances.ListMonoid@3976d8f0

And instances for type constructors that depend on (one of) their type parameters having instances such as tuples (pointwise combine).

Semigroup[(List[Foo], Int)]
// res13: Semigroup[(List[Foo], Int)] = cats.kernel.Monoid$$anon$2@80bba90

Example usage: Merging maps

Consider a function that merges two Maps that combines values if they share the same key. It is straightforward to write these for Maps with values of type say, Int or List[String], but we can write it once and for all for any type with a Semigroup instance.

import cats.syntax.all._

def optionCombine[A: Semigroup](a: A, opt: Option[A]): A =
  opt.map(a |+| _).getOrElse(a)

def mergeMap[K, V: Semigroup](lhs: Map[K, V], rhs: Map[K, V]): Map[K, V] =
  lhs.foldLeft(rhs) {
    case (acc, (k, v)) => acc.updated(k, optionCombine(v, acc.get(k)))
  }

val xm1 = Map('a' -> 1, 'b' -> 2)
// xm1: Map[Char, Int] = Map('a' -> 1, 'b' -> 2)
val xm2 = Map('b' -> 3, 'c' -> 4)
// xm2: Map[Char, Int] = Map('b' -> 3, 'c' -> 4)

val x = mergeMap(xm1, xm2)
// x: Map[Char, Int] = Map('b' -> 5, 'c' -> 4, 'a' -> 1)

val ym1 = Map(1 -> List("hello"))
// ym1: Map[Int, List[String]] = Map(1 -> List("hello"))
val ym2 = Map(2 -> List("cats"), 1 -> List("world"))
// ym2: Map[Int, List[String]] = Map(2 -> List("cats"), 1 -> List("world"))

val y = mergeMap(ym1, ym2)
// y: Map[Int, List[String]] = Map(
//   2 -> List("cats"),
//   1 -> List("hello", "world")
// )

It is interesting to note that the type of mergeMap satisfies the type of Semigroup specialized to Map[K, *] and is associative - indeed the Semigroup instance for Map uses the same function for its combine.

Semigroup[Map[Char, Int]].combine(xm1, xm2) == x
// res14: Boolean = true

Semigroup[Map[Int, List[String]]].combine(ym1, ym2) == y
// res15: Boolean = true

Exploiting laws: associativity

Since we know Semigroup#combine must be associative, we can exploit this when writing code against Semigroup. For instance, to sum a List[Int] we can choose to either foldLeft or foldRight since all that changes is associativity.

val leftwards = List(1, 2, 3).foldLeft(0)(_ |+| _)
// leftwards: Int = 6

val rightwards = List(1, 2, 3).foldRight(0)(_ |+| _)
// rightwards: Int = 6

Associativity also allows us to split a list apart and sum the parts in parallel, gathering the results in the end.

val list = List(1, 2, 3, 4, 5)
val (left, right) = list.splitAt(2)

val sumLeft = left.foldLeft(0)(_ |+| _)
// sumLeft: Int = 3
val sumRight = right.foldLeft(0)(_ |+| _)
// sumRight: Int = 12
val result = sumLeft |+| sumRight
// result: Int = 15

However, given just Semigroup we cannot write the above expressions generically. For instance, we quickly run into issues if we try to write a generic combineAll function.

def combineAll[A: Semigroup](as: List[A]): A =
  as.foldLeft(/* ?? what goes here ?? */)(_ |+| _)

Semigroup isn't powerful enough for us to implement this function - namely, it doesn't give us an identity or fallback value if the list is empty. We need a more powerfully expressive abstraction, which we can find in the Monoid type class.

N.B. Cats defines the Semigroup type class in cats-kernel. The cats package object defines type aliases to the Semigroup from cats-kernel, so that you can simply import cats.Semigroup.