Monads

Let's generalize the pattern we have developed in the previous section. We had a functor Writer, and we equipped it with a function composition operator

(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)

In general, what we're after is a functor m (for "monad") and a function composition operator

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

Let me emphasize one more time that this is a rather special function composition operator. Normal function composition has the type

(.) :: (b -> c) -> (a -> b) -> (a -> c)

f . g is the function that simply applies g to its argument and then applies f to the result. That's all that happens, and it is possible because the return type of g exactly matches the argument type of f. The (>=>) operator does more than that. In the expression f >=> g, the return type of f is not the same as the argument type of g; it it is the argument type of g decorated using the functor m. The (>=>) operator needs to strip this decoration off f's return value, pass the undecorated value, which has exactly the type expected by g, to g, and then combine the decoration of g's return value with the decoration we removed from f's return value.

As we will see, it will also be useful to have a function that allows us to manually decorate a value of type a with our functor m. This function is

return :: a -> m a

Any functor that comes equipped with these two operations is a monad:

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

Well, not quite. For m to be a monad, the implementations of return and (>=>) need to satisfy two monad laws:

Identity: If f :: a -> m b, then
```
return >=> f = f = f >=> return
```
In other words, composing any decorated function f with return just gives us f again; return acts like the unit element with respect to decorated function composition, just as 0 is the unit element for addition, 1 is the unit element for multiplication, and id is the unit for "normal" function composition: id . f = f = f . id.
Associativity: If f :: a -> m b, g :: b -> m c, and h :: c -> m d, then
```
(f >=> g) >=> h = f >=> (g >=> h)
```
Just as with addition, multiplication or "normal" function composition, the order in which we apply function composition to a sequence of decorated functions doesn't matter.

Where do these laws come from? They are exactly the laws that a monad in category theory needs to satisfy, and it turns out that they ensure that monads are well-behaved, which turns them into a useful abstraction in programming.

The above definition of the Monad class is not exactly the one you find in the Haskell standard library. The way Haskell programmers think about monads is as functors that are instances of the following class:¹

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

Instead of an operator (>=>) to compose decorated functions, we have an operator (>>=), called "bind", that we should think of as decorated function application. For pure functions, we have f . g for function composition and f $ x for function application. The two operators are (.) and ($). For decorated functions, we have g >=> f for function composition and x >>= f for function application. The two operators are (>=>) and (>>=).

In the expression x >>= f, x is a decorated value and f is a decorated function. This expression strips the decoration off x, applies f to the resulting undecorated value of type a, and then combines the return value of f with the decorations of x and f's return value.

Mathematicians use yet another definition of a monad:²

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

As the name suggests, if we have a value of type m (m a), that is, a value that has been decorated twice, join combines the decorations and returns a singly decorated value of type m a.

In the standard library, we have the definition of the Monad class that uses return and (>>=), the second definition given above. Neither join nor (>=>) is part of the definition of the Monad type class. However, the Control.Monad module provides them as separate functions that can be used with any monad. These implementations of join and (>=>) are possible because all three definitions of the Monad class we have given above are equivalent: we can implement each of (>>=), (>=>) or join in terms of the others, possibly with the help of return and fmap. Let's see what these implementations look like. Specifically, we'll discuss how to implement (>>=) and (>=>) in terms of each other, and (>>=) and join in terms of each other. Thus, we can go from any of these three functions to any other by combining one or two of these implementations.

From `join` to `(>>=)`

The goal of x >>= f is to take a value x :: m a and a function f :: a -> m b and apply f to x somehow. The result should be a value of type m b. We start by observing that any monad is a functor, so we have

fmap :: (a -> c) -> m a -> m c

If we set c = m b, then f certainly has the type a -> c, so fmapping f over x gives a value of type m c, that is, a value of type m (m b):

fmap f x :: m (m b)

However, we want a value of type m b. That's exactly the problem that join solves for us, as we have join :: m (m b) -> m b. This gives

(>>=) :: m a -> (a -> m b) -> m b
x >>= f = join $ fmap f x

This works out as far as types go, but does it do the right thing? Let's see. The intuition about fmap f x was that it applies f to every value inside the container x (x is a container because it has type m a, and m is a functor). The "value inside x" is just x with the decoration provided by the functor m stripped off. So fmap f x achieves the first goal of x >>= f: applying f to x minus its decoration. What we have now is a value of type m (m b). The outer m is the decoration that x came with. The inner m is the decoration of f's return value. For now, they are separate. join takes these two decorations and combines them into a single decoration of type m. That was the second goal of x >>= f. So we have an implementation of (>>=) that does exactly what we want, at least intuitively.

From `(>>=)` to `join`

The goal of join x is to take a doubly decorated value x :: m (m a) and collapse the two decorations into one to produce a value of type m a. The tool we have at our disposal is

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

By setting b = m a, we get

(>>=) :: m (m a) -> (m a -> m a) -> m a

So, if we had a function f that allows us to turn an m a into an m a, we could implement join x as x >>= f. What could such a function look like? Knowing nothing about m and a, we don't know how to produce any value of type m a other than the one we already have, x, and there is a function that simply returns its argument, the identity function:

id :: c -> c
id x = x

Thus, we have

join x = x >>= id

Again, we should ask whether this does the right thing, at least intuitively. join x is supposed to take the two decorations of x and combine them into a single decoration, and it should leave the decorated value itself alone. y >>= f takes the decoration of y and the decoration of f's return value and combines them. If set y = x and f = id, then the decoration of y is the outermost decoration of x, the outermost m in the type m (m a). The decoration returned by id is the same as the decoration of its argument. But the argument the expression x >>= id passes to id is x with its outermost decoration stripped off. What we're left with is the innermost decoration of x. Since (>>=) combines these two decorations, it does exactly what join is expected to do.

From `(>>=)` to `(>=>)`

The goal of f >=> g is to take two functions f :: a -> m b and g :: b -> m c and compose them to produce a function of type a -> m c. Let's build this up one step at a time. Here's our skeleton:

f >=> g = \a -> ...

The ... should become a value of type m c. We know how to get a value of type m b from a: we apply f to it:

f >=> g = \a -> let mb = f a
                in  ...

The ... now has to turn mb into a value of type m c. But we know how to do this, because (>>=) has type

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

and g has type b -> m c. Thus,

f >=> g = \a -> let mb = f a
                in  mb >>= g

Inlining the definition of mb gives

f >=> g = \a -> f a >>= g

which is the same as

(f >=> g) a = f a >>= g

So that's our definition of (>=>) in terms of (>>=).

From `(>=>)` to `(>>=)`

Finally, let's see how to implement (>>=) in terms of (>=>). We'll use the const function as a helper. Another helper we need is (). With these two helpers, we can easily define (>>=) in terms of (>=>). Our goal is to take a value x :: m a and a function f :: a -> m b and apply it to x somehow. We have const and our composition operator (>=>) at our disposal. const x is a function of type const x :: c -> m a, because it ignores its argument and simply returns x. By setting c = (), we get const x :: () -> m a. We can compose this function with f to obtain const x >=> f :: () -> m b. But x >>= f should have type m b, not () -> m b. Easy enough: We apply const x >=> f to the value (). This gives

x >>= f = (const x >=> f) ()

What these type calculations show is that we can certainly use any of (>>=), (>=>) or join to implement the other two in a way that they have the right type. The implementations of (>=>) and (>>=) in terms of each other obviously also do the right thing, and we argued intuitively that the same is true for the implementations of join and (>>=) in terms of each other. To formally verify that these are the correct implementations, we would have to formulate the monad laws in terms of join and return or in terms of (>>=) and return. We would then be able to verify that the implementation of (>>=) in terms of (>=>), for example, satisfies the monad laws in terms of return and (>>=) if our monad satisfies the monad laws in terms of return and (>=>). The above implementations have this property, but we won't verify this here.

Another observation to be made is that we need to obtain implementations that work for any possible choices of the involved types a, b, and c. In particular, we know nothing about these types. This severely limits the tools we can use in our implementations, and a careful analysis shows that the implementations above are in fact the only ones that are possible. We won't do this either here.

I hope you agree with me that, as such, monads are a simple concept, even though it seems terribly abstract at this point: We have a functor m, that is, some sort of container type or decorator, depending on our point of view, and this functor must come equipped with two operations: return x takes a value x and sticks it into a container, decorates it. x >>= f takes a container x, applies f to each value in x, and collects the results. This is a bit like fmap f x, but f is not a pure function. f produces itself some container, and we somehow need to combine the containers produced by applying f to all elements in x.

What's remarkable is that a long list of programming abstractions all fit this simple pattern:

Exception handling: Maybe or Either
Non-determinism: the list
Logging: Writer
Context-aware computations: Reader
Stateful computations: State
Input/output: IO
...

Next we'll show that Maybe and Either, lists, Writer, Reader, State, and IO are all monads, and we will see how they allow us to accomplish the things listed here. As optional reading for those who feel adventurous, we will also discuss the continuation monad, which some Haskell geeks would say is the one monad to rule them all.³.

Along the way, we'll learn about do-notation, which makes programming with monads easy and elegant.

This is the definition of the Monad class you would have found in the standard library until a few years ago. Nowadays, you'll find the definition
```
class Applicative m => Monad m where
    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b
```
An Applicative functor is a special type of functor. As the class definition says, every monad is an applicative functor, but there are applicative functors that aren't quite monads. The Applicative type class provides a useful abstraction that allows us to program with such functors almost as with monads. Even the do-notation for monads has been extended to applicative functors. We will not discuss applicative functors in any detail in this course, but I thought I should point out why the definition you see if you type :info Monad into GHCi is different from the one given here. ↩
A note for those of you that are mathematically inclined. (All others, please stop reading this footnote because it will make your head spin.) In category theory, a monad $T$ is an endofunctor from some category $C$ to itself that satisfies certain monad laws. Functors in Haskell are endofunctors of the category of Haskell types, and monads are special types of such endofunctors. Every monad $T$ in some category $C$ must come equipped with two operations $\eta_a : a \rightarrow Ta$ and $\mu_a : T(Ta) \rightarrow Ta$, for each object $a$ in $C$. Those are the methods return and join in our Monad type class, respectively.

Using $\eta$ and $\mu$, we can define a new category where we view arrows of type $a \rightarrow Tb$ as arrows from $a$ to $b$. This is called the Kleisli category of the monad $T$. It turns out that our function composition operator (>=>) in our original definition of the Monad type class is exactly the composition of arrows in the Kleisli category of $T$. The monad laws then state that $\eta$ (return) is the identity arrow in the Kleisli category and that, as in any category, arrow composition in the Kleisli category is associative. This is the mathematical connection between the definitions of the Monad class using return and (>=>) or using return and join. ↩
The reason why the continuation monad is the one monad to rule them all is that many useful monads, such as Maybe, lists, Reader, State, and Writer can easily be implemented from scratch on top of the continuation monad. So, if Haskell didn't give us the ability to define our own monads but somehow came with one monad that's built right into the language, then the continuation monad is the one we should choose to have built right in. We can then achieve the same effects as achieved by Maybe, lists, Reader, State or Writer simply by choosing the right types to decorate using the continuation monad. ↩

Monads

From join to (>>=)

From (>>=) to join

From (>>=) to (>=>)

From (>=>) to (>>=)

From `join` to `(>>=)`

From `(>>=)` to `join`

From `(>>=)` to `(>=>)`

From `(>=>)` to `(>>=)`