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.
>>=
is called ‘bind’ .return
isn’t likereturn
in other languages.- Monads also define
>>
andfail
, 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 byreturn
, 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 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
.
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