Monads in Minutes

Jump to:
Introduction
Why do we Need Monads?
The Monad Laws
Examples
Category Theory

Introduction

I'd like to preface this article by explaining why I think many people find monads confusing. In the context of programming, a monad is not fundamentally unlike an interface; it's just that the functions that a monad must implement (and perhaps the properties that the functions must satisfy) seem alien at first. Many examples of a certain monad in action can be given, but they all seem unrelated, which can be confusing. It's ultimately the existence of these many examples that makes monads such a critical idea - it turns out that many useful notions of computation (to use Moggi's terminology) can be encoded in a pure functional language as monads.

In other words: I think you think monads are confusing because you are looking for a motivation for the definition, but the usefulness of the definition comes after we start applying it.

A pure functional program is simply a composition of functions. That is, a sequence of functions whose domains and codomains match up so that input can be passed through consecutive functions. A pure imperative program is a sequence of commands for the retrieval and manipulation of data. It's difficult to see how commands like this could be composed in the way pure functions can be. A monad is a special kind of operator on types that allows us to compose imperative actions in the same way that we do functions. This is why monads are important - they allow us to do things like achieve side effects, monitor state, and throw exceptions in a pure functional language.

It's best to know a little bit about Haskell syntax before reading this article. If you know any other functional language you can probably catch on pretty easily. The only Haskell features that pop up are lambdas, pattern matching, and type signatures. If you're totally new to Haskell, I would recommend checking out Real World Haskell or Miran Lipovača's Learn You a Haskell for Great Good!

Why do we Need Monads?

Monads answer the question of how to get imperative behavior in a pure functional language. What distinguishes functional behavior from imperative behavior? In a pure functional language the only thing you can actually do is compose and apply functions, where functions are always look-up tables that don't change and do nothing but return a value whenever they are passed an argument of the correct type. Just like in all forms of programming, it is common to solve a problem by composing many functions, each of which solves part of the problem and is more understandable to the programmer. Most compilers for imperative languages aren't optimized for this sort of behavior in its purest form, which always uses recursion instead of loops. Imperative programs are sometimes written as a sequence of commands; each one without any input or output. A crude example:

void main() {
getInput();
processInput();
printOutput();
}

You could of course make processInput() a pure function, bind the input to a variable, pass that variable to your new pure function, and then print out the result. However, the act of getting input and printing output are still side effects. They can't be composed like ordinary functions. This doesn't mean there isn't any way to compose them at all. Let's take a look at the defintion of a monad in Haskell:

class Monad m where
return :: a -> m a
(>>=):: m a -> (a -> m b) -> m b
(>>):: m a -> m b -> m b

What the first line of this declaration is saying is that there exists a class called Monad whose instances, m, act as wrappers for an arbitrary type a. Below the declaration is a number of functions which this wrapper must implement. So it's kind of like an interface in object oriented programming.

The first function that our monad, m, must implement is called return, not at all to be confused with the return statement in imperative programming. The type signature for this function says that it goes from the arbitrary type a into the monadic value of that type, m a, i.e. the monad wrapping that type. This is like the generic constructor that classes/structs/objects have in object-oriented programming. That is to say, every monad must have at least one type constructor. We'll get into what exactly is special about return when I talk about the constraints that these functions must satisfy.

The next weird looking function is called the bind operator. Looking at it's type signature, we see that it takes in m a, followed by a function from a to m b, and then outputs something in m b. What could that be useful for? Well, let's return to the example of the imperative program with side effects, there is a monad called IO, which deals with input/output actions, there is a value in IO String called getLine, which secretly holds the value of the string that a user enters at the console. There is also a function putStrLn with type String -> IO () that simply takes a string as input and outputs a monad action that prints it to the console. Recall that () is the type of tuples that wrap no values - i.e. the type with only one element. Then I could write a Haskell program that looks like this:

main = getLine >>= putStrLn . processInput

In this case, processInput must be a function that takes any string to a string. The "." represents the composition of processInput and putStrLn. So this program executes the action of getting the input from the console, the bind operator then unwraps it and sends it to a function that processes it and then prints the output to the console. I like to think of the >>= symbol as squeezing the value out of the monadic value and then injecting it into the function on the right. Regardless of metaphor, what we've done is compose imperative actions even though they don't output values! This may look very alien and non-imperative, but Haskell has something called "do notation" that can be used to make particularly long sequences of monad actions more readable.

Finally, >> gives us a way to compose arbitrarily many monad actions of different types (the monad must remain the same but the type that it wraps can be different for each of the actions being composed), without having to explicitly unwrap any data. This means that >> can literally be read as "and then do" in code. For example:

main = (getLine >>= putStrLn . processInput) >> main

Is the exact same program that we constructed before except that it repeats itself every time after printing. I like to think of the >> symbol as an arrow telling the program where to go next.

The Monad Laws

You can't just make any old parametrized type that implements functions with the above type signatures and call it a monad. You could in Haskell, GHC doesn't check that an instance of Monad obeys these rules; that would be extrmely difficult, so its up to the programmer. If you wrote an instance of monad that didn't satisfy the properties described below then it wouldn't be a monad by the mathematical definition and it probably wouldn't be as useful as an actual monad. For a monad to be a monad it's functions have to satisfy the following "monad laws:"

Left Identity: return a >>= f = f a
Right Identity: m >>= return = m
Associativity: (m >>= f) >>= g = m >>= (\x -> f x >>= g)

These requirements are a lot simpler than they appear. The first one says that if we wrap up a value using return, then we want >>= to be able to unwrap that same value and feed it to the next function. The second condition says something similar it just looks more strange because there aren't any non-monadic values in the definition. It says that if >>= unwraps a value and feeds it to return, then we'll get the same wrapped value back. Hopefully it makes sense that both of these things would be something desirable for a default type constructor, which is basically what return is.

As for the associativity condition, since function composition is a associative, i.e. (f . g) . h = f . (g . h), we desire the same thing to be true when we compose imperative actions. The left side of the equation represents feeding the value inside m into f and then feeding the result into g; the right side of the equation represents first constructing a function (the lambda) that takes x then feeds it into f then into g and then feeding the value inside m into this lambda. The associativity condition ensures that these two ways of feeding the value inside m through the functions are the same.

Examples

The example that I've already brought up is the IO monad. IO stands for Input/Output, so it's role is pretty self-exaplantory - monad actions get compiled to input/output actions.

Another common example of a monad that isn't often referred to as a monad is [a], the type of lists with elements from a. Here's what the monad functions look like for lists:

return x = [x]
xs >>= f = concat (map f xs)
xs >> ys = ys

return simply takes a value and makes a list that contains only that value. The bind operator maps the function onto the list that is passed to it, which makes a list of lists, and then concat flattens that list. The then operator simply returns the second list. This may seem useless, but its not quite useless. In functional programming the great thing about the type of lists is that it is an instance of Functor. This is the typeclass which gives us the map function for lists, which takes a list and a function and applies the function to every element of the list. It turns out that the monad structure of the list type isn't completely essential for applications, but map can be written in terms of >>= and return (how?).

Maybe a is a type that is probably less familiar to object-oriented programmers but it's not at all difficult to understand:

Maybe a = Just a | Nothing

This means that Maybe a, for some type a, is either a box called Just with a value from a inside it or it's a box called Nothing with nothing inside it. This wrapper for types is excellent for representing computations that could fail. Here's how it works as a monad:

return x = Just x
Nothing >>= f = Nothing
Just x >>= f = f x
Nothing >> _ = Nothing
Just _ >> m = m

In practice, the use of this type's monad functionality is extremely useful. Imagine this, you have an important function, foo :: String -> Maybe String, and it's broken into steps:

foo = stepThree . stepTwo . stepOne.

But the failure that causes the output to be Nothing could happen at any step, i.e.:

stepOne :: String -> Maybe MyType
stepTwo :: MyType -> Maybe [Int]
stepThree :: [Int] -> Maybe String

So since the domains and ranges don't match up, foo = stepThree . stepTwo . stepOne would actually cause a type error. What we can do, however, is say

foo = \x -> stepOne x >>= stepTwo >>= stepThree

And huzzah! We have a way of composing computations that could fail without having to manually unwrap the value for each step!

I want to conclude this section by mentioning that if the metaphor of >>= unwrapping the value in its first argument and injecting that value into the function that is its second argument, that's okay. The Control.Monad library provides a few variations of the bind operator:

(=<<) :: (a -> m b) -> m a -> m b
(>=>) (a -> m b) -> (b -> m c) -> a -> m c

The first operator can be thought of as if its "lifting" a function a -> m b to a function m a -> m b. And the second operator could be thought of as a literal composition of functions, so we can rewrite our important functions like so:

foo = stepOne >=> stepTwo >=> stepThree

Category Theory

Everything that I've covered so far should allow you to effectively use monads as a programmer. But there is more to the definition of a monad. I'm assuming you're familiar with basic categry theoretic terminology from this point on. If you aren't, I'd recommend Bartosz Milewski's online book Category Theory for Programmers, which has lots of C++ examples, or his YouTube series, which makes more use of Haskell.

The first thing we should discuss is monoids. Monoids are usually formulated in terms of sets. Specifically, a monoid is a set $S$ with an operation $(\cdot) : S \times S \rightarrow S$ and $1\in S$ such that $$\forall s\in S \quad 1\cdot s = s \cdot 1 = s$$ $$\forall a,b,c\in S \quad (a\cdot b)\cdot c = a \cdot (b\cdot c)$$ One familiar example of a monoid is the type of lists of any data structure. That is, the identity, $1$, is the empty list and the binary operation is concatenation. Another example of interest is the set of all functions from a given set to itself; the identity is the identity function and the operation is composition of functions.

In category theory however, we don't like talking about sets. We want to construct a monoid based on the morphisms of some category. The first thing we have to do is define a monoidal category. A monoidal category $\mathbb{C}$ is one with a bifunctor, called the tensor product, $\otimes : \mathbb{C}\rightarrow \mathbb{C} \rightarrow \mathbb{C}$ and an "identity object," $I$, such that $\forall A,\, B, \, C\in Ob(\mathbb{C})$ there is an isomorphism $\alpha_{A,B,C} : (A \otimes B)\otimes C \rightarrow A\otimes (B\otimes C)$ (associativity) as well as isomorphisms $\lambda_A : I\otimes A \rightarrow A$ (left identity), and $\, \rho_A : A\otimes I \rightarrow A$ (right identity).

We can generalize the idea of a monoid categorically by defining a monoid in a monoidal category. A monoid in the monoidal category $\mathbb{C}$ is an object $M$ in $\mathbb{C}$ with a morphism $\mu: M\otimes M \rightarrow M$ and another morphism $\eta: I \rightarrow M$. These morphisms must satisfy the following "coherence conditions:" $$\mu \circ (id_M\otimes \mu) \circ \alpha_{M, M, M} = \mu \circ (\mu \otimes id_M)$$ $$\mu \circ (id_M \otimes \eta) = \lambda_M$$ $$\mu \circ (\eta \otimes id_M) = \rho_M$$ Recall that $\alpha$ is an isomorphism that "reassociates" the tensor product, so the first condition is analogous to associativity. The second and third conditions are left identity and right identity, respectively. The meaning of these conditions is made much more clear with diagrams, something I do not have but that Wikipedia does. If one assumes that the underlying category is the category of sets, with $\otimes$ being the Cartesian product and $I$ being a set with one element, then the original algebraic defintion of a monoid is recovered.

But again, sets are boring. What's another example of a monoidal category? The category of endofunctors on some category $\mathbb{C}$. $\otimes$ is identified as the composition of endofunctors (which, like the composition of all morphisms, is associative) and the identity object is $id_{\mathbb{C}}$ - the identity endofunctor. So what would a monoid in this category look like? Well, it would be an endofunctor $T$ with a natural tranformation $\mu:T\circ T \rightarrow T$ and another natural transformation $\eta : id_{\mathbb{C}} \rightarrow T$ that satisfy the conditions for a monoid; that's what a monad is!

For a monad, the coherence conditions are as follows: $$\mu \circ T \eta = \mu \circ \eta T = id_T$$ $$\mu \circ T \mu = \mu \circ \mu T$$ In this case, the left and right identity morphisms, $\lambda_T$ and $\rho_T$, are the identity on $T$. $\, (T\eta)_x=T(\eta_x)$ and $(\eta T)_x = \eta_{T\, x}$. Likewise for $T\mu$ and $\mu T$.

But wait how could any of that possibly relate to all the programming? To see, let's make a Haskell type class:

class MyMonad M where
fun :: (a -> b) -> (M a -> M b)
mu:: M (M a) -> M a
eta :: a -> M a

fun is the endofunctor itself. The endofunctor is acting on the category of all Haskell types. A functor acts on both objects (types) and morphisms (functions). When the functor acts on a morphism $f$ it yields a morphism whose domain is the functor acting on the domain of $f$, likewise for the codoamin. This explains the type signature of the first function in our class. The others shouldn't be too difficult to understand as they are equivalent to $\mu:M\circ M \rightarrow M$ and $\eta : id_{\mathbb{C}} \rightarrow M$. The difference is that in the category-theoretic notation we consider the endofunctor as acting on the entire category but in Haskell notation we are considering it as acting on a particular object.

We also demand that these functions satisfy the above conditions for a monad. In Haskell, these can be written like so:

eta . f = fun f . eta
nu . fun (fun f) = fun f . nu

Now that we have that set up, let's show that it's equivalent to the definition of monad in Haskell. Haskell monads are actually called Kleisli triples in Category theory, so let's call our next class that:

class KleisliTriple T where
ret :: a -> T a
>>== :: T a -> (a -> T b) -> T b

Notice that the then operator, >> is not defined in a Kleisli triple. That's because it actually has the following default implementation:

m1 >> m2 = m1 >>= (\_ -> m2)

The KleisliTriple class must satisfy the "monad laws" discussed earlier in the article. Now all that's left to do is the following:

instance KleisliTriple t => MyMonad t where
fun f m = m >>== (ret . f)
eta = ret
mu m = m >>== id

instance MyMonad t => KleisliTriple t where
ret = eta
m >>== f = mu (fun f m)

One can verify that if the conditions for either instance are assumed, the conditions for the other follow. I won't show that here since I think its a useful exercise for the reader. Once that's been done, however, you've proven that Haskell monads are monoids on the category of endofunctors on the underlying category of Haskell types!