“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.

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

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:

More than 14 years’ experience as full stack developer and Software Architect .https://leanpub.com/u/dimitrispapadim

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store