## Introduction

Some very brief notes summarizing the abstract side of Haskell monads. It’s my crib sheet, written partly to straighten matters in my own mind and partly for future reference.

Most of the information here comes from the usual places, notably the Typeclassopedia.^{1} I’m also indebted to Dominic Prior for many helpful discussions. Dominic is collecting useful and interesting monad examples^{2} on Google Docs.

## Basic definitions

There are (at least) four sensible ways to define monads, but they’re all equivalent: you get the same monad in every case.

`>>=`

is called ‘bind’ .`return`

isn’t like`return`

in other languages.- Monads also define
`>>`

and`fail`

, but we’ll ignore them for now.

### The standard Haskell formulation

The standard Prelude defines monads thus:

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

with the (unenforced) rules that:

```
return a >>= f = f a
a >>= return = a
(a >>= f) >>= g = a >>= (\x -> f x >>= g)
```

Intuitively `return x`

‘puts’ x into the monad in a ‘natural’ way. Continuing the intuition, `x >>= f`

applies function `f`

to value `x`

It’s worth noting the signature for `f`

,

`f :: Monad m => a -> m b`

which implies that it’s the function’s responsibility to put its result into the monad. Conversely `>>=`

gets the value from the monad, then applies the function to it. From the outside, everything stays inside the monad. ‘Get’ and ‘put’ are deliberately vague because they mean different things in each monad.

We can make a stronger statement: there are no generic monad functions to take things out of the monad. Put another way, all the function types end in `m x`

, never just `x`

.

Our intuitive view of `>>=`

and `return`

make the first two monad laws easy to understand.

- The first says that the unwrapping bit of
`>>=`

exactly cancels out the wrapping done by`return`

, leaving only the function applying bit. - The second says that you get the same cancellation if you do the unwrapping then the wrapping.

The third law tells us how to compose two monadic functions. On the left we apply first `f`

then `g`

to `a`

, whilst on the right we apply the lambda expression to `a`

. So, that lambda expression must encode applying first `f`

then `g`

.

Note that the monad laws are exhaustive in the sense that they cover all the non-trivial binary combinations of `return`

and `>>=`

:

`return`

…`>>=`

`>>=`

…`return`

`>>=`

…`>>=`

### Building on functors

Instead of building monads from scratch, we can build them from some of Haskell’s simpler abstract type classes: functor and applicative. In future Haskell might well make this the default.

Let’s look at the declarations:

```
class Functor f where
fmap :: (a -> b) -> f a -> f b
class Functor f => Applicative f where
(<*>) :: f (a -> b) -> f a -> f b
pure :: a -> f a
class Applicative m => Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
```

and the laws which instances of these classes should obey:

```
fmap id = id
fmap (g . h) = (fmap g) . (fmap h)
pure id <*> v = v
pure f <*> pure x = pure (f x)
u <*> pure y = pure ($ y) <*> u
u <*> (v <*> w) = pure (.) <*> u <*> v <*> w
return a >>= f = f a
a >>= return = a
(a >>= f) >>= g = a >>= (\x -> f x >>= g)
```

Finally, because every monad is an applicative, and every applicative is a functor, we can write the characteristic functions of the simpler classes in terms of the more complicated ones:

```
fmap f x = pure f <*> x
fmap f x = x >>= return . f
pure = return
f <*> a = f >>= \x ->
a >>= \y ->
return $ x y
```

Clearly `pure`

and `return`

are very similar animals, but let’s look instead at the function-applying functions:

```
fmap :: Functor f => (u -> v) -> f u -> f v
(<*>) :: Applicative a => a (u -> v) -> a u -> a v
(=<<) :: Monad m => (u -> m v) -> m u -> m v
(=<<) = flip (>>=)
```

We can regard all three functions as tweaking a function so that it applies to a wrapped value. However the function being transformed is different in each case:

`fmap`

takes a pure function:`(u -> v)`

.`<*>`

takes a function already in the applicative:`a (u -> v)`

.`=<<`

takes a function which puts its result into the monad:`u -> m v`

.

### Doing it with join

Consider the implementation of `fmap`

with `>>=`

:

`fmap f x = x >>= return . f`

It’s clear that to some extent `>>=`

duplicates the functionality in `fmap`

, and somewhat begs the question whether we could distil the unique part of `>>=`

into a different function. Happily we can: it’s called `join`

, and gives us a third way to define a monad:

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

Note that `join`

is almost the inverse to `return`

, but `join`

will only collapse two lots of wrapping into one: it won’t return a pure value from the monad. More poetically (ex The Universe of Discourse^{3} ):

…a monad must possess a join function that takes a ridiculous burrito of burritos and turns them into a regular burrito.

We can implement `join`

in terms of `>>=`

, but we need both `join`

and `fmap`

to implement `>>=`

:

```
join x = x >>= id
x >>= f = join (fmap f x)
```

Finally we need different, but equivalent laws for this definition of monads:

```
return . f = fmap f . return
join . return = id
join . fmap return = id
join . fmap join = join . join
join . fmap (fmap f) = fmap f . join
```

### Kleisli composition

Recall that in the third monad law for `>>=`

we discussed how to compose monadic functions:

`(a >>= f) >>= g = a >>= (\x -> f x >>= g)`

where the lambda expression on the left hand side applies `f`

then `g`

. The lambda looks a bit unwieldy but happily there is a standard name for this, the Kleisli composition arrow:

```
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
f >=> g = \x -> f x >>= g
```

This gives us our fourth and final definition:

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

It transpires that if we rewrite the laws to use `>=>`

instead of `>>=`

they take on a much more elegant form:

```
return >=> f = f
f >=> return = f
(f >=> g) >=> h = f >=> (g >=> h)
```

In other words `return`

is the left and right identify for `>=>`

, and `>=>`

is associative.

We can also express `fmap`

, `join`

, and `>>=`

succinctly:

```
fmap f = id >=> return . f
join = id >=> id
(>>= f) = id >=> f
```

There’s a fun game to play with the types in the expression for `join`

. Recall:

```
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
id :: a -> a
```

and so in `id >=> id`

we must have:

```
a ≣ m b
b ≣ m c
```

and thus:

```
a ≣ m (m c)
(id >=> id) :: Monad m => m (m c) -> m c
```

Finally note that the Kleisli arrow is the monadic take on `flip (.)`

, not `.`

:

```
(.) :: (b -> c) -> (a -> b) -> a -> c
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
```

## Standard Monad Functions

Having defined the monad, one gets a whole variety of fun little functions to play with it. Many of these are listed in Control.Monad^{4} and you should consult that for full documentation. The notes below, are my notes on top of that.

`>>`

`>>`

is a specialized version of `>>=`

, which is defined for every monad. We omitted it above because it doesn’t add anything conceptual to the picture:

```
(>>) :: Monad m => m a -> m b -> m b
f >> g = f >>= const g
```

`fail`

Although it’s included in every monad, `fail`

is a mistake, born of `do`

-notation.

### liftM, liftM2, …, liftM5

These lift functions of n-arguments into a monadic form:

```
liftM :: Monad m => (a -> r) -> m a -> m r
liftM2 :: Monad m => (a -> a1 -> r) -> m a -> m a1 -> m r
…
```

They can be expressed as a chain of `>>=`

. For example:

```
liftM2 f x y = x >>= \u ->
y >>= \v ->
return (f u v)
```

though perhaps `do`

-notation^{5} is nicer:

```
liftM2 f x y = do u <- x
v <- y
return (f u v)
```

Finally,

`liftM ≣ fmap`

`ap`

`ap`

provides a more scalable way to lift functions into the monad:

`liftMn f x1 x2 … xn ≣ return f `ap` x1 `ap` … `ap` xn`

The right-hand-side might remind you of applicative:

`(pure f) <*> x1 <*> x2 <*> … <*> xn`

and indeed we find:

```
pure ≣ return
<*> ≣ `ap`
```

It’s easy to implement `ap`

directly:

```
f `ap` x = f >>= \g ->
x >>= \y ->
return (g y)
```

But there’s also an elegant relation to `liftM2`

:

`ap = liftM2 id`

This is obviously true from the expression for `liftM2`

above, but I think there is merit in pondering the result until it is obvious without seeing the innards of the lift.

`sequence`

`sequence`

interchanges the monad and the list:

`sequence :: Monad m => [m a] -> m [a]`

It can be implemented with `foldr`

, where it bears a striking resemblance to the identity fold:

```
sequence = foldr (liftM2 (:)) (return [])
idFold = foldr (:) []
```

Given the fold, we just convert both the step and base-case to their monadic equivalents and get `sequence`

.

## References

- 1. http://www.haskell.org/haskellwiki/Typeclassopedia
- 2. https://docs.google.com/document/d/1DvbcQTibeUEOVmoLO14vvRa27kf6y29sObUmQpyFn9g/pub
- 3. http://blog.plover.com/prog/burritos.html
- 4. http://hackage.haskell.org/package/base/docs/Control-Monad.html
- 5. http://www.haskell.org/haskellwiki/Typeclassopedia#do_notation