Monoids, Functors, and Monads Oh My!

This will be the first post in a multi-part series I’m thinking. ‘Functional Design Patterns’, where I’ll cover monoids, functors and monads.

I get that I’ve just started out on the whole blogging thing but hey, what the hell…might as well jump into the deep end and get swimming.

Now, I am no guru and I certainly don’t just roll out of bed in the morning knowing this shit. I had to do some research for these topics, which is part of the reason I started blogging. These posts are heavily inspired by the excellent book Functional Programming in Scala by Paul Chiusano and Runar Bjarnason. Pick it up if you really want to get serious about FP in Scala …and do the excercises! …but I digress…

We will be attacking monoids from the perspective of computer science as much as possible. The definition and application of monoids in mathematics is a lot more strict, or at least it seems that way to me. Along the way there may be some math interspersed here and there, but I’ll try to keep it minimized where it’s not directly relevant to CS. Of course, monoids are fundamentally mathematical structures/concepts, so we’ll have to think about math a little.

Commutativity and Associativity

Before we dive in, these terms will need to be understood before we go any further. Commutativity a little less so, but it doesn’t hurt to know what it is if you don’t already.

In mathematical operations such as addition, subtraction, multiplication, and division, each operation can be assigned, or better yet, comes out of the box with certain properties. For the purposes of monoids, we are concerned with commutativity and associativity.

Commutativity, or the commutative law, simply means that when you apply an operation to two numbers, can you swap those numbers and get the same answer?

2 + 3 = 3 + 2    Commutative
2 / 3 != 3 / 2   Not commutative
2 * 3 = 3 * 2    Commutative
2 - 3 != 3 - 2   Not commutative

You get the picture.

Associativity, or the associative law, means that no matter how you group the numbers, you will also get the same answer.

(2 + 3) + 4 = 2 + (3 + 4)    Associative
(2 * 3) * 4 = 2 * (3 * 4)    Associative

So as you can see above, the + and * operations on numbers are both associative and commutative. The / and — operations are not.

So what does this have to do with monoids?

In more computer sciency terms, a monoid is nothing more than a type T which contains an associative binary operator and an identity element. What this means is if you have an a, b, c of type T, then:

(a op b) op c) == a op (b op c)

Let’s go back to our number example from the above associativity definition.

For our purposes, let’s say we have a Number (Type T). Let us take an a, b, c of that type Number, 2, 3, 4. Then:

(2 + 3) + 4 == 2 + (3 + 4) == 9

One more law that a monoid must obey to be a monoid is that it must have an identity element, which is nothing more than an element such that when our binary operator is applied to it, you will always get the other element back.

(a op 0) == a and (0 op a) == a

So taking our Number example from above,

(2 + 0) == 2 and (0 + 2) == 2
(And don't fall into the trap of assuming it's always 0:
(2 * 1) == 2 and (1 * 2) == 2 for the associative * operator

In computer science, monoids can be any type T and do not have to be related in any way as we’ll see. They only need to offer up an associative binary operation and have an identity element.

Monoids are actually kind of everywhere, and you use them all the time but don’t even realize it.

Let’s look at another popular example of monoids in software, string concatenation.

(“abc” concat “def”) concat “ghi” breaks down into “abcdef” concat “ghi” which is “abcdefghi”. This is equivalent to

"abc" concat ("def" concat "ghi")
"abc" concat "defghi"
"abc" concat "defghi"
"abcdefghi"

Strings also have an identity element, can you guess what it is?

"abc" concat "" == "abc" and "" concat "abc" == "abc"

…that’s right, the empty string. The same concepts go for lists. There are countless other examples and I’m sure you can come up with a few!

In the next part, I’ll go over some applications of monoids in actual programming constructs and patterns.

Till next time brothers and sisters, thanks for reading \,,/

Originally published at tcasper.com.