25 Dec 2014

As of March 2020, School of Haskell has been switched to read-only mode.

## The Anatomy of a Monad

The goal of programming is to write programs that perform computations. When complexity reaches a certain level, we start decomposing larger computations into smaller ones. The quality of this decomposition is measured by how much coupling there is between the pieces, and how well we -- and the compiler -- can control and verify it. There is overwhelming evidence that hidden couplings are a major source of bugs in both single-threaded and (even more so!) multi-threaded code.

Pure functional programming reduces couplings to the very minimum -- it's just plugging the output of one function to the input of another. However, many traditional notions of computation are expressed in a pseudo-functional way: with procedures that take arguments and return results but also do some non-functional shenanigans. There is a surprisingly large class of such computations that can be turned into pure functions by just modifying their return types.

A monad describes the way of transforming the return type of a particular kind of computation into a fancier monadic type. Functions that return a monadic type are called monadic functions. Each monad provides a mechanism for composing such monadic functions.

As we have seen, the `do` notation simplifies the syntax of composing multiple monadic functions.

Let's illustrate this on a particular type of computation: the non-deterministic computation. It's the kind of computation that, instead of producing a single result, might produce many.

### Non-Deterministic Computations

Think of a chess program that evaluates future moves. It has to anticipate the moves of a non-deterministic opponent. Only one such move will materialize, but all of them have to be taken into account in planning the strategy. The basic routine in such a program would likely be called `move`: it would take a state of the chessboard and return a new state after a move has been made. In order to make two moves, you would compose two such compuatations, etc. But what should `move` return? There are many possible moves in almost every situation. The result of `move` is non-deterministic.

A computation returning a non-deterministic result of type `a` is not a pure function, but it can be made into one by transforming its result type from `a` to a list of `a`. In essence, we create a function that returns all possible results at once. Our chess program would probably have many such non-deterministic functions as well as some regular ones. In order to be able to compose them, we define a monad.

A monadic function returns a monadic type. Let's define the monadic type, `List a`, for non-deterministic computations. For the purpose of illustration, I'm not going to use the built-in list type, since it already is an instance of a monad and we would run into name conflicts. So here's our private version of the list:

``````data List a = Nil | Cons a (List a)
deriving Show``````

Let's think about composing non-deterministic functions. How do we want to calculate the result of two chess moves? If the first move returns a list of options, we should apply the second move to each of the resulting positions in turn. We'll end up with a list of lists of options. If we want a composition of two monadic functions to be another monadic functions, we have to somehow turn this list of lists into a single list. We need to `join` them. With built-in lists we would just use the function `concat`:

``concat :: [[a]] -> [a]``

For our private implementation of `List` we have to code it ourselves:

``````data List a = Nil | Cons a (List a)
deriving Show

join :: List (List a) -> List a
join Nil = Nil
join (Cons xs xss) =  cat xs (join xss)

cat :: List a -> List a -> List a
cat Nil ys = ys
cat (Cons x xs) ys = Cons x (cat xs ys)

l1 = Cons 1 (Cons 2 Nil)
l2 = Cons 3 Nil

main = print \$ join \$ Cons l1 (Cons l2 Nil)``````

Now let's implement monadic bind. In the chess example, I said that we wanted to apply the second `move` to each of the options returned by the first `move`. We know how to do it with regular lists: we just apply `map` to it:

``map :: (a -> b) -> [a] -> [b]``

We can easily implement an analogous function for our `List`, but let's use this opportunity to talk about another important pattern: Type constructors that let you apply functions to their content. Then we'll come back to defining bind.

### Functor

This pattern is called a functor and is defined in Haskell as a type class with one function `fmap`

``````class Functor fr where
fmap :: (a -> b) -> fr a -> fr b``````

Here, `fr` is a type constructor. `fmap` takes a function that transforms `a` into `b` and applies it to the type `fr a`, producing `fr b`. The intuition is that `fmap` reaches inside `f a` to transform its contents. A regular list constructor `[a]` is a `Functor` with `fmap` being just the Prelude `map`. Our own `List` is also a functor:

``````instance Functor List where
fmap f Nil = Nil
fmap f (Cons x xs) = Cons (f x) (fmap f xs)``````

It turns out that every monad is a functor, although, for historical reasons this important information is not encoded into the definition of the `Monad` typeclass. (The reverse though is not true: there are functors that are not monads.)

Let's verify this statement with some of the monads that we've seen so far. Here's the instance of `Functor` for `Maybe`:

``````instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)``````

You can see how `f` gets under the skin of `Maybe`.

This is the `Functor` instance for `State`:

``````instance Functor (State s) where
fmap f act = state \$ \st ->
let (x, st') = runState act st
in (f x, st')``````

Here, the work is a little harder, because you have to create an action that, when the state becomes available, runs the original action and applies the function `f` to its result. State is changed from `st` to `st'` as a side effect of running the first action.

There are some simple functor laws that must be satisfied by every functor's `fmap`. One is that doint the `fmap`with the identity function doesn't change anything:

``fmap id fra = fra``

and the other is that `fmap` preserves function composition:

``fmap (f . g) fra = fmap f (fmap g fra)``

(`id` is the identity function, `id x = x`.)

## List Bind

As I said before, to bind two non-deterministic functions, we have to apply the second one to each element of the list returned by the first one and then collapse the results into a single list using `join`:

``xs >>= k = join (fmap k xs)``

The other monadic function `return` simply produces a one-element list:

``return x = Cons x Nil``

We can test this monad in action:

``````data List a = Nil | Cons a (List a)

instance (Show a) => Show (List a) where
show Nil = ""
show (Cons x xs) = show x ++ ", " ++ show xs

instance Functor List where
fmap f Nil = Nil
fmap f (Cons x xs) = Cons (f x) (fmap f xs)

return x = Cons x Nil
xs >>= k = join \$ fmap k xs

join :: List (List a) -> List a
join Nil = Nil
join (Cons xs xss) =  cat xs (join xss)

cat :: List a -> List a -> List a
cat Nil ys = ys
cat (Cons x xs) ys = Cons x (cat xs ys)

neighbors :: (Num a) => a -> a -> List a
neighbors x dx = Cons (x - dx) (Cons x (Cons (x + dx) Nil))

test = do
x <- neighbors 0 100
y <- neighbors x 1
return y

main = print \$ test``````

Here's an interesting tidbit: the definition of bind in terms of `fmap` and `join` works for every monad `m`:

``ma >>= k = join \$ fmap k ma``

where `join` is defined to have the following signature:

``join :: m (m a) -> m a``

`join` converts the double application of the monadic type constructor into a single application -- it flattens it. In terms of lists, `join` converts a list of lists into a single list.

The opposite is also true: you can define `join` in terms of bind. Remember, bind has a way of extracting a value from its first argument and applying the continuation to it. So if you start with a doubly wrapped argument, bind will extract a singly wrapped center. You can then pick `id` as the continuation, et voila!

``join mma = mma >>= id``

It turns out that mathematicians prefer the definition of a monad as a functor with join and return, whereas programmers prefer to use the one with bind and return. As you can see, it doesn't really matter.

Ex 1. Define `join` for `Maybe` (don't be surprised how simple it is):

``````join :: Maybe (Maybe a) -> Maybe a
join = undefined

test1, test2, test3 :: Maybe (Maybe String)
test1 = Nothing
test2 = Just Nothing
test3 = Just (Just "a little something")

main = do
print \$ join test1
print \$ join test2
print \$ join test3``````

Ex 2. Define functions `listBind` and `listReturn` for regular lists in a way analogous to `>>=` and `return` for our private lists (again, it's pretty simple):

``````import Data.Char

listBind :: ...
listBind = undefined

listReturn :: a -> [a]
listReturn = undefined

neighbors x = [x - 1, x, x + 1]

main = do
print \$ listBind [10, 20, 30] neighbors
print \$ listBind "string" (listReturn . ord)``````

Since we are exploring different ways of representing a monad, there's another one that stresses composability. On several occasions I described a monad as a means to compose functions whose return types are embellished. This can be implemented by binding the result of the first function to the second function. But it can also be done by composing two monadic functions using a special composition operator.

Regular functions are composed right to left using the dot operator, as in `g . f` (pass the result of `f` to `g`). Here's the signature of dot:

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

It takes a function from `b` to `c` and a function from `a` to `b` and composes them into one function that goes straight from `a` to `c`.

Monadic functions can be composed likewise using the so called Kleisli operator, colloquially known as the fish operator: `g <=< f`. The fish is easily defined using bind:

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

Here it is applied to the list monad:

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

f x = [x, x + 1]
g x = [x * x]

test = g <=< f

main = print \$ test 7``````

Ex 3. Implement the other fish operator that composes from left to right:

``````(>=>) :: Monad m => ...
f >=> g = undefined

f x = [x, x + 1]
g x = [x * x]

test = f >=> g

main = print \$ test 7``````

You can also start with the (right or left) fish and define bind in terms of it:

``ma >>= k = (\x -> ma) >=> k``

As you can see, these formulations are equivalent. What's nice about the last one is that it's very easy to express monadic laws in it. Monadic laws (also called axioms) are additional conditions that must be fulfilled by every monad implementation in order to, for instance, make the `do` notation unambiguous. In terms of `return` and the fish operator, these laws simply state that the fish must be associative and that `return` is an identity of fish:

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

Notice an interesting thing: If you replace the fish with `*` and `return` with `1`, you get the laws of multiplication:

``````(a * b) * c = a * (b * c)
1 * a = a
a * 1 = a``````

Consider this a useful mnemonic, but there is actually a nice theory behind it.

Ex 4. Express the fish operator for standard lists considering the non-deterministic function interpretation (the solution is totally unsurprising):

``````import Data.Char

(>=>) :: ...
f >=> g = undefined

modCase c = [toLower c, toUpper c]
camelize = modCase >=> modCase

main = print \$ fmap camelize "Hump"``````

## List Monad and List Comprehension

As I mentioned before, the standard Prelude defines the instance of `Monad` for built-in lists. This lets us use the `do` notation to compose list operations. Here's a function `squares` that squares each element of a list:

``````squares lst = do
x <- lst
return (x * x)

main = print \$ squares [1, 2, 3]``````

We can desugar this code to see how it works internally:

``squares lst = lst >>= \x -> return (x * x)``

Let's expand `>>=` and `return`:

``````squares lst =
concat \$ fmap k lst
where
k = \x -> [x * x]``````

Here, `fmap k` produces a list of one-element lists of squares. This list of lists is then squashed into a single list by `concat`.

At a higher abstraction level, you may think of a `do` block as producing a list. The last `return` shows you how to generate an element of this list. The line `x <- lst` draws an element from `lst`.

Of course, `squares` can be implemented simply by using `fmap`:

``````squares = fmap sq
where sq x = x * x``````

A more interesting example is when you draw from more than one list:

``````pairs l1 l2 = do
x <- l1
y <- l2
return (x, y)

main = print \$ pairs [1, 2, 3] "abc"``````

There is a shortcut notation for `do` blocks that deals with lists called list comprehension. List comprehension is based on a mathematical notation for defining sets. For instance, our first example can be written as:

``[x * x | x <- lst]``

You read it as "a list of `x * x` where `x` is drawn from `lst`." Similarly, the second example reduces to:

``main = print \$ [(x, y) | x <- [1..3], y <- "abc"]``

The clauses to the right of the vertical bar (pronounced "where") are processed in order, just like lines in the `do` block. So, for instance, the second clause may depend on the result of the first one, as in this example that prints ordered pairs of integers:

``````main =
print \$ [(x, y) | x <- [1..4], y <- [x..4]]``````

Moreover, you may filter the elements of lists, which is not easy to accomplish using the `do` notation (there is a `guard` function for that, but it's a bit tricky so I won't explain it here). For instance, in this example we use a guard that only allows Pythagorean triples to pass through:

``````triples =
[(x, y, z) | z <- [1..]
, x <- [1..z]
, y <- [x..z]
, x * x + y * y == z * z]

main = print \$ take 4 triples``````

Notice that we are using an infinite list of `z`s (with no upper bound) so the resulting list is also infinite. However, since Haskell is lazy, the program will terminate after the first 4 results are printed. In an imperative language this list comprehension would probably be expressed as a deeply nested loop.

``````void printNTriples(int n) {
int i = 0;
for (int z = 1;; ++z) {
for (int x = 1; x <= z; ++x) {
for (int y = x; y <= z; ++y){
if (x * x + y * y == z * z){
printf ("(%d, %d, %d)\n", x, y, z);
if (++i == n)
return;
}
}
}
}
}``````

Haskell's use of infinite lists or streams is a powerful idiom for structuring code. In C++ it's very hard to separate the algorithm for generating Pythagorean triples from the algorithm that prints the first n of them. For instance, in the above C++ code the control over the length of the result list happens at the innermost level of the loop. Alternatively, you could define your own lazy C++ iterator, but then you'd end up with another form of inversion of control in the implementation of `operator++` (you'd have to turn the loop inside out). If you're a C++ programmer you should try it.

In the next tutorial we'll go back to the symbolic calculator project and consolidate our monads.

## Exercises

Ex 5. Each card in a deck has a rank between 1 (Ace) and 13 (King) and a Suit (Club, Diamond, Heart, Spade). Write a list comprehension that generates all cards in a deck. Hint: You can encode suit as an enumeration deriving `Show` and `Enum`. The `Enum` type class will let you create ranges like `[Club .. Spade]` (put space before `..` or the parser will be confused).

``````data Suit = ...

data Rank = Rank Int

instance Show Rank where
...

deck = ...

main = print deck``````

Ex 6. What does this function do?

``````f [] = []
f (p:xs) = f [x | x <- xs, x < p]
++   [p]
++ f [x | x <- xs, x >= p]``````