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 argument
const leftZeroSemigroup = {
  concat: (x, y) => x
}
// always return the second argument
const rightZeroSemigroup = {
  concat: (x, y) => y
}
// always return the same value a ∈ A
const 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 equal
function 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 -> A
function 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.every
function every(as: Array<boolean>): boolean {
  return fold(everySemigroup, true, as)
}
// Array.prototype.some
function some(as: Array<boolean>): boolean {
  return fold(someSemigroup, false, as)
}
// Object.assign
function assign(as: Array<Object>): Object {
  return fold(mergeSemigroup, {}, as)
}