Explaining Monoids

Let’s have some fun with F#. Through example, we will discover together what are monoids, and why they could be useful. All the following code can be found online.

Function composition example with integers

We now all agree about what’s function composition. We all know what are integers. So, let’s compose some functions using the set of integers.

As shown in this code, add and minus for the set of integers are functions defining a rule of combining two elements for the set of integers. These functions have two interesting properties: they are associative, and they behave as an identity function when the neutral element is one of the input.

As you can guess, the neutral element in this case is 0. You can trust me, or you can just run this code instead:

Let’s wrap up: the set of integers has a rule (add) for combining two elements of the set, this rule is associative and has a neutral element (0).

 

Function composition example with hours 

We can also agree on what are hours (positive integers between 1 and 24), so we could compose some functions using the set of hours.

As it happens, we can also defined add and minus operation on hours. It’s a bit more interesting now, because these operations use a modulo, it’s no longer a simple operation. We can still prove associativity and the existence of a neutral element for the set hours on operation add.

We can add to our knowledge that the set of hours has a rule (add) for combining two elements of the set, this rule is associative and  has a neutral element (24).
 

Monoid land

Monoids are a collection of things (a set) with a rule of combining two elements of this set together (this rule is called the internal law of composition). This composition law has to be associative, and to contain a neutral element (otherwise it is not a monoid, but it could be another mathematical structure like a magma or a semigroup that we won’t detail here, because they have less interest for a programmer).

Does it remember you something? You got it:

  • The integers set with the function add is a monoid, because add is a rule to combine two int together, add is associative, and add is an identity function when it is used with the neutral element of the set which is zero.
  • The hours set with the function add is a monoid, because add is a rule to combine two hours together, add is associative, and add is an identity function when it is used with the neutral element of the set which is 24.

We use simple examples here, but please understand that any law (function) defining the combination of two element of a set, that is associative and behave as an identity function when used with a neutral element, is a valid rule to define a monoid. No matter the name or the complexity of this function. Note also that we call monoid the set with the function. Integers are not monoids. But integers with the function add is a monoid. Hours with the function add is another monoid. You can’t define a monoid without its internal law of composition.

Parallel Monoid

The coolest thing about monoid is the associativity law. And the cool thing with associativity in programming is that it allows parallel streams. Why?
Because if (f°g)°h =f°(g°h), you don’t care which function is executed in which order. How convenient is that for parallel processing?
 

Monoids everywhere

Cyrille Martraire has a great talk to explain why you should look for monoids in your domain. By their very nature, you can assume they have a neutral element, they are composable and parallelizable (because they are associative), and they are based on a set of value objects. You say all that when you say that something is a monoid in your domain.

Monoids are powerful and deserve to be known, as you probably use them already without noticing their existence!

 

Ouarzy

 

2 thoughts on “Explaining Monoids

  1. “Monoids are a collection of things (a set) with a rule of combining two elements of this set together […]. This composition law has to be associative, and the set has to contain a neutral element”
    Notice that the neutral element in the set can change depending on the actual composition law ( neutral element for integer addition is not the same as neutral element for integer multiplication)

Leave a Reply

Your email address will not be published. Required fields are marked *

IP Blocking Protection is enabled by IP Address Blocker from LionScripts.com.