# 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)
// 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.implicits._

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

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.implicits._
``````
``````Semigroup[Int]
// res8: Semigroup[Int] = cats.kernel.instances.IntGroup@7c1f793b
Semigroup[String]
// res9: Semigroup[String] = cats.kernel.instances.StringMonoid@43e8325b
``````

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@3c4a1404
Semigroup[Set[Int]]
// res11: Semigroup[Set[Int]] = cats.kernel.instances.SetSemilattice@32d5ffa9

trait Foo
Semigroup[List[Foo]]
// res12: Semigroup[List[Foo]] = cats.kernel.instances.ListMonoid@5c06b0af
``````

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.instances.TupleInstances2\$\$anon\$182@8e48dfc
``````

# 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.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: 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 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`.