# Semigroups

Adapted from Algebraic Structure and Protocols by @mbrandonw

Mathematicians love to study objects abstractly. When the object is a set of elements that is equipped with some operation(s) (and some laws!) we call it an algebra. In this post we’ll see how algebras can be encoded as interfaces and then some important algebras are presented.

Let’s start with the simplest algebra we can think of: magmas. A magma is a pair (M, *) in which M is a non-empty set and * is a binary operation on M, i.e. a function that takes two elements of M as input and returns an element of M as output

`*: (M, M) -> M;`

A semigroup (S, *) is a magma in which * is associative, i.e. the equation

(x * y) * z = x * (y * z)

holds for all x, y, z ∈ S.

Associativity simply tells us that we do not have to worry about parenthesizing an expression and can write x * y * z.

Semigroups capture the essence of parallelizable operations

There are plenty of examples of semigroups

• (number, *) where * is the usual multiplication of numbers
• (string, +) where + is the usual concatenation of strings
• (boolean, &&) where && is the usual conjunction

and many more.

### Implementation

How do we translate these ideas into JavaScript? We can implement the concept of a semigroup on a type A as an interface (using Flow or TypeScript), where the operation * is named concat (see static-land specification)

`interface Semigroup<A> {  concat(x: A, y: A): A;}`

The following law must hold

• Associativity concat(concat(x, y), z) = concat(x, concat(y, z))

This is how we can implement the semigroup instance (number, *)

`const multiplicationSemigroup: Semigroup<number> = {  concat: (x, y) => x * y}`

Note that you can define different semigroup instances for the same type. Here’s the implementation of the semigroup instance (number, +) where + is the usual addition of numbers

`const additionSemigroup: Semigroup<number> = {  concat: (x, y) => x + y}`

Another example, with strings this time

`const stringSemigroup: Semigroup<string> = {  concat: (x, y) => x + y}`

### I can’t find an instance!

What if, given a type A, you can’t find an associative operation on A? You can create a (trivial) semigroup instance for every type just using the following constructions

`// always return the first argumentconst leftZeroSemigroup = {  concat: (x, y) => x}`
`// always return the second argumentconst rightZeroSemigroup = {  concat: (x, y) => y}`
`// always return the same value a ∈ Aconst fixedSemigroup = {  concat: (x, y) => a}`

Another technique is to define a semigroup instance for Array<A> (called the free semigroup of A)

`function getFreeSemigroup<A>(): Semigroup<Array<A>> {  return {    // here concat is the native array method    concat: (x, y) => x.concat(y)  }}`

and map the elements of A to the singleton elements of Array<A>

`function of<A>(a: A): Array<A> {  return [a]}`

The free semigroup of A is the semigroup whose elements are all possible finite sequences of elements of A.

### Semigroups for type constructors

In order to build a sensible semigroup instance for a type constructor, for example Maybe<A> or Promise<A>, we first need a semigroup instance for A

`type Maybe<A> = null | A;`
`function getMaybeSemigroup<A>(  semigroup: Semigroup<A>):   Semigroup<Maybe<A>> {`
`  return {    concat: (x, y) => {      if (x === null) {        return y      }      if (y === null) {        return x      }      // here we need a semigroup instance for A      return semigroup.concat(x, y)    }  }}`
`function getPromiseSemigroup<A>(  semigroup: Semigroup<A>): Semigroup<Promise<A>> {`
`return {    concat: (x, y) => Promise.all([x, y])      // again, here we need a semigroup instance for A      .then(([ax, ay]) => semigroup.concat(ax, ay))  }}`

### The product semigroup

Given two semigroup instances, one for A and one for B we can build the semigroup instance of their product, i.e. the tuple [A, B]

`function getProductSemigroup<A, B>(  a: Semigroup<A>, b: Semigroup<B>): Semigroup<[A, B]> {`
`  return {    concat: ([ax, bx], [ay, by]) =>       [a.concat(ax, ay), b.concat(bx, by)]  }}`

### Ordered sets

If A is sortable, then you can define a semigroup on A using min (or max) as operation

`const minSemigroup: Semigroup<number> = {  concat: (x, y) => Math.min(x, y)}`
`const maxSemigroup: Semigroup<number> = {  concat: (x, y) => Math.max(x, y)}`

We can try to capture the notion of “sortable”, but before that we need to capture the notion of “being equal”. Mathematicians talk about equivalence relations. Let’s introduce another interface for that: Setoid

`interface Setoid<A> {  equals(x: A, y: A): boolean}`

The following laws must hold

• Reflexivity equals(x, x) = true for all x ∈ A
• Symmetry equal(x, y) = true if and only if equals(y, x) = true for all x, y ∈ A
• Transitivity if equal(x, y) = true and equal(y, z) = true then equal(x, z) = true

We can now capture the notion of “sortable”. Mathematicians talk about order relations. Let’s introduce the interface Ord

`type Ordering = 'LT' | 'EQ' | 'GT';`
`interface Ord<A> extends Setoid<A> {  compare(x: A, y: A): Ordering}`
`// less than or equalfunction leq<A>(ord: Ord<A>, x: A, y: A): boolean {  return ord.compare(x, y) !== 'GT'}`

We write x <= y if and only if leq(ord, x, y) = true.

The following laws must hold

• Reflexivity x <= x for all x ∈ A
• Antisymmetry if x <= y and y <= x then x = y
• Transitivity if x <= y and y <= z then x <= z

In order to be compatible with Setoid, the following additional property must hold

• compare(x, y) = ‘EQ’ if and only if equals(x, y) = true

We can now define min and max in a generic way

`function min<A>(ord: Ord<A>, x: A, y: A): A {  return ord.compare(x, y) === 'LT' ? x : y}`
`function max<A>(ord: Ord<A>, x: A, y: A): A {  return ord.compare(x, y) === 'GT' ? x : y}`

### Appendix

Other examples and implementations of semigroups in JavaScript

`const everySemigroup: Semigroup<boolean> = {  concat: (x, y) => x && y}`
`const someSemigroup: Semigroup<boolean> = {  concat: (x, y) => x || y}`
`const mergeSemigroup: Semigroup<Object> = {  concat: (x, y) => Object.assign({}, x, y)}`
`// an endomorphism of a set A is a function f: A -> Afunction getEndomorphismSemigroup<A>(): Semigroup<(a: A) => A> {  return {    concat: (x, y) => ( a => x(y(a)) )  }}`

If we define a generic fold function

`function fold<A>(semigroup: Semigroup<A>, a: A, as: Array<A>): A {  return as.reduce(semigroup.concat, a)}`

we can re-implement some well known functions using the semigroups defined above

`// Array.prototype.everyfunction every(as: Array<boolean>): boolean {  return fold(everySemigroup, true, as)}`
`// Array.prototype.somefunction some(as: Array<boolean>): boolean {  return fold(someSemigroup, false, as)}`
`// Object.assignfunction assign(as: Array<Object>): Object {  return fold(mergeSemigroup, {}, as)}`