Why we need monads, what they are and where we can see them.

Motivational introduction

Outlines what purpose monads serve in computer science.
The shaded paragraphs are supposed to be more in-depth and give a mathematical background; they can be omitted and it should not affect the overall understanding.

Functional languages are founded on the idea of function composition; having $f: A \longrightarrow B$ and $g: B \longrightarrow C$ we can create a composition $gf: A \longrightarrow C$. Suppose now those functions have some additional, common behaviour. Maybe they sometimes don’t return a result (e.g. because something is undefined) or maybe they return a varying number of results.

In a strongly typed language we’d represent this additional behaviour by a different type of the return value. Let’s stick to the example of possibly not returning a value. We’d introduce a type constructor Maybe, $M$ for short, and our functions would have signatures $f:A \longrightarrow MB$ and $g:B \longrightarrow MC$.

We still do want to compose them. The additional behaviour shouldn’t be a problem; both functions have it. But now the types are incompatible. We want to apply $g$ after $f$ but $g$ accepts type $B$, not $MB$. We are stuck. Monads are a device to break this impasse; let’s keep this in mind for the rest of the section.

Taking a step back, another thing besides composition of functions that we can employ is the identity function $id: A \longrightarrow A$, a trivial computation for any type $A$. Now, it turns out that there is a mathematical structure built on top of these two properties - a category.

It belongs to category theory, a mathematical area that tries to describe things in the most general way possible. Thus the definition of a category is very non-specific. Intuitively, it's a thing with some objects and with some things between these objects (like functions between sets). Formally:

For more details refer to chapter 1 in [1]. So the types of a programming language together with its functions form a category.

Further into category theory, there is a notion of a monad. It is different from the computer science monad we are discussing and we are not going to give its definition (the reader can refer to 5.1 in [1]). But it is closely related to the one we are interested in.

A monad $M$ on a category $\mathcal{C}$ gives us another category, the Kleisli category $\mathcal{C}_\mathbb{M}$. The only thing we need to know about it is that its arrows are the arrows in $\mathcal{C}$ of the form $f:A\longrightarrow MB$. Because the Kleisli category is ineed a category, we can compose those arrows - which is precisely what we wanted.

The upshot is as follows: if we have functions with some additional behaviour represented by $f:A\longrightarrow MB$ and if the type constructor $M$ has some nice properties, then we can compose those functions despite an apparent type inconsistency. This is what monads are all about.

What is a monad?

Presents two definitions of a monad in computer science.
The shaded paragraphs serve as their comparison and discussion. They are more mathematically involved and can be safely skipped if they bring more harm than good.

Much in the spirit of the above reasoning, the definition of a computer science monad can be given as follows ([5]):

A monad is a map $M$:

1. sending every type $X$ of a given programming language to a new type $MX$.
2. equipped with a rule for composing two functions of the form $f: X \longrightarrow MY$ and $g: Y \longrightarrow MZ$ to $gf: X\longrightarrow MZ$. The functions are called Kleisli functions and the composition the Kleisli composition.
3. together with a map $\mathrm{pure}_X: X\longrightarrow MX$ for every type $X$ that acts trivially in the composition. The Kleisli composition is required to be associative.

The Kleisli functions are the functions with additional behaviour discussed in the previous section.

A more practical definition offered by Haskell [1] states:

A monad is:

1. a type constructor $m$
2. a function $a \longrightarrow ma$ building values of type $m$, called return
3. a combinator function called bind of the form $(ma, a \longrightarrow mb)\longrightarrow mb$ for any types $a, b$. Typically denoted $x\ {\scriptstyle \gg=}\ f$.

So given a monadic value $x$ of type $ma$ and Kleisli function $f: a\longrightarrow mb$ the bind function gives us a way to apply $f$ to $x$. The monad above has to also satisfy the laws equivalent to the third point in the previous definition.

A natural question to ask would be about the meaning of the $\mathrm{pure}$ function (and its counterpart from the second definition - bind). If all we want is a composition of Kleisli functions and this is guaranteed by the second point in the definition, why bother with the third?

$\mathrm{pure}$ and bind are in some sense trivial computations; ones such that composing them with others does not make any difference. They provide an "obvious" or "natural" way to get from a value in $X$ to a value in $MX$.

The fact that such trivial computations exist ensures that $M$ is not too weird, that it has some nice structure. Mathematically speaking, this means that the computations of the form $A\longrightarrow MB$ form a category (the Kleisli category we mentioned before).

The requirement of being a category is a really basic one. If we don't insist on it and don't require the existence of $\mathrm{pure}$ function, we would allow some very irregular and strange structures to be monands. Ones that would be irregular enough to not have any practical value anyway. It's better to simply disregard them.

For now we will leave it as an open question: what are those irregular structures? What "monads" would we get if we didn't require the $\mathrm{pure}$ and bind functions and their associated laws in the definition?

Another question we might want to ask concerns the relation between the two definitions. Are they equivalent? First points are clearly the same. $\mathrm{pure}$ for a given type is the same as bind and the associated laws are already stated to be equivalent. The only question is whether having Kleisli composition is the same as having the bind combinator.

Indeed if we have a bind function then we get a Kleisli composition by defining $gf(x) := f(x)\ {\scriptstyle \gg=}\ g$. Before looking into whether a Kleisli composition gives us bind let's look at the Haskell definition more closely; the findings below are not immediately obvious but the reader will be spared the detailed proofs.

The three points of the second definition together with its laws ensure that the return function is injective for any type $a$ unless $ma$ is trivial. In both cases $m$ is a functor and $(m, \mathrm{return}, \left(\mathrm{return}_m)^{-1}\right)$ is a monad in the category theory sense.

If $\mathrm{pure}_X$ from the first definition happens to be injective as well then indeed we get a bind from the second. In general however, it looks as though it need not be.

Again, we leave these as open questions: can we construct a monad as in the first definition without $\mathrm{pure}_X$ being injective? Can $M$ be non-monadic in category theory sense? Can it be non-functorial?

So in general the first definition seems broader than the second. However, in all practical and useful cases in which computer science is actually interested the two definitions coincide and one should forget the potential discrepancy.

Examples of monads in programming languages

Three examples: language-agnostic list constructor, Optionals from Java as semimonad and random number generators from Haskell.

A list constructor

A list constructor $L$ can be given a structure of a monad. Kleisli functions in this case are functions returning a varying number of results.

Let’s take an example of a function $f$ that takes a chess position and returns a list of possible chess positions after one move. We want compose two such functions $f: \mathrm{ChPos}\longrightarrow L\mathrm{ChPos}$ to get a function computing possible chess possitions after two moves.

How would we do that? $f(x)$ is a list of chess positions $[x_1, x_2, \ldots]$; we’d apply another $f$ to every such position getting a list of lists of positions $[[x_1’, \ldots], [x_2’, \ldots], \ldots]$. Then we’d flatten this list to a simple list of positions $[x_1’, \ldots, x_2’, \ldots]$.

The $\mathrm{ChPos}$ is just an example, but it’s clear that we could do the same with all functions returning a list of elements. The bind is the operator applying a function to every element of a list and flattening the result. The return for an element $x$ returns a list containing this single element $[x]$. These two together with $L$ form a monad

Optionals in Java

Optionals are Java-implementation of the $\mathrm{Maybe}$ we took for an example in the first section. For instance, Optional<String> can be thought of as a box which can either contain a String or be empty.

The Kleisli functions, are those that may not return a value. For example suppose the objects we work with are Sheep. Those sheep have families and we can write functions returning a given sheep’s parent. But if the sheep is cloned, it does not have parents, the function would return null.

If we ever want to write functions returning grandparents, we’d have to check first whether the father is defined and only in this case one could search for its parents. For great-grandparents it’s even worse; the deeper we go, the more ugly it becomes.

But this seems wrong, doesn’t it? If we have a function returning the father, returning the grandfather should be just a composition of two such functions. That’s the most clear and elegant solution, no null-checking should be involved. Indeed, in this case Java has us do the following:

where Optional.ofNullable is the $\mathrm{return}$ function and Optional.flatMap is the $\mathrm{bind}$. Looks like a monad and Kleisli composition!

However, we mentioned before that a monad has to also satisfy some laws in order to really be a monad. It turns out that Java’s Optional does not always abide these.

One of those laws is the left identity which says that $\mathrm{bind}$-ing a function to a $\mathrm{return}$-ed value has to be the same as just applying the function to the value. In Java terms this reads:

Optional.ofNullable(x).flatMap(f).equals(f.apply(x))

for any value x and any Function f. In other words, $\mathrm{return}$ is like an identity function. Whenever x is not null this works fine, but consider the following example:

This code breaks down; left side is an empty Optional, and the right one - minus one.

The problem here is that Optional.ofNullable(null) is translated to Optional.empty. So even if f is defined to work on nullable values of x, on the left-hand-side it never gets executed.

Thus Java’s Optional is not a full monad. What are the implications of this? For the answer as well as for some additional account of the topic consult [4].

Random numbers in Haskell

Consider generating random numbers in a purely functional language like Haskell. Purely functional means that any function always returns the same result for the same input. In this setting functions like random() returning a random number from $(0, 1)$ are not allowed to exist; the input is always the same (empty) so the output has to be as well. The best we could do would be to imitate xkcd:

Jokes aside, how functions like random() work in “traditional”, non-functional languages? They sample some data like mouse movements or time in nanoseconds from the system and produce a value based on these. Such implicit arguments are not allowed in functional languages, so what one has to do here is to pass this data explicitly as a parameter, in the form of some object.

So, in languages like Haskell functions returning random values take a random number generator object, rng, and return a value together with another rng (in case we want to generate more numbers in the future. We can’t reuse the rng that we passed initially – as explained above it would return the same value!). The signature of such functions is

$$r\longrightarrow(v, r)$$

A function of this form is called a stateful computation, sc, because what we are doing is passing some state $r$ to the function based on which it returns a value together with a new state. In the case of our example the state is the rng. The type of an sc is defined to be the type of the return value - $\mathrm{type}(v)$ in the above notation.

Using these, to write a function returning three random numbers we’d need to write code like the following:

where we have to manually pass the subsequent rngs to subsequent function calls. If the reader thinks this is ludicrous we totally agree and if she expects we are going to use monads to get around it, she is not mistaken.

So, for a given type $a$, what could monadic $ma$ be? We really have only one choice - it’s going to be stateful computations with values in $a$. Thus the values of Kleisli functions are stateful computations. Their signature is:

$$f: a \longrightarrow (r\longrightarrow(b,r))$$

This means that $ma$ is a functional type - it’s values are functions, the scs. Don’t get lost on this.

We need to find bind and return functions for a complete monad. Starting with the latter, what would be a trivial sc for a value $x$? It’s a function - one that yields $x$ for all states $r$.

$$\mathrm{return}\ x = r \longmapsto (x,r)$$

To come up with a bind suppose we have an sc $c: r \longrightarrow (a, r)$ of some type and a function $f: a \longrightarrow (r \longrightarrow (b, r))$ from that type to scs of possibly some other type. E.g. $f(a)$ could be an sc returning two values, the first of which is always $a$.

$c\ {\scriptstyle >==}\ f$ is an sc, name it $c’$. Intuitively, what we want it to do on a state $r$ is to do whatever $c$ did and then do whatever sc returned by $f$ does. To be precise the definition of $c’$ is:

Now the function generating three random numbers with a bit of Haskell’s syntactic sugar can look as follows:

Thus, what monads did to us is carrying out the pesky state passing implicitly, out of our sight, making the code look much more like what we would expect in a “traditional” language. For a more careful account of the topic you could refer to [3].

Leibniz’s monads

A taste of the meaning of monad in philosophy. Unrelated to computer science.

The term monad, from Greek monas, “unit”, was first used by Giordano Bruno. He claimed the world is homogeneous, one; nevertheless, it consists of a multitude of self-contained units. Like a point, mathematical minimum, is a basic component of space, and an atom, physical minimum, of that of matter - monad is a metaphysical minimum. Their shapes and forms are unique (which followed naturally from God being the ultimate perfect creator of infinite inventiveness).

It was then picked up by Gottfried Wilhelm Leibniz, one of the most interesting philosophers of the 17th century. While he’s mostly known for the fundamental contributions to differential and integral calculus, his metaphysical system was equally groundbreaking in its cohesiveness and generality.

Three hundred years ago the most enlightened minds of Europe were debating the problem of substance. It may seem like a silly problem now (or, to be polite, a poorly defined one) but surprisingly, these old ideas influence our language and way of thinking even today.

Rene Descartes rejected the then dominant school of thought, platonism, arguing that the corporeal substance consists of only matter itself, that there are no platonic forms. However, he went only so far in reducing the metaphysical overhead of previous generations - inspired by then state-of-the-art automatons on the streets of Paris, he introduced the distinction between body and mind. And that dualism lives on, three centuries later.

Descartes struggled with explaining how exactly these two substances influence each other. His successors suggested various solutions, most of which seem odd nowadays:

1. They don’t influence each other and they don’t have to because God does that for them
2. They may seem like two substances but in reality they are just two sides of the same coin, so to speak, namely God
3. There is no dualism, and only matter exists (no God here)

But perhaps the most original solution was Leibniz’s. He claimed there is an infinite number of substances but they are of the same kind. In this respect his views were similar to materialists; but looking closer we discover significant differences.

Leibniz believed that every phenomenon is unique, that everything differs from everything else, that there are no two identical leaves or drops of water. There are no two objects that differ only by their positions in space. However, things are similar. Phenomena are continuous series (notice connection to differentials). Straight line is just a special case of a curve, equation - of inequality. Consciousness is a spectrum, a lie is the smallest truth, evil the smallest good. This was Leibniz’s continuity law (lex continui). It allowed him to connect seemingly disjoint phenomena using a coherent framework. An interesting application of this theory was in psychology, where he introduced unconscious states of mind long before Freud (claiming that these were only weak forms of consciousness).

This law, along with his metaphysical pluralism was perhaps the most revolutionary thesis of Leibniz’s philosophy. And here, finally, we come to monads - this is how he called these simple individual units of being. Unfortunately for computer science-oriented readers, they have little in common with Haskell. Perhaps the most significant is that they don’t have windows, as Leibniz said, each of them being a closed universe that acts upon its environment but cannot be influenced from outside.

Bibliography

1. All About Monads, Wiki Haskell
2. Category Theory, 2015, Peter Johnstone
3. For a Few Monads More, Learn You a Haskell for Great Good!
4. How Optional Breaks the Monad Laws and Why It Matters, Sitepoint
5. Monad (in computer science), nLab
6. The List Monad, School of Haskell
7. Why Do We Need Monads?, Stack Overflow