Monoids in TypeScript
“Alternatively, the fundamental notion of category theory is that of a Monoid”
— Categories for the Working Mathematician
Monoids are one of those profound ideas that are easy to understand and are everywhere. Monoids belong to the category of Algebras. There are a couple of very important ways to organize different structures that appear in functional programming. Algebras is one of them. Fantasy land has some of the most important algebras in its specification.
Wikipedia says a monoid is an algebraic structure with a single associative binary operation and an identity element. Any structure that has those two elements is a monoid.
Suppose that S is a structure and ⊗ is some binary operation S ⊗ S → S, then S with ⊗ is a monoid if it satisfies the following two axioms:
1. Associativity: For all a, b and c in S, the equation (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c) holds.
2. Identity element: There exists an element e in S such that for every element a in S, the equations e ⊗ a = a ⊗ e = a hold.
Let us take the integers we can take addition as a binary operation between two integers. The addition is associative. This means there is no importance on the order of the addition.
(x+(y+z)) = ((x+y) +z)
And 0 is the identity element for addition since :
x + 0 = x
For those reasons, the pair (+,0) forms a monoid over the integers. However, we can form different other monoids over the integers. For example, multiplication * also can be viewed as a monoid with its respective identity element the 1. In this way the pair (*,1) is another monoid over the integers. Strings in TS have a default monoid, which is formed by the concatenation and the empty string (‘’, concat). String type in TS has natively a concat method that refers to this specific monoid we all know. However, for integers, for example, it would not make any sense to pick a specific monoid as default.
TypeScript Formulation
We will use monoids in our code by defining simple object literals that have two functions, one that returns the identity element called empty and one that represents the binary operation called concat .
We can define for example:
const Sum: monoid<number> = ({
empty: 0,
concat: (u: number, v: number) => u + v
})which we will use it like this:
var total:number = Sum.concat(Sum.empty, Sum.concat(3, 4));
This definition would allow us to use it with the reduce function of a list in a direct manner
total = [ 1, 3, 4, 5 ].reduce( sum.concat ,sum.empty);
Alternative Definition
Alternatively, if we want to have closure [meaning that the return type of the concat and empty is of the same type with the initial object], we could define one new class for each monoid.
Run This: Fiddle
This formulation is nice in the sense that allows for fluent chaining var total = new SumAcc (0).concat(new SumAcc (1)) .concat(new SumAcc (2)) because of the fact that empty and concat both return a result of the same type. This also is more congruent with the mathematical definition that says that if S is a structure (in a programming language, this translates to a Type), then S × S → S, means that the operation returns a structure of the same kind.
Folding monoids
Monoids have this very desirable property that if we keep applying this binary operation, we can always reduce the computation to a single element of the same type:
(M⊗…(M (⊗(M ⊗ M))) → M
this is called folding. We already know folding as reduce from the TS Array type. However, we are going to generalize fold in a latter chapter for data structures that we will call traversables. Coming back to fold, let us try to derive reduce.
Let’s say we have some sequence of integers 2,4,5,6 and we want to add them this a beginner level problem:
var list = [ 1, 2, 3, 4 ];
var total = 0; foreach (var item in list)
total = total + item;
I highlighted there the elements of a monoid. So, let’s abstract away. If we replace the (0,+) with any other monoid this should work, so why not abstract and reuse.
Run This: Fiddle
Now we can use this function with all kind of monoids
Run This: Fiddle
Next:
