Explaining Monoids to the 10 years old me

Sometime ago I started to code using the functional paradigm in Node.js and Elixir .

When you try to make the switch from a non-pure functional language to a pure one (such as Haskell ), you can find some scaring concepts like Functors (we talked about thempreviously) and Monoids .

What if I tell you that you’re already using them?

What if I tell you that you’ve always used them without knowing it?

Let’s see what the heck is a Monoid.

Monoid Axioms

Let’s do a bit of maths using the + operation:

5 + 5 = 10
(10 + 5) + 15 = (5 + 15) + 10
10 + 0 = 0 + 10

We can immediately notice three things:

1. The result will always be the same, doesn’t matter the order in which we’re doing the sum operation. We can try to sum (10 + 5) + 15 and (5 + 15) + 10 , but we’ll always get the same result.
2. There is a case where adding a number, the result won’t change at all. 10 + 0 returns just 10 .
3. Let’s look at the first equation: there is a kind of binary operation that takes two things of type int and returns an element of the same type ( int ).

Pretty easy, isn’t it? Now let’s call these things with their proper names:

Associative Property

The associative property states that you can add or multiply regardless of how the numbers are grouped. By 'grouped' we mean 'how you use parenthesis'. In other words, if you are adding or multiplying it does not matter where you put the parenthesis. Add some parenthesis any where you like! ( read more here )

Identity Element

The identity property for addition tells us that zero added to any number is the number itself. Zero is called the "additive identity." The identity property for multiplication tells us that the number 1 multiplied times any number gives the number itself. The number 1 is called the "multiplicative identity.” ( source )

Binary Operation

The word "binary" means composed of two pieces. A binary operation is simply a rule for combining two values to create a new value. The most widely known binary operations are those learned in elementary school: addition, subtraction, multiplication and division on various sets of numbers. ( read more here )

So guess what is a Monoid ?

A Monoid is a set that is closed under an associative binary operation and has an identity element.

Once again, let’s summarize the three rules that compose a Monoid:

1. A binary operation that combines two things and returns a third thing of the same type.
2. That binary operation must be associative.
3. There must be some kind of identity element for the binary operation.

For instance, we can clearly see that the division operation does not respect those rules:

(10 / 5) / 2 = 1
10 / (5 / 2) = 0.25

but the multiplication does:

10 * 10 = 100
10 * (5 * 2) = (10 * 5) * 2
10 * 1 = 10

Why should I care about Monoids?

Now let’s make a little example using theES6 reduce method in TypeScript .

const myList: number[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const mySum:  number   = myList.reduce((x, y) => x + y, 0);

What’s happening here? In that case, the reduce method combines the Nth element of the list with an accumulator until there’s only one element left.

For instance, it starts with 1 + 2 , then with 3 + 3 (where the first 3 is the result of the previous operation, 1 + 2 ) and so on:

(1 + 2) + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
(3 + 3) + 4 + 5 + 6 + 7 + 8 + 9 + 10
(6 + 4) + 5 + 6 + 7 + 8 + 9 + 10
(10 + 5) + 6 + 7 + 8 + 9 + 10
(15 + 6) + 7 + 8 + 9 + 10
(21 + 7) + 8 + 9 + 10
(28 + 8) + 9 + 10
(36 + 9) + 10
(45 + 10)
55

now let’s assume that we have a list with millions of numbers. How long would it take to compute that task?

Now, let’s think about the associative property. It doesn’t matter the execution order for our operations, right? So that operation can be done in parallel on multiple threads, cores, nodes!

Let’s say that reducing an array of 100 elements on a single core takes 10 seconds (a lot of time, I know, but it’s just for keeping things simple); splitting that operation on five cores may reduce the execution time up to five times!

And what about the identity property ? Our reduce function expects to combine two things… but what if I pass an empty list? Or what if that list has only on element?

You can notice how the reduce method solves that problem by letting us to add the initial value as parameter:

const mySum: number = myArray.reduce(sumElements, 0);
//                                  initial value ^

as you can see, we’re passing the addition identity which is 0 . If we’re parallelizing the code above on multiple cores/threads/nodes, it doesn’t matter if we’re passing 0 as initial value in our reduce function.

Other Monoids

As I said at the beginning of the article, we’re already using Monoids without even knowing:

Boolean

Boolean AND and OR are Monoids. Their identity is TRUE for AND and FALSE for OR :

(true && false) && true = (false && true) && true
(true || false) && true = (false || true) && true

String

String concatenation is also a Monoid. Its identity element is the empty string "" :

("Hello" + " ") + "World!" = "Hello" + (" " + "World!")

List/Arrays

Just like strings, list/arrays are Monoids and their identity element is the empty list/array [] :

[1, 2, 3, 4] + ([5, 6] + [7, 8, 9, 10]) = ([1, 2, 3, 4] + [5, 6]) + [7, 8, 9, 10]

there are also other Monoids and I bet that you’re already using them… try to guess others of them!

Benefits of Monoids

Ok I have to be honest, we’ve just seen some abstract mathematical concepts, but what are the advantages of using Monoids when programming?

First of all, thanks to the associativity property we can parallelize our algorithms, reason on them with a “divide and conquer” mindset and we also get support for incremental for free.

Identity elementensure a correct computation given a starting/default value for our functions, so no error will be spawned because of missing values during our operations.

Understanding Monoids (alongside Functors) is also fundamental for another hot topic in mathematics and computer science: Monads . But we’ll talk about them in future!