10.md

Monads

Motivation

The concept of monad started its life as an abstract bit of mathematics, and it so happened that functional programmers stumbled upon it as a useful programming construct. And it is a useful programming construct!

A monad is handy whenever a programmer wants to sequence actions, and the details of the monad says exactly how the actions should be sequenced.

We’ve already (implicitly) learned about the IO monad, which sequences its actions quite naturally, performing them in order, and gives actions access to read and write anything, anywhere. We’ll also see the Maybe and [] (pronounced "list") monads, which do their own things with sequencing.

In the end, the best way to really understand monads is to work with them for a while. After programming using several different monads, you’ll be able to abstract away the essence of what a monad really is.

Monad

The Monad type class is defined as follows:

class Monad m where
  return :: a -> m a

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

  (>>) :: m a -> m b -> m b
  m1 >> m2 = m1 >>= \_ -> m2

We have already seen these functions in the context of IO. Here, we see that they are available in every monad.

(>>) is just a specialized version of (>>=). It is included in the Monad class in case some instance wants to provide a more efficient implementation, but usually the default implementation is just fine. So to understand it we first need to understand (>>=).

(>>=) (pronounced “bind”) is where all the action is! Let’s think carefully about its type m a -> (a -> m b) -> m b.

(>>=) takes two arguments. The first one is a value of type m a. (These are sometimes called monadic values, or computations. The one thing you must not call them is "monads," since that is a kind error: the type constructor m is a monad.) The idea is that an action of type m a represents a computation which results in a value (or several values, or no values) of type a, and may also have some sort of "effect":

• c1 :: Maybe a is a computation which might fail but produces an a if it succeeds.
• c2 :: [a] is a computation which produces (multiple) as.
• c3 :: IO a is a computation which potentially has some I/O effects and then produces an a.
• c4 :: Rand StdGen a is a computation which may use pseudo-randomness and produces an a.

And so on. Now, what about the second argument to (>>=)? It is a function of type (a -> m b). That is, it is a function which will choose the next computation to run based on the result(s) of the first computation. This is precisely what embodies the promised power of Monad to encapsulate computations which can be sequenced.

So all (>>=) really does is put together two actions to produce a larger one, which first runs one and then the other, returning the result of the second one. The all-important twist is that we get to decide which action to run second based on the output from the first.

The default implementation of (>>) should make sense now: m1 >> m2 simply does m1 and then m2, ignoring the result of m1.

Examples

Let’s start by writing a Monad instance for Maybe:

instance Monad Maybe where
  return  = Just

  Nothing >>= _ = Nothing
  Just x  >>= k = k x

return, of course, is Just. If the first argument of (>>=) is Nothing, then the whole computation fails; otherwise, if it is Just x, we apply the second argument to x to decide what to do next.

Incidentally, it is common to use the letter k for the second argument of (>>=) because k stands for "continuation."

Some examples:

check :: Int -> Maybe Int
check n
  | n < 10 = Just n
  | otherwise = Nothing

halve :: Int -> Maybe Int
halve n
  | even n = Just (n `div` 2)
  | otherwise = Nothing

ex1 :: Maybe Int
ex1 = check 7 >>= halve

ex2 :: Maybe Int
ex2 = check 12 >>= halve

The do notation we’ve learned for working with IO can work with any monad:

ex1' = do
  checked <- check 7
  halve checked

ex2' = do
  checked <- check 12
  halve checked

(Think about what these examples should evaluate to!)

How about a Monad instance for the list constructor []?

instance Monad [] where
  return x = [x]
  xs >>= k = concat (map k xs)

A simple example:

addOneOrTwo :: Int -> [Int]
addOneOrTwo x = [x + 1, x + 2]

ex3 = do
  num <- [10, 20, 30]
  addOneOrTwo num

We can think of the list monad as encoding non-determinism, and then producing all possible values of a computation. Above, num is non-deterministically selected from [10, 20, 30] and then is non-deterministically added to 1 or 2. The result is a list of 6 elements with all possible results.

This non-determinism can be made even more apparent through the use of the function guard, which aborts a computation if its argument isn’t True:

ex4 = do
  num <- [1..20]
  guard (even num)
  guard (num `mod` 3 == 0)
  return num

Here, we can think of choosing num from the range 1 through 20, and then checking if it is even and divisible by 3.

The full type of guard is MonadPlus m => Bool -> m (). MonadPlus is another type class that characterizes monads that have a possibility of failure. These include Maybe and []. guard then takes a boolean value, but produces no useful result. That’s why its return type is m () – no new information comes out from it. But, guard clearly does affect sequencing, so it is still useful.

Monad combinators

One nice thing about the Monad class is that using only return and (>>=) we can build up a lot of nice general combinators for programming with monads.

For example, sequence takes a list of monadic values and produces a single monadic value which collects the results. What this means depends on the particular monad. For example, in the case of Maybe it means that the entire computation succeeds only if all the individual ones do; in the case of IO it means to run all the computations in sequence; and so on.

sequence :: Monad m => [m a] -> m [a]
sequence [] = return []
sequence (ma : mas) =
  ma >>= \a ->
  sequence mas >>= \as ->
  return (a : as)

We'll see several more examples of monad combinators in class and on the homework.

List comprehensions

The monad for lists gives us a new notation for list building that turns out to be quite convenient. Building lists using monad-like operations is so useful that Haskell has a special syntax for it, called list comprehensions. It is best shown by examples:

evensUpTo100 :: [Int]
evensUpTo100 = [n | n <- [1..100], even n]

-- inefficient, but it works
primes :: [Int]
primes = [p | p <- [2..],
              all ((/= 0) . (p `mod`)) [2..p-1] ]

List comprehensions work just like set-builder notation you may have learned in a high-school math class. In a list comprehension, the statements to the right of the | are carried out, in order. A statement with a <- selects an element from a list. Statements without <- are boolean expressions; if the expression is False, then the current choice of elements is thrown out.

There is a straightforward translation between list comprehensions and do notation:

[a | b <- c, d, e, f <- g, h]

is exactly equivalent to

do
  b <- c
  guard d
  guard e
  f <- g
  guard h
  return a

Note that, in the translation, lists aren’t mentioned anywhere! With the GHC language extension MonadComprehensions, you can use list comprehension notation for any monad. But, I’ve never used one for anything other than lists.