Monoids, functors, monads

Hello everybody!

This is going to be my attempt to explain these cryptic concepts. I’m going to take examples of things we know well to illustrate the concepts.

So, let’s start with the monoid. A good example of a monoid is addition. Let’s say we wanted to add a list of numbers:

2+3+4+5+6+7+...

We could start at the front and just perform the operation, adding 2 to 3 then the result of this to 4 etc. etc. Let’s say, however, that we have a lot of computers and the list of numbers is very long and we want to get this done quickly. Addition is parallelisable. We could distribute chunks of the list as we wished to each computer and have it add its part of the list. We’d give it its chunk and the following instructions:

1. Start with 0
2. Combine two adjacent elements by adding them
3. Carry on adding adjacent elements until you only have 1 element left.

And that’s all the computer would need to know.

Congratulations! That’s a monoid. A starting value and an instruction of how to combine adjacent elements that can be parallelised.

Note that according to this definition, division is not a monoid, because the order of the operations is important. Consider the following list:

1/2/3/4/5/6/7/...

Its result depends on starting at the left and working your way through. In other words (1/2)/3 is not the same as 1/(2/3).

Note also that combining words into sentences (or letters into words) is a monoid according to this definition, because we only provide a rule for adding adjacent elements. In other words (“liberté” + “égalité”) + “fraternité” is the same as “liberté” + (“égalité” + “fraternité”). It is however not the same as (“liberté + “fraternité”) + “égalité”. Let’s call this operation collect.

Ok, let’s move on to functors. A functor transforms each element of the list. Think of multiplying each element in a list of numbers by 3 or taking its sinus, for example. In a number of programming language this is referred to as map. So that the functor is parallelisable it can only depend upon the element of the list it is currently working on and not on any other elements. Another example would be counting the occurances of each letter in a list of words:

countOccurances(["foo", "bar", "banana"]) => [{'f'=>1, 'o'=>2,}, {'b'=>1, 'a'=>1, 'r'=>1}, {'b'=>1, 'a'=>3, 'n'=>2}]

You could think of this as being a stage in an assembly line. The objects arrive on a conveyor belt and are then all painted or polished or whatever individually by some big machine. You could parallelise this by just installing more machines next to each other. To be a functor however, the order of the stream of objects before the machine has to be the same as the order afterwards.

So that just leaves the monad. A monad will turn each element of the list into a list and then string all the lists together. An example would be a function that repeats each number in a list twice:

[1,2,3,4,5] => [1,1,2,2,3,3,4,4,5,5]

For lists, this function is called flatmap. It may not be immediately obvious why this is useful. I must admit, I spent a while trying to find an example of where this is used in everyday life and the best I could think of was breaking up large items into small items for easy transport. Maybe taking the freight of a container ship and putting it in lorries which all have to arrive at the same destination in the same order?

So that’s pretty much all there is to these three concepts as they are applied to lists. One important concept is that all 3 are parallelisable. If you distributed the input list in chunks to 10 machines, you could reduce the time needed to perform the calculation, be it monoidic, functoric (? does that word exist) or monadic.

However, the three concepts can be applied to things other than a list. To understand how, let’s have a look at what a list is.

A list contains the idea of an ordered collection of similar things. For example a certain ordering of numbers, or a carpark at a certain moment of time, or my favourite tv series when I was young. The word “list” by itself doesn’t tell you as much as “list of vitam C content of various citrus fruits”. Programming languages have a word for this concept, they call it a parametrised type. List[Int] is a different type from List[String], although both are lists and have a certain ‘list’-iness. If a calculation should be performed on a List[Int], it probably won’t work when you try to perform it on a List[String]. (Exceptions would be calculations which are only interested in the ‘list’-iness, things like “length” or “are you empty?”)

Can we think of other parametrised types? Well, yes, there are quite a few. A standard example is an Option, which you can think of as a list which either contains one item or is empty. Another possibility is a Try, which you can think of as a box which either contains a value you hope to get, or an explanation as to what went wrong. Or there’s the Future, which is a box which doesn’t contain a value at the moment, but will do at a later date.

Now comes the interesting thing. If we have code that works on lists by calling the methods collect, map and flatmap, we could use the same code for dealing with Options and Futures and stuff if we found good definitions of these methods for those parametrised types. Let’s take the Option (which we’re thinking of as a list of zero or one element) as an example. Just to make juggling with Options easier, I’m going to call an empty Option None, and an Option which actually contains something Some(contents).

Monoid => just return contents, if it exists

Functor => perform the given function on contents if it exists. So the Option turns into Some(function applied to contents). If not, the Option remains as None.

Monad is a bit trickier. Remember with the list we applied a function which turned each element of the list into its own list? With an Option the corresponding function would be one that turned contents (if it exists) into Some(function applied to contents). Why would we want to do this? Well, let’s consider the case that the computation we want to perform may only return a value for certain inputs, like “which is the smallest room in your flat large enough to contain a whale”. The result may be a room, or (more likely) nothing. But this is exactly what an Option itself is — a wrapper around the uncertainty of the existence of something.

So the monad allows us to chain computations or questions or functions which themselves return Options. Consider the following line of questioning, every step of which could return nothing:

1. Name the first animal you saw yesterday (could be None, if you stayed indoors all day)
2. Which is the smallest room in your house large enough to contain this animal (could be None, if you saw a whale yesterday morning)
3. What is the colour of the wallpaper in this room (could be None if the room doesn’t have wallpaper).

The result would be an either Some(yellow) or None. The important thing about the Option is that the chain of questioning will complete. It won’t get stuck somewhere not knowing what to do (for example, getting stuck at the second question because you didn’t see an animal yesterday so the question makes no sense). It will just record “no answer found” (i.e. None) and from then on record “no answer found” as the answer to any subsequent question.

That’s all from me for now. I may try to add stuff later :) Maybe some hints on what a language has to support in order to make monads and things easy to create and work with.