* Practical Monads *

Wherein Monads are explained the way I wish someone had explained them to me. (Warning: incomplete)

Why does Haskell need Monads?
=============================

Let's go back a few years.

Haskell is a wonderfully elegant language. It's pure and lovely and makes language researchers very happy. But Haskell has a problem, and that problem is the Real World.

People would very much like programs to interact with the real world. They would like to write some code which asks the user for their name and then prints it (don't ask me why). But this bothers Haskell, which only has notions of 'pure' values and computations. So something must be done.

Sacrificing the purity of Haskell and allowing side-effects would be one option, and it's the option taken by, for instance, Standard ML. But doing so would cause Haskell to lose much of what makes it great. So we seek another option...


IO
==

A first glimpse of IO
---------------------

Now, some brainy person notices that, rather than writing programs which interact with the real world, we can:

* Write a program, which
* Constructs a computation, which
* Interacts with the real world

This is perhaps a little mindbending. Instead of writing a program which asks someone for their name, we're going to write a program which constructs /another/ program which asks them for their name. The program we write has no side-effects, but the program which our program creates /can/ have side-effects.

"But," you might ask. "What's the point of that? Why not just write our program in a language with side-effects?" The key is that the program we construct is able to call back into our pure program. This allows us to write our programs in two parts: a delicious pure center, and a crunchy thin outer shell with side-effects. The side-effecty part can be kept simple and self-contained, and won't sully the otherwise pure program.


Do notation
-----------

So how do we write a program which constructs a program? We can start with 'primitive' program building-blocks, like a computation which reads some text from the keyboard, and glue them together to make bigger computations (such as one which asks someone for their name and then prints it out). Now, Haskell has no way of saying "do this then that" -- due to lazy evaluation, Haskell will do things when it feels they need doing, and no sooner. So we'll need to invent a mechanism.

We'll tell Haskell to construct a program which will do taskA and then taskB (which are themselves mini programs) as follows:

> do taskA
>    taskB

That seems simple enough. So, we can glue together mini programs into bigger programs. Let's assume we have some primitive actions to read and print strings, and try our ask-for-a-name example.

> askName = do putStrLn "What is your name?"  -- putStrLn will write out a string and a newline.
>              getLine                        -- getLine will read in a line of text
>              putStrLn ("Hello, " ++ 

Uh-oh. We need some way to get the result of 'getLine'. Let's extend our notation a bit...

> askName = do putStrLn "What is your name?"
>              name <- getLine
>              putStrLn ("Hello, " ++ name)

Success! Now, how does Haskell know what the result of our program is (that is, what computation we've produced)? It simply takes the computation called 'main':

> main = askName


What is a computation?
----------------------

Our program is creating a computation called askName out of computations called getLine and putStrLn "...". That's nice, but what /is/ a computation?

We want to be able to treat these computations like any other Haskell value, and pass them to functions and return them from functions and all that jazz. So we can consider defining a data-type, which I'll arbitrarily call IO because that's what we're using it for right now:

> data IO = ...

Let's not worry about what we put on the right-hand side of this definition. Is this enough to get a working system? Looking at getLine, we can see that it's probably not. getLine is a computation which produces a String, and we'd like to be able to tell the type-system that, so that it can detect cases where we misuse getLine:

> do text <- getLine
>    putStrLn (show (text * 42))

Here, we would like a compile-time error -- getLine doesn't produce a number, so multiplying it by 42 is nonsensical. Let's extend our IO type to also tell us what type of value is being computed:

> data IO a = ...

Now, we have:

> getLine :: IO String        -- A computation which produces a String
> putStrLn :: String -> IO () -- A function which creates computations which produce nothing

putStrLn here is interesting. It's a normal Haskell function which takes a String and produces a value of our new IO type, in this case IO (). That is, this function produces computations. We can imagine it being implemented as follows:

> putStrLn [] = putChar '\n'        -- On an empty string, produce a computation which writes a newline
> putStrLn (c:cs) = do putChar c    -- Otherwise, produce a computation which writes the first character, and then...
>                      putStrLn cs  -- Writes out the rest of the string and a newline

You might be wondering what the () in IO () means. () is the name of a type with only one defined value:

> data () = ()

This is merely used as a convenience. We said that each IO computation would have an associated type for the value it produces, but putStrLn doesn't produce a value (it only has side-effects), so we'll pretend it produces a value by making it always return ().


How do we run a computation?
----------------------------

We don't, and we can't. This might seem surprising, but if our Haskell code were able to run our computations, then it could have side-effects, and would not be pure. The only way we can get side-effects to occur is by including them in the computation we create. That means, making them be (directly or indirectly) used by the computation we called 'main'.

If you're using 'GHCi', there is another way to run a computation: you may simply name it at GHCi's prompt, and it will be executed for you.


How do we call pure code?
-------------------------

I promised earlier that we'd be able to call our 'classical' pure Haskell code from our computations. How can we do that?

Well, we've already done it. putStrLn is a normal Haskell function from String to IO (). However, there is one thing which we might want to do. Suppose we want to create a computation which reads a line of text and then computes its length. We obviously can't write "length getLine" because getLine is a computation which we haven't run yet! Can we extend our "do" notation to cope with this too? Let's try:

> do text <- getLine
>    length text

This doesn't quite work, and for a fairly subtle reason. In our previous examples, the last line of a do-block was always of type "IO a" for some "a", but in this case is of type Int. Because "IO a" is just a normal data type like String or Int as far as Haskell is concerned, allowing this notation would introduce an ambiguity. Consider this code ...

> do text <- getLine
>    foo text

This could either mean "produce the computation which reads a line then applies the function 'foo' to it", or it could mean "produce the computation which reads a line, then runs the computation which is returned by foo when applied to that line". To remove this ambiguity, we'll need to say when we want either option. (It's worth noting that there is another option here -- GHCi says "if the value is of type IO a, then run it, otherwise print it" -- but this is not the option which Haskell uses in general, because the ambiguity means that the type of "foo" cannot be inferred).

So let's introduce a function:

> return :: a -> IO a

which we can use with a pure value to construct a computation which does no work and produces that value, and hence remove the ambiguity. With that in hand, we're all set:

> do text <- getLine
>    return (length text)


Summary
-------

So far we've seen:

* Every Haskell program is pure in some kind of mathematical sense, and in particular has no side-effects.
* The goal of every useful Haskell program is to produce a computation which /does/ have side-effects.
* Computations which compute a value of type 'a' (with side effects) have type IO a.
* Computations we create are able to "call back" into the pure world.
* We can't run computations except by making them be part of our 'main' computation.
* We can create new computations by gluing together existing computations inside a 'do' block.

This is enough knowledge to allow you to write useful programs which perform IO. But what does this have to do with Monads? Well, bear with me.


Intermission: 'Maybe' and error handling
========================================

Now, a bit of a diversion. How might we handle failure in Haskell? Let's start with an example.

Suppose I have a list of numbers, 'ns', and a list of indices into that list, 'is'. I want to produce a new list where, for each element of 'is', I use the corresponding element of 'ns'. Like so:

> unsafeElementMap :: [a] -> [Int] -> [a]
> unsafeElementMap is ns = map (\i -> ns !! i) is

Or as a list comprehension,

> unsafeElementMap is ns = [ ns !! i | i <- is ]

But there's a problem with this definition. What happens if 'is' contains an element that's out of range, say, -1? Sadly, our program explodes some time later, when someone looks at that element of the result! This isn't what I wanted. If any of the 'is' are out of range, I'd like to be told politely. Fortunately, Haskell gives us a way of dealing with values we may not be able to compute:

> data Maybe a = Nothing | Just a

This 'Maybe' type is just what we want. I can now proceed as follows:

> elementMap :: [a] -> [Int] -> Maybe [a]
> elementMap (i:is) ns =
>   if i < 0 || i >= length ns
>      then Nothing
>      else case elementMap is ns of
>                Just vs -> Just (ns!!i : vs)
>                Nothing -> Nothing

That works, but it's not that easy to read or understand. Let's see if we can do better. One problem we have is the nasty (!!) operator which is producing an error, and requiring us to check the length of the list. Applying the 'Maybe' trick again gives:

> (!!?) :: [a] -> Int -> Maybe a
> []     !!? _ = Nothing
> (a:_)  !!? 0 = Just a
> (_:as) !!? n = as !!? (n-1)

And this lets us rewrite elementMap as:

> elementMap (i:is) ns =
>   case ns !!? i of
>        Just n -> case elementMap is ns of
>                       Just vs -> Just (n:vs)
>                       Nothing -> Nothing
>        Nothing -> Nothing

This looks a bit better. But it's still not very clear. What we'd like to be able to say is something like, "do this thing, and if it works then do that thing, and fail if either of them fails". That is, we want some way of gluing together possibly-failing actions. Something like:

> elementMap (i:is) ns =
>   try n <- ns !!? i
>       vs <- elementMap is ns
>       produce (n:vs)


This looks awfully familiar
---------------------------

This new notation I just invented looks a lot like the do-notation we used for IO. Instead of inventing a new notation, let's reuse the existing notation:

> elementMap (i:is) ns =
>   do n <- ns !!? i
>      vs <- elementMap is ns
>      return (n:vs)

That looks pretty reasonable now. We can still do better (as we'll see later), but this is good enough for the time being.


How can we generalize this notation?
====================================

We now appear to want the 'do' notation to mean two different things. That doesn't sound good! Fortunately, Haskell has a mechanism for working out what we mean in such cases: type inference. It has plenty of clues:
 * The context in which the result is used,
 * The type of the expression on the right-hand side of a <-, and
 * The type of the result (the last line of the do-notation).

That's good enough for supporting IO and Maybe. But there are plenty more types for which we might want to support do-notation. So let's introduce a type-class, to allow anyone to use do-notation for their types. So...

Let's have a type class
-----------------------

> class DoNotation m where

Here, "m" will be the type (technically type constructor) for which we want 'do' notation to be available, such as Maybe or IO.

What primitives do we want? Well, both of our types had a 'return' function. So let's add that.

>   return :: a -> m a

What else do we need? Some way of joining together two lines would be handy. That is, we want a function:

> bind a b = do x <- a
>               b x

Or as an operator:

> a >>= b = do x <- a
>              b x

So let's add that to our class. (Note, we write this as '>>=' but we'll still pronounce that as 'bind' -- another word for 'attach' or 'glue').

Binding lines together
----------------------

What type does (>>=) have? Well, the left-hand side is "m a" for some a, and the right-hand side looks like "a -> m b". Finally, we're returning the result of applying the right-hand-side function to a value, so the result must be of type "m b". So we add:

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

Is that enough? It turns out that it is - starting from do-notation, we can combine lines together using (>>=) until we have collapsed the entire block. Like so:

> do x <- a
>    y <- b x
>    z <- c x y
>    f x y z

... which we can see should be the same as ...

> do x <- a
>    do y <- b x
>       z <- c x y
>       f x y z

... so it gets translated into ...

> a >>= (\x -> do y <- b x
>                 z <- c x y
>                 f x y z)

... which gets translated into ...

> a >>= (\x -> b x >>= (\y -> do z <- c x y
>                                f x y z))

... which gets translated into ...

> a >>= (\x -> b x >>= (\y -> c x y >>= (\z -> f x y z)))


As a brief aside, we're assuming that:

> do x <- a
>    ...

is the same as

> do x <- a
>    do ...

As a special case of that rule, we can see that, for one-line do-blocks:

> do foo = foo


Lines that don't return values
------------------------------

But what about blocks like this?

> ratherGood = do putStrLn "Food"
>                 putStrLn "Blode"

Well, remember that putStrLn "Food" is of type IO (). So we can translate that into our binding notation as follows:

> ratherGood = do a <- putStrLn "Food"
>                 putStrLn "Blode"

... and then into ...

> ratherGood = putStrLn "Food" >>= (\a -> putStrLn "Blode")

Note that we ignore the value 'a' (which is of type '()') produced by the first action. It turns out that we want to do this quite often, so let's introduce an operator for that:

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

Or equivalently:

> a >> b = a >>= (\x -> b)

This (>>) operator has no need to be part of the "DoNotation" type class since it can be defined in terms of (>>=), but we add it in case it can be implemented more efficiently.


The three rules of 'do'
-----------------------

If we're going to let anyone overload the do-notation for their own purposes, we should introduce some ground rules to make sure that it makes sense.

_Rule 1_

Above, when we were translating (desugaring) 'do' notation into uses of (>>=), we started with the top pair of lines and combined them. We'd want to get the same result if we desugared the bottom two lines first. We arbitrarily said that:

> do a <- x
>    b <- f a
>    g b

is the same as

> do a <- x
>    do b <- f a
>       g b

so let's require that to be the same as this:

> do b <- do a <- x
>            f a
>    g b

In terms of (>>=), this means that:

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

is the same as

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

A mathematician would describe this rule by saying "(>>=) is (sort-of) associative". It's often written more tersely as:

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


_Rules 2 & 3_

Conceptually, 'return' pushes a value into our type (for IO, it turns a pure value into an action which produces that value, and for Maybe it turns a pure value into Just that value). And '<-' pulls a value out of our type. So let's make sure that they are opposites of one another. We'll require:

> do a <- x
>    return a

is the same as

> x

... and ...

> do a <- return x
>    f a

is the same as

> f x


In (>>=) notation, we might write:

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

Or more tersely:

> x >>= return = x
> return x >>= f = f x

A mathematician might say "return is a left and right identity for (>>=)".


Instances of DoNotation
-----------------------

For practice, let's define the instance of DoNotation for Maybe. Start with the easy bit:

> instance DoNotation Maybe where

Now, we want 'return :: a -> Maybe a'. Straightforward:

>   return a = Just a

More difficult is (>>=). From above, we know that we want '(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b'. But (>>=) is just our glue operator for joining together two lines of 'do' notation. Recall this from before:

> elementMap (i:is) ns =
>   do n <- ns
>      vs <- elementMap is ns
>      return (n:vs)

We only want a 2-line fragment of this:

> addN n is ns =
>   do vs <- elementMap is ns
>      return (n:vs)

... which we could also write without 'do' notation as:

> addN n is ns =
>   case elementMap is ns of
>        Just vs -> return (n:vs)
>        Nothing -> Nothing

So, we've manually glued together two lines of 'do' notation. Let's explain to Haskell how we did it.

We know that:

> a >>= f = do x <- a
>              f x

So for Maybe:

>   a >>= f =
>     case a of
>          Just x  -> f x
>          Nothing -> Nothing

That's it. At this point you might like to check that the rules of do-notation are met by these definitions for 'return' and '>>='. I'll go over this later if you want to compare.

We can write this bind operator more nicely using pattern matching as:

>   Just x  >>= f = f x
>   Nothing >>= f = Nothing


Pattern matching
----------------

Pattern matching. That reminds me... our 'do' notation allows this:

> do a <- f
>    g a

But what if we want f to return, say, a tuple? Well, we can allow this:

> do (a, b) <- f
>    g a b

... perhaps with the obvious translation "f >>= (\(a, b) -> g a b)". But what if the pattern match can fail?

> do Left a <- return (Right 42)
>    return (a + 1)

Suppose we're using 'do' notation for Maybe here. If we translated this in the same way, we'd end up passing "Right 42" to a function "\Left a -> ...", which will explode at runtime! That's no good! We're using this notation to avoid that type of explosion! Instead, let's try a different translation:

> do tmp <- return (Right 42)
>    case tmp of
>         Left a -> return (a + 1)
>         _      -> fail "Pattern match failure"

Here, 'fail' is a new function I'm adding to the DoNotation type class:

> fail :: DoNotation m => String -> m a

For convenience, the compiler will provide 'fail' with a string which can be used to explain what went wrong. However, for Maybe, we'll just ignore that and use 'Nothing':

> instance DoNotation Maybe where
>   fail _ = Nothing

And now pattern matches will cause a nice tidy failure returning Nothing rather than exploding the whole program.

Note that many users of Haskell consider 'fail' to be a blemish on Haskell, and would prefer that 'refutable' pattern matching (that is, pattern matching which isn't guaranteed to succeed) required a special type class "DoNotationWithFail" or similar.


Finally, Monads
===============

So far, we've seen a nice notation, and how it makes IO and error handling easy in Haskell. We've seen that this notation is extensible, and that it's defined in terms of two primitive functions '(>>=)' and 'return' (and a third function 'fail' which some people dislike). We've seen that there is a typeclass defining these operations, and that there are certain rules which you must follow when implementing that typeclass. Most of what I've shown is standard Haskell, but I lied to you a bit -- the typeclass in Haskell is not called DoNotation, it's called Monad (this name comes from category theory, a branch of mathematics).

There's plenty more that can be said about monads, but at this point, you have seen all the core ideas. The rest of this document covers various things which can be built on the Monad foundation we've already seen.


Examples of Monads
==================

Lists and list comprehensions
-----------------------------

So far, I've only told you about two monads: IO and Maybe. But there are a lot more which come as standard in Haskell. Let's look next at lists.

Lists are an interesting monad, because they're a bit of a departure from Maybe and IO. In 'Maybe a' and 'IO a', our monadic value conceptually carries with it a single value of type 'a', in some sense. In Maybe, that sense is that either we have a value of type 'a' (Just x) or we have failed (Nothing). In IO, that sense is that we have a computation with side effects that produces an 'a'. However, in a list of 'a's (written as '[a]' or more uniformly as '[] a'), our monadic value carries with it /any number/ of 'a's.

In Maybe, binding a value to a function with (>>=) applies the function to the value within the Maybe (if there is one). In IO, binding a value to a function with (>>=) applies the function to the value, with side-effects in the result happening after side-effects in the value. However, in the list monad, binding a value to a function with (>>=) will apply that function to /every element/ of the list, and collect together all the results. Let's see how this works.


Hopefully, you've already met list comprehensions in Haskell. They look something like this:

> [ (a,b,c) | a <- [1..100], b <- [a..100], c <- [b..100], a*a + b*b == c*c ]

This notation already looks somewhat familiar, and we might wonder whether such list comprehensions could be made to use do-notation. With a bit of rearrangement we can try to write our example like this:

> do a <- [1..100]
>    b <- [a..100]
>    c <- [b..100]
>    a*a + b*b == c*c
>    (a,b,c)

In this case, we can read 'a <- xs' as 'for each value of xs (which we'll call a), do the following stuff...'.

However, there's a problem with this. In order for our translation into '(>>=)' form to make sense, we want all of the lines in our do-block to have the type '[a]' for some a (in the same way that all of the lines in our IO do-block had type 'IO a' for some a). The first three lines are OK, but the last two are not. Let's look at them in turn:

_1) a*a + b*b == c*c_

For now, let's add a function 'guard :: Bool -> [a]' (for some 'a' which we can come back to later). The idea is that this function will give up on the current value (and drop it from the result list) if the Bool is False, and will keep it if the Bool is True. We can look at how to implement that once we've figured out how '(>>=)' will work.

_2) (a,b,c) and return_

Remember that 'do (a,b,c)' is basically the same thing as '(a,b,c)', and that we want

> [ (a,b,c) | <nothing> ] = [ (a,b,c) ]

So what we wanted here is really [(a,b,c)]. We can also observe that, in order for lists to be a monad (and thus usable in do-notation), we'll need:

> return :: a -> [a]

There's an obvious candidate for this:

> return a = [a]

... and this is exactly what we needed.


_bind_

We can now rewrite our example as:

> do a <- [1..100]
>    b <- [a..100]
>    c <- [b..100]
>    guard $ a*a + b*b == c*c
>    return (a,b,c)

To make the above notation work, we'll need an '(>>=)' function, and we know by definition that:

> xs >>= f = do a <- xs
>               f a

But what does that fragment of 'do' notation /mean/? We know that we want:

> do a <- xs      = [ f a | a <- xs ] 
>    return (f a)

Now we can be a little cunning. If lists really are a monad, then they must follow the monad laws (the three rules of do notation given above), so that:

> do a <- xs = do a <- xs     = do a <- xs  = [ b | a <- xs, b <- f a ]
>    f a          do b <- f a      b <- f a
>                    return b      return b

Therefore:

> xs >>= f = [ b | a <- xs, b <- f a ]

So this means, for each element of the list xs, pass it to the function f to build a new list, then return a list of all the values produced by all of those function calls. Like so:

> [x1, x2, x3] >>= f = f x1 ++ f x2 ++ f x3

You might now observe that:

> xs >>= f = concat (map f xs) = concatMap f xs


_fail_

Finally, we need some notion of 'failure' for our monad instance. What should happen if a pattern match fails within the do-notation? Since this is supposed to be alternative syntax for list comprehensions, let's see what happens there:

> [ x | Just x <- [ Just 1, Just 2, Nothing, Just 3 ] ]
>>> [1,2,3]

OK, so we want to skip elements where pattern match failure occurs. Remember that:

> do Just x <- xs
>    f x

is translated into:

> do tmp <- xs
>    case tmp of
>         Just x -> f x
>         _      -> fail "Pattern match failure"

For convenience, I'll pull out a function:

> g (Just x) = f x
> g _        = fail "Pattern match failure"

Leaving:

> do tmp <- xs
>    g tmp

Which is the same as:

> xs >>= g = [ a | x <- xs; a <- g x ]

Or in pseudocode:

> [x1, x2, ..., xn] >>= g = g x1 ++ g x2 ++ ... ++ g xn

Now, when the value given to g is 'Just x', this will work fine. When the value given to g is 'Nothing', we want no elements in our resulting list. Therefore:

> fail _ = []


_The Monad instance for []_

Putting it all together, we get:

> instance Monad [] where
>   fail _   = []
>   return a = [a]
>   xs >>= f = concatMap f xs

To emphasize that this is just another way of writing list comprehensions, we could equivalently write:

> instance Monad [] where
>   fail _   = [ a | Just a <- [Nothing] ]
>   return a = [ a | True ]
>   xs >>= f = [ a | x <- xs, a <- f x ]

We should at this point check that the monad laws hold. You can take this on trust, or check below.


_guard and MonadPlus_

Let's return to our example, and its use of 'guard'. We said that if its argument is True, it should allow the computation to continue, and if it's False, it should interrupt it. Put another way, if the argument is True, we want a one-element list, and if it's False, we want a zero-element list. Like so:

> guard :: Bool -> [()]
> guard True  = [()]
> guard False = []

You might notice that the above definition can be made to work for /all/ monads (not just lists) by using return and fail instead of [()] and []. However, this isn't quite how 'guard' is defined in Haskell. If you recall, there is something of a holy war over whether 'fail' should be part of the Monad typeclass or not. To this end, another typeclass exists, with a slightly different form of 'fail':

> class Monad m => MonadPlus m where
>   mzero :: m a
>   mplus :: m a -> m a -> m a

Here, mzero represents some kind of failure for the monad. mplus allows us to take two monadic values, either of which might be a failure, and combine them together to produce a successful result if we can.

It's conventional that monads which have a useful implementation of 'fail' are also made instances of MonadPlus (with mzero = fail ""). Unfortunately, this typeclass also has a method 'mplus' (which is obliged to follow certain rules, and which it isn't possible to define for all monads), so it's not ideal for representing monads which have sensible implementations of fail.

The type of guard could therefore be either the liberal "guard :: Monad m => Bool -> m ()", or the more restrictive "guard :: MonadPlus m => Bool -> m ()". You'll recall that for pattern matching, the more liberal option was taken (using fail). Sadly, Haskell is inconsistent on this point, and guard is defined as:

> guard :: MonadPlus m => Bool -> m ()
> guard True  = return ()
> guard False = mzero

In any case, here's an example of an implementation of MonadPlus for Maybe:

> instance MonadPlus Maybe where
>   mzero = Nothing
>   Nothing `mplus` x = x
>   Just x `mplus` y = Just x

Note that 'Just x `mplus` Just y' will produce 'Just x'. Unfortunately, Haskell doesn't provide guidance on which value should be used in this case -- the decision is arbitrary, but you need to remember that mplus on Maybe is left-biased.


Either and Error
----------------

Let's go back to the Maybe monad for a second, and think about what it means. The type 'Maybe a' contains two sorts of values: successes (Just x) and failures (Nothing). This is a pretty convenient and simple way of doing error handling, but in more advanced cases, it seems to be lacking something. Specifically, it'd be nice if we had some way of saying /what/ went wrong, rather than just saying that /something/ went wrong.

So how can we do that? Well, we want to extend our 'Nothing' value with some kind of error code. That'd give us a type like this:

> data MaybeWithErrorCode a = Nothing ErrorCode | Just a

We want to allow the user of this type to decide what sorts of error codes they want to use, so let's add a parameter for that too:

> data MaybeWithErrorCode e a = Nothing e | Just a

Now, this type is isomorphic to (a fancy way of saying 'structurally the same as') an existing type in the Haskell prelude:

> data Either e a = Left e | Right a

Can we make it a monad in the same way we made Maybe a monad? Let's try.

As always, we want:

> x >>= f = do v <- x
>              f v

Now, if x is an error, we want to propagate that error, and not call f:

> Left e >>= f = Left e

But if x is a success, we want to pass the value on to f:

> Right v >>= f = f v

Finally, we want 'return' to produce a successful value:

> return x = Right x

So our instance looks like this:

> instance Monad (Either e) where
>   return x = Right x
>   Left e >>= f = Left e
>   Right v >>= f = f v

And we're done. We can check the monad laws hold (they do) and start using this in do-notation.

But... wait. We forgot 'fail' again. This time, we can do something with the error message we get given:

> fail error = Left (... somehow convert error into the error code type ...)

Uh-oh. We don't know how to convert the String we get as an error from GHC into the user's error code type (which could be any type at all). All we can do is ask the user of the monad to tell us what to do here. And for that we're going to need another type class.

> class Error e where
>   strMsg :: String -> e

Right. Now we're all set.

> instance Error e => Monad (Either e) where
>   fail error = Left (strMsg error)
>   -- ... same as before

Hooray!


Since we have a meaningful implementation of 'fail', we ought to provide a MonadPlus instance too. Let's do that:

> instance MonadPlus (Either e) where
>   mzero = noMsg
>   Left a `mplus` b = b
>   Right a `mplus` b = Right a

There are a couple of notable things here:

Firstly, we can't really use strMsg, because we don't have a specific message, so we add another method to the Error typeclass, noMsg :: Error e => e.

Secondly, as with Maybe, this will return the left-most successful value -- but if both values fail, it'll return the rightmost error. This decision is essentially arbitrary, but makes some sense: if we had a sequence of options and we wanted to find the left-most one which works, we would put our 'catch-all' option at the end, and that's the option we would want to collect errors from.

Reader and (->) a
-----------------

State
-----

ST
--

Cont
----

STM
---

Structuring your code with monads
---------------------------------


Functors and other animals
==========================

'liftM'
-------

fmap

Monads as Applicative Functors
------------------------------

Why, what, how. <$> and <*> as generalized application.

return and ap as pure and <*>

Applicatives as intersections; Applicatives as joins.

There aren't many common examples of Applicatives which aren't Monads, but they give us nicer syntax.

Utility functions
=================

mapM, mapM_, sequence, ...
(look through Control.Monad)
(relate back to applicative functors)

More on Do Notation
===================

'let' in 'do'
-------------

Rules for 'fail'
----------------

We could have chosen to use fail to implement pattern matching in a different way:

> do tmp <- return (Right 42)
>    a <- case tmp of
>              Left a -> return a
>              _      -> fail "Pattern match failure"
>    return (a + 1)

We would like the this and the previous formulation to behave the same way. Fortunately, using the existing rules, we know that this new formulation is equivalent to:

> do tmp <- return (Right 42)
>    case tmp of
>         Left a -> do a <- return a
>                      return (a + 1)
>         _ -> do a <- fail "Pattern match failure"
>                 return (a + 1)

Which is equivalent to:

> do tmp <- return (Right 42)
>    case tmp of
>         Left a -> return (a + 1)
>         _ -> fail "Pattern match failure" >>= (\a -> return (a+1))


In order for this to be equivalent to our original formulation, we need to know that:

> fail str

is the same as

> fail str >>= x

for all values of x. This is not a monad law, but is obeyed by most (all?) of the standard Haskell monads. It is, however, a law for mzero.


Proving the monad laws:
=======================

Maybe and the monad laws
------------------------


Lists and the monad laws
------------------------

> xs >>= return
> = [ a | x <- xs, a <- return x ]
> = [ a | x <- xs, a <- [x] ]
> = [ x | x <- xs ]
> = xs

> return x >>= f
> = [ b | a <- return x, b <- f a ]
> = [ b | a <- [x], b <- f a ]
> = [ b | b <- f x ]
> = f x

> (x >>= f) >>= g
> = [ b | a <- x, b <- f a ] >>= g
> = [ d | c <- [ b | a <- x, b <- f a ], d <- g c ]
> = [ d | a <- x, b <- f a, d <- g b ]
> = [ d | a <- x, d <- [ d | b <- f a, d <- g b ] ]
> = [ d | a <- x, d <- f a >>= g ]
> = [ d | a <- x, d <- (\a -> f a >>= g) a ]
> = x >>= (\a -> f a >>= g)

So it looks like we're OK. For the curious, here's a more rigorous proof of that last law:

> (x >>= f) >>= g
> = concatMap g (concatMap f x)                     -- x >>= f = concatMap f x
> = concat . map g $ (concat . map f $ x)           -- concatMap f = concat . map f
> = concat . map g . concat . map f $ x             -- a $ (b $ c) = a . b $ c
> = concat . concat . map (map g) . map f $ x       -- map g . concat = concat . map (map g)
> = concat . map concat . map (map g) . map f $ x   -- concat . concat = concat . map concat
> = concat . map (concat . map g . f) $ x           -- map a . map b = map (a . b)
> = concat . map (\a -> concat . map g . f $ a) $ x -- f = \a -> f $ a
> = concatMap (\a -> concatMap g (f a)) x           -- concat . map = concatMap
> = x >>= (\a -> f a >>= g)                         -- x >>= f = concatMap f x


Monad Transformers
==================

What, how, liftIO and lift.