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 Map
s.
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@3e5400c7
Semigroup[String]
// res9: Semigroup[String] = cats.kernel.instances.StringMonoid@6b62d2b2
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@6fbe9670
Semigroup[Set[Int]]
// res11: Semigroup[Set[Int]] = cats.kernel.instances.SetSemilattice@132054c3
trait Foo
Semigroup[List[Foo]]
// res12: Semigroup[List[Foo]] = cats.kernel.instances.ListMonoid@6fbe9670
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@dec2c58
Example usage: Merging maps
Consider a function that merges two Map
s that combines values if they share
the same key. It is straightforward to write these for Map
s 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
.