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 examples2 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.

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 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 >>=:

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:

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 Discourse3 ):

…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.Monad4 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-notation5 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.