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] = new Semigroup[Int] {
  def combine(x: Int, y: Int): Int = x + y
}

val x = 1
val y = 2
val z = 3
Semigroup[Int].combine(x, y)
// res0: Int = 3

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

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

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

import cats.implicits._
// import cats.implicits._

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

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

import cats.implicits._

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

map1 |+| map2
// res5: scala.collection.immutable.Map[String,Int] = Map(hello -> 2, 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.implicits._
Semigroup[Int]
// res0: cats.kernel.Semigroup[Int] = cats.kernel.instances.IntGroup@121140a4

Semigroup[String]
// res1: cats.kernel.Semigroup[String] = cats.kernel.instances.StringMonoid@528eef2a

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

Semigroup[List[Byte]]
// res2: cats.kernel.Semigroup[List[Byte]] = cats.kernel.instances.ListMonoid@7cc6bbfc

Semigroup[Set[Int]]
// res3: cats.kernel.Semigroup[Set[Int]] = cats.kernel.instances.SetSemilattice@12293e2f

trait Foo
// defined trait Foo

Semigroup[List[Foo]]
// res4: cats.kernel.Semigroup[List[Foo]] = cats.kernel.instances.ListMonoid@7b05aea8

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

Semigroup[(List[Foo], Int)]
// res5: cats.kernel.Semigroup[(List[Foo], Int)] = cats.kernel.instances.TupleInstances2$$anon$182@695f0a2e

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.implicits._

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: scala.collection.immutable.Map[Char,Int] = Map(a -> 1, b -> 2)

val xm2 = Map('b' -> 3, 'c' -> 4)
// xm2: scala.collection.immutable.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: scala.collection.immutable.Map[Int,List[String]] = Map(1 -> List(hello))

val ym2 = Map(2 -> List("cats"), 1 -> List("world"))
// ym2: scala.collection.immutable.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
// res6: Boolean = true

Semigroup[Map[Int, List[String]]].combine(ym1, ym2) == y
// res7: 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 power 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.