PSST… Ordering is a Monoid

2020, Sep 9

What is a Monoid

if you have this 3 things T, concat and empty together, you have a monoid:

T - Set of values for example set of strings, or set of array etc,
concat — Function which takes 2 values from that set T, and returns new value which is in the same set T, such that this function is Associative.
empty — special value from the set T such that it is an identity element for that function concat.

We can express this in typescript like this:

type Monoid<T> = {
  concat: (a: T, b: T) => T;
  empty: T;
};

And we can have this laws/tests that must hold true for valid monoids:

const associativity = <T>(M: Monoid<T>, a:T, b:T, c: T) =>
  deepEqual(
    M.concat(a, M.concat(b, c)),
    M.concat(M.concat(a, b), c))
  )

const leftIdentity = <T>(M: Monoid<T>, a:T) =>
  deepEqual(
    M.concat(a, M.empty),
    a
  )

const rightIdentity = <T>(M: Monoid<T>, a:T) =>
  deepEqual(
    M.concat(empty, M.a),
    a
  )

Why should you care? why are discovering such structures useful?

The fact that you can refactor a _ (b _ c) into a _ b _ c and be sure that result will not change, or the reason you can write a + b + c and don’t care if you even use parentheses at all, is + and _ are associativity. The reason you would refactor a + 0 or a _ 1 to just a is because 0 is identity to the + operator as well as1 for *. Once you know something is a monoid you know that if you want to concat multiple values you can group in multiple batches execute them on multiple threads/workers and combine them. You can implement generic functions for such structures my favorite is fold

function fold<T>(M: Monoid<T>, array: T[]): T {
  return array.reduce(M.concat, M.empty);
}

fold(stringMonoid, ["a", "b", "c"]) === "abc";
fold(arrayMonoid, [["a"], ["b"], ["c"]]) === ["a", "b", "c"];
fold(numberAdditiveMonoid, [1, 2, 3]) === 6;
fold(numberMultiplicativeMonoid, [2, 3, 4]) === 24;

Here are Some Monoid Examples

one of the most obvious instance are for String and Array

String

const stringMonoid: Monoid<string> = {
  concat: (a: string, b: string): string => a.concat(b),
  empty: "",
};

// Associativity
a.concat(c.concat(d)) === a.concat(c).concat(d);

// Identity
"".concat(s) === s;
s.concat("") === s;

Array

const arrayMonoid: Monoid<Array<any>> = {
  concat: function<T>(a:Array<T>, b:Array<T>):Array<T> {
    return a.concat(b)
  },
  empty: [],
}

// Associativity
a.concat(c.concat(d)) === (a.concat(c)).concat(d)

// Identity
[].concat(s) === s
s.concat([]) === s

Note that for some type T there can exist more then one Monoid

Most well known of such types is Number

Number

const numberAdditiveMonoid: Monoid<number> = {
  concat: (a: number, b: number): number => a + b,
  empty: 0,
};

// Associativity
a + (b + c) === a + b + c;

// Identity
0 + s === s;
s + 0 === s;

and

const numberMultiplicativeMonoid: Monoid<number> = {
  concat: (a: number, b: number): number => a * b,
  empty: 1,
};

// Associativity
a * (b * c) === a * b * c;

// Identity
1 * s === s;
s * 1 === s;

Boolean

const booleanAndMonoid: Monoid<boolean> = {
  concat: (a: boolean, b: boolean): boolean => a && b,
  empty: true,
};

// Associativity
a && (b && c) === (a && b) && c;
// Identity
true && s === s;
s && true === s;

const booleanOrMonoid: Monoid<boolean> = {
  concat: (a: boolean, b: boolean): boolean => a || b,
  empty: false,
};

// Associativity
a || (b || c) === (a || b) || c;
// Identity
false || s === s;
s || false === s;

Ordering

Ordering is my favorite, it’s very nice and useful, when you want to sort array of some records based on many properties.

type Ordering = -1 | 0 | 1

const orderingMonoid: Monoid<Ordering> =  {
  concat: (a: Ordering, b: Ordering): Ordering {
    return a === 0 ? b : a
  },
  empty: 0
}

const users =
  [ { firstName:"Alisa", lastName:"Able" }
  , { firstName:"Bob",   lastName:"Able" }
  , { firstName:"Alisa", lastName:"Brown" }
  , { firstName:"Bob",   lastName:"Brown" }
  , { firstName:"Alisa", lastName:"Bold" }
  , { firstName:"Bob",   lastName:"Bold" }
  ]

users.sort(
  (a,b) => orderingMonoid.concat(
    a.firstName.localeCompare(b.firstName),
    a.lastName.localeCompare(b.lastName)
  )
)

// users now will be
[ { "firstName": "Alisa", "lastName": "Able" }
, { "firstName": "Alisa", "lastName": "Bold" }
, { "firstName": "Alisa", "lastName": "Brown" }
, { "firstName": "Bob", "lastName": "Able" }
, { "firstName": "Bob", "lastName": "Bold" }
, { "firstName": "Bob", "lastName": "Brown" }
]

users.sort(
  (a,b) => orderingMonoid.concat(
    a.lastName.localeCompare(b.lastName),
    a.firstName.localeCompare(b.firstName)
  )
)

// users now will be
[ { "lastName": "Able", "firstName": "Alisa"}
, { "lastName": "Able", "firstName": "Bob"}
, { "lastName": "Bold", "firstName": "Alisa"}
, { "lastName": "Bold", "firstName": "Bob"}
, { "lastName": "Brown", "firstName": "Alisa"}
, { "lastName": "Brown", "firstName": "Bob"}
]

// or you can do this
users.sort((a,b) => fold(
  orderingMonoid,
  [ a.lastName.localeCompare(b.lastName)
  , a.firstName.localeCompare(b.firstName)
  , a.points - b.points
  , a.someNumberField - b.someNumberField
  ]
))

if you look closely at the orderingMonoid.concat you would notice that it can be implemented as a || b. Which means you can write this code while fully understanding how ordering is a monoid and why this works:

users.sort(
  (a, b) =>
    a.lastName.localCompare(b.lastName) ||
    a.firstName.localCompare(b.firstName) ||
    a.points - b.points ||
    a.someNumberField - b.someNumberField
);

Also, there are monoids which depend on other monoids, for example Function and Record

Function

Function from Number to String is a monoid because String is a monoid:

type NumToStr = (n: number) => string
const numToStrMonoid: Monoid<NumToStr> = {
  concat: (a:NumToStr, b:NumToStr): NumToStr => n => {
    return stringMonoid.concat(a(n),b(n))
  },
  empty: () => stringMonoid.empty,
}

const a = x => (x*2).toString()
const b = x => (x*8).toString()
const c = x => (x*9).toString()

numToStrMonoid.append(a, numToStrMonoid.append(b,c))
// is equivalent to
numToStrMonoid.append(numToStrMonoid.append(a,b),c))
// is equivalent to
(x) =>  a(x).concat**(**c(x)  .concat(d(x))**)
**// is equivalent to
(x) => **(**a(x).concat(c(x))**)**.concat(d(x))

Record

Also, If all fields of a some Record/Object R are monoids, then there exists monoid instance for this R:

type Stats = { age: number; height: number; weight: number };

const numToStrMonoid: Monoid<Stats> = {
  concat: (a: Stats, b: Stats): Stats => ({
    age: numberAdditiveMonoid.concat(a.age, b.age),
    height: numberAdditiveMonoid.concat(a.height, b.height),
    weight: numberAdditiveMonoid.concat(a.weight, b.weight),
  }),
  empty: {
    age: numberAdditiveMonoid.empty,
    height: numberAdditiveMonoid.empty,
    weight: numberAdditiveMonoid.empty,
  },
};

Cheers 🎉