# 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)]

}

}

### Partially 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' ? y : x

}

### 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)

}