# Yet Another Monad Tutorial (part 4: The Maybe and List Monads)

In the previous articles in this series, I covered the conceptual basis of monads, but the discussion was pretty abstract. Now that (I hope) you have a pretty good idea of what monads are and what they're for, it's time to get into the nitty-gritty details of how to actually derive the definitions of specific monads. That means that we are going to have to define the correct instances of the type class `Monad` for the various notions of computation we talked about previously. In our derivations, we will use our understanding of how monadic composition should work in each particular case to give us the definition of monadic apply (the `>>=` operator), and we'll use the monad laws to give us the definition of `return`.

## The `Maybe` monad

The `Maybe` monad is often the first monad shown to new Haskell programmers in tutorials, because it's very simple to use, to implement, and to understand. To start with, let's look at the definition of the `Maybe` data type:

``````  data Maybe a = Nothing | Just a
``````

This states that `Maybe` is a type constructor that acts on a particular type `a` to give a (concrete) data type. We usually describe this by saying that `Maybe` is a "polymorphic" data type, but the meaning is the same. So if `a` was `Int`, we'd have

``````  data Maybe Int = Nothing | Just Int
``````

except that we don't have to define this directly, as the one definition given above suffices for all types.

A value of type `Maybe a` is either there or not there; if it's `Nothing`, it's "not there" and if it's `Just x` for some value `x`, it's "just" the value `x`. One way to think of this is as a container that either has zero or one elements. (Remember that I said previously that monadic values were sometimes described, misleadingly, as containers. This is a case in point.)

The `Maybe` polymorphic type is useful because we can use it to model a kind of "extended function" which can either produce a value as its output or fail to produce any output (i.e. a function that can fail). This can be written as follows:

``````  f :: a -> Maybe b
``````

A function `f` of this type takes in an input value of type `a`, and either returns `Nothing` (which indicates failure) or a value `Just x` where `x` has type `b`. Functions like `f` will be the ones that will be used in the `Maybe` monad, and composing two functions of this kind will look like this:

``````  f :: a -> Maybe b   -- assume it's defined elsewhere
g :: b -> Maybe c   -- assume it's defined elsewhere

h :: a -> Maybe c   -- monadic composition of f and g
h = f >=> g         -- recall: >=> is the monadic composition operator
``````

We said that all monads must be type constructors. `Maybe` is a type constructor, so it qualifies in that sense. But in order to make `Maybe` into a monad, we have to make it an instance of the type class `Monad`, which means that we have to fill out this definition:

``````  instance Monad Maybe where
(>>=)  = {- definition of >>= for Maybe -}
return = {- definition of return for Maybe -}
``````

How do we define `(>>=)` and `return` for `Maybe`?

First, let's write a skeleton definition for the `>>=` operator, covering the two possible cases of a left operand of type `Maybe a`:

``````  Nothing >>= f  =  {- to be defined -}
Just x  >>= f  =  {- to be defined -}
``````

where `x` has type `a`. It would also be legal to write the left-hand side of this definition as:

``````  (>>=) Nothing  f  =  {- to be defined -}
(>>=) (Just x) f  =  {- to be defined -}
``````

but it looks better if we define it the way we use it, as an operator, and Haskell allows us to do this.

To complete this definition, consider how we want monadic composition to work in the `Maybe` monad. Let's take our example above with `f` and `g` composing monadically to make `h`:

``````  f :: a -> Maybe b
g :: b -> Maybe c
h :: a -> Maybe c
h = f >=> g
``````

If we pass an argument to `f` and it returns `Nothing` (i.e. it fails), then what should `h` return on the same output?

``````  f x = Nothing
h x = (f >=> g) x = ???
``````

It seems apparent that if `f x` is `Nothing`, `h x` must also be `Nothing`, because if the first function (`f`) in the definition of `h` fails to produce an output, then `h` as a whole must also fail to produce an output. The only way `h` could produce an output is if `f` produced an output (call it `y`), passed it to `g`, and `g y` also produced an output. If either `f` or `g` fails, then `h` fails too i.e. `h x` will evaluate to `Nothing`.

Putting this into our definition of `h`, we have:

`````` h = f >=> g
h = \x -> (f x >>= g)  -- equivalent (from the definition of >=>)
h x = f x >>= g        -- equivalent
-- assume f x == Nothing
h x = (Nothing >>= g)
= Nothing
-- therefore:
Nothing >>= g = Nothing
``````

So we know how the `(>>=)` operator will work with an input of `Nothing` — it will just return `Nothing`:

``````  Nothing >>= f  =  Nothing
Just x  >>= f  =  {- to be defined -}
``````

Note that I changed `g` to `f` here, which is fine because the name of the function doesn't matter in the definition. In fact, where possible we leave off the name of the function entirely and use the `_` wildcard operator as follows:

``````  Nothing >>= _  =  Nothing
``````

We can't do this for the second equation because we'll need the function `f` in the definition.

Now let's look at the other case. If `f x` does not fail, it will produce an output of the form `Just y` for some result value `y`. We need to "unpack" a value from `Just y` to get the value `y`, which we will give as the argument to `g`, and `g y` will be what `h x` evaluates to:

`````` h = f >=> g
h = \x -> (f x >>= g)  -- equivalent (from the definition of >=>)
h x = f x >>= g        -- equivalent
-- assume f x == Just y
h x = (Just y >>= g)
= g y
``````

This gives us the second part of our definition:

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

Note that I changed `y` to `x` and `g` to `f` in the definition. Again, the variable and function names don't matter as long as you're consistent.

That completes the definition of the `>>=` operator for the `Maybe` monad. Now we need to define the `return` function for this monad:

``````  return x  =  ???
``````

for an arbitrary value `x`. What possibilities have we got? We could just say that

``````  return x  =  Nothing
``````

for any `x`. If this were the case, however, we would violate our monad laws:

``````  return x >>= f  ==  f x
Nothing >>=  f  ==  f x
Nothing         ==  f x   -- WRONG!
``````

Since we can assume that at least some `f x` values are not `Nothing` (for instance, consider the monadic function `f x = Just x`), this can't be correct. The obvious alternative is:

``````  return x  =  Just x
``````

``````  return x >>= f
= (Just x) >>= f   -- definition of return for Maybe monad
= f x              -- definition of >>= for Maybe monad
-- correct according to monad law 1

Just x >>= return
= return x         -- definition of >>= for Maybe monad
= Just x           -- definition of return for Maybe monad
-- correct according to monad law 2

Nothing >>= return
= Nothing          -- definition of >>= for Maybe monad
-- correct according to monad law 2
``````

This works, so let's use it. The complete definition of the `Maybe` monad is thus:

``````  instance Monad Maybe where
return x  =  Just x

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

Woo hoo! We've just derived our first monad!

Just to be on the safe side, let's check that our definition obeys monad law 3, which is:

``````  (mv >>= f) >>= g    ==    mv >>= (\x -> (f x >>= g))
``````

First let's check that it's correct when `mv` is `Nothing`:

``````  (Nothing >>= f) >>= g             -- left hand side
= Nothing >>= g                 -- definition of >>=
= Nothing                       -- definition of >>=

Nothing >>= (\x -> (f x >>= g))   -- right hand side
= Nothing                       -- definition of >>=
``````

OK, that checks out. Now let's see if it works when `mv` is `Just v` for some value `v`:

``````  ((Just v) >>= f) >>= g            -- left hand side
= f v >>= g                     -- definition of >>=

(Just v) >>= (\x -> (f x >>= g))  -- right hand side
= (\x -> (f x >>= g)) v         -- definition of >>=
= f v >>= g                     -- normal function application (beta reduction)
``````

so this checks out too. So it works! This is the correct definition of the `Maybe` monad! And the audience goes wild!

What's the significance of this? It means that we can compose a bunch of monadic functions in the `Maybe` monad easily. And why, you will certainly be asking yourself, is that important? It's not hard to imagine having a bunch of `Maybe` monadic functions i.e. functions that can fail. Let's say that they all have type `Int -> Maybe Int`. Here are three such functions:

``````  f :: Int -> Maybe Int
f x = if x `mod` 2 == 0 then Nothing else Just (2 * x)

g :: Int -> Maybe Int
g x = if x `mod` 3 == 0 then Nothing else Just (3 * x)

h :: Int -> Maybe Int
h x = if x `mod` 5 == 0 then Nothing else Just (5 * x)
``````

We'd like to compose them to get a final function:

``````  k :: Int -> Maybe Int
``````

which is the result of applying `f`, then `g`, then `h` one after another, with `Nothing` returned if any of them failed. All this does is multiply the input number by 30 unless the number is a multiple of 2, 3, or 5 (in which case it fails i.e. returns `Nothing`).

If you've followed the previous discussion it should be clear that you can define `k` using monadic composition as follows:

``````  k = f >=> g >=> h
``````

Or, if you want to use the `>>=` operator instead:

``````  k x = f x >>= g >>= h
``````

Or, if you like the `do` notation:

``````  k x = do y <- f x
z <- g y
h z
``````

Any way you slice it, though, it's pretty simple.

Now, it's perfectly possible to define `h` without using monads at all. It looks like this:

``````  k x = case f x of
Nothing -> Nothing
Just y  -> case g y of
Nothing -> Nothing
Just z  -> h z
``````

This shows why the `Maybe` monad is important: it drastically cuts down on the boilerplate code we have to write to chain `Maybe`-producing functions together. Imagine how grungy the non-monadic code would be if there were ten `Maybe` monadic functions in a row being chained together — it would be indented so far to the left that you wouldn't be able to read it, and the overall structure of the computation would be lost in a maze of `case` statements. But with monads, you could write it like this:

``````    f11 = f1 >=> f2 >=> f3 >=> f4 >=> f5 >=> f6 >=> f7 >=> f8 >=> f9 >=> f10
``````

or (using `>>=`):

``````    f11 x = f1 x >>= f2 >>= f3 >>= f4 >>= f5 >>= f6 >>= f7 >>= f8 >>= f9 >>= f10
``````

The `Maybe` monad is very useful for illustrating basic concepts, but it may be confusing in one sense: many people mistakenly believe that the only reason for having monads in Haskell is to handle non-functional computations i.e. ones that do (file or terminal) I/O, alter global variables, etc. And yet, here I showed you a monadic computation which can be done perfectly well without monads. In this case, monads are not essential; they're just very convenient. And that's why I said that even though the original reason for adding monads to Haskell had to do with dealing with inherently non-functional kinds of computations (like computations involving I/O), they turned out to have a far greater applicability. That's why they're neat.

Now, on to our next monad.

If you liked the `Maybe` monad, you're going to love the list monad ;-) We're going to be filling in this instance definition:

``````  instance Monad [] where
(>>=)  = {- definition of >>= for lists -}
return = {- definition of return for lists -}
``````

Note that we use the empty list `[]` to represent the list type constructor. This is a bit of a hack (lists have special syntactic support in Haskell). Whatever.

As with all monads, the first task is to be clear about what the monad's monadic function represents. For the list monad, a monadic function `f` looks like this:

``````  f :: a -> [b]
``````

(where, of course, the notation `[b]` means "list of `b`"). Recall that the generic definition of a monadic function is this:

``````  f :: a -> m b
``````

for some monad `m` which has to be a type constructor. Lists are a plausible candidate for a monad because "list of" is a type constructor (even though the syntax is hard-wired into Haskell); if we wanted to, we could even define a list datatype ourselves:

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

and then the monadic function would look like this:

``````  f :: a -> List b
``````

We'll stick to the standard list syntax from now on.

What do functions of this sort represent? The normal way of thinking about them is that they take in an input value of type `a`, and produce a bunch of output values of type `b`, collected in one convenient container (the list). (Here again, we have a monad that seems to be a container.) A different way of thinking about functions of this type is that they represent functions with multiple return values i.e. functions which can somehow return a bunch of different values "all at once". (I don't want to say "in parallel" because that implies simultaneous processing which isn't going on here.) The multiple return values are just the elements of the list. This turns out to be a useful perspective when you have multiple functions of this type, for instance:

``````  f :: Int -> [Int]
g :: Int -> [Int]
``````

Here, `f` and `g` both take in a single `Int` as an argument and return a bunch of `Int`s as results. What if we wanted to take every result from `f` and apply `g` individually to each result, collecting all the results together? It would be great if we could do this directly, without having to unpack every element from the list of results that `f` returns and apply `g` to each one. This is what the list monad will allow us to do.

Let's flesh this out a bit with some example functions:

``````  f :: Int -> [Int]
f x = [x-1, x, x+1]

g :: Int -> [Int]
g x = [-x, x]
``````

How would we "compose" these two functions? `f x` returns a list, so to apply `g` to each element of the list we will need the `map` function:

``````  f 10   -->  [9, 10, 11]
map g (f 10)  -->  [[-9, 9], [-10, 10], [-11, 11]]
``````

This new result may be interesting, but it can't be the composition of `f` and `g` because it doesn't have the same type (it's a list of lists of `Int`s, not a list of `Int`s). To turn it into a simple list of `Int`s, we can flatten the list of lists using the `concat` function (which just concatenates a list of lists into a single list):

``````  -- N.B. concat has the type [[a]] -> [a]
concat (map g (f 10))  -->  [-9, 9, -10, 10, -11, 11]
``````

What this result represents is the collection of all the results obtained by applying `f` to an integer input and then applying `g` to one of the results. If you think of `f` and `g` as functions which produce multiple results "all at once", then this result is just the collection of all possible results of applying `f` and then `g`. Diagrammatically, we can represent this as:

``````                  g   |  -9
|  9 ----> |
|          |   9
|
f   |      g   | -10
10 ----> | 10 ----> |
|          |  10
|
|      g   | -11
| 11 ----> |
|  11
``````

This shows that the composition of `f` and `g` is the collection of all paths through the `f` and `g` functions.

Interestingly enough, we've just determined what the `>>=` operator has to be for the list monad! It's defined as follows:

``````  -- mv :: [a]
-- g  :: a -> [b]
mv >>= g = concat (map g mv)
``````

where `mv` is a monadic value in the list monad (which is just a list of values of type `a`). In the previous example, `mv` is just the result of evaluating ```f 10``` and `g` is as it was before. This definition even works if `mv` is the empty list `[]`, since mapping a function over the empty list just returns the empty list, and `concat` applied to the empty list returns the empty list as well. So the definition of the `>>=` operator for this monad is very simple.

[Note for GHC fans: The GHC Haskell compiler actually implements `>>=` for the list monad in a slightly different way which is (I believe) more efficient but which gives the same results.]

How would we define `return` in this monad? Let's think of the list monadic value as an "action" returning various values. Let's also recall that `return` should be the equivalent of the identity function in any given monad. What would be the equivalent of the identity function in the list monad? It would take an input value and return an "action" which simply returns that value when "executed". So we know that `return` can't simply return the empty list, for instance. A reasonable possibility is to define `return` as follows:

``````  return :: a -> [b]
return x = [x]
``````

In other words, `return` just creates a list with a single value. Let's see if this is plausible by seeing if it obeys the monad laws:

``````  -- f :: a -> [b]
-- x :: a
return x >>= f  =  concat (map f (return x))   -- definition of >>=
=  concat (map f [x])          -- definition of return
=  concat [f x]                -- definition of map
=  f x                         -- definition of concat
-- correct according to monad law 1

-- mv :: [a]
mv >>= return   =  concat (map return mv)      -- definition of >>=
=  concat (map (\x -> [x]) mv) -- definition of return
-- Two cases:
-- Case 1:  mv == []
=  concat (map (\x -> [x]) []) -- definition of mv
=  concat []                   -- definition of map
=  []                          -- definition of concat
=  mv                          -- definition of mv
-- Case 2:  mv == [v1, v2, ...]
=  concat (map (\x -> [x]) [v1, v2, ...])  -- definition of mv
=  concat [[v1], [v2], ...]    -- definition of map
=  [v1, v2, ...]               -- definition of concat
=  mv                          -- definition of mv
-- correct according to monad law 2
``````

OK, this works. You might want to try other possible definitions for `return` in the list monad (e.g. where `return` returns a list which contains 0, 2, 3, or an infinite number of copies of its argument), and find out why they violate the monad laws. This is a good way to get practice using the monad laws.

To prove that our list monad is really a monad, we still have to show that monad law 3 is obeyed. This will be a lot harder, but let's do it anyway. It'll turn out to be easier to do if we use the nice version of monad law 3 (the one involving monadic composition). To start, we need to define monadic composition in the list monad:

``````  -- Monad law 3 (nice version):
(f >=> g) >=> h  =  f >=> (g >=> h)
-- By definition:
f >=> g = \x -> f x >>= g
-- In the list monad, using the definition of >>= for lists:
f >=> g = \x -> concat (map g (f x))
-- Using the composition operator (.), this can be written as:
f >=> g = concat . map g . f
``````

In addition, I'll be using several identities involving `map` and `concat` applied to lists. You should just take these on faith for now, though I'll show how to derive them below.

``````  -- equation 1:
map (f . g)  =  map f . map g
-- equation 2:
map f . concat =  concat . map (map f)
-- equation 3:
concat . concat  =  concat . map concat
``````

As I mentioned above, `.` refers to the (pure) function composition operator. It has lower precedence than function application (via concatenation), so an expression like `map f . map g` actually means `(map f) . (map g)`. Haskell programmers usually prefer to leave out unnecessary parentheses when possible. It's also important to note that e.g. `map f` is a function even though `map` normally takes two arguments (a function and a list to map the function over). If you recall what I said about currying previously, then you'll understand that `map f` is a function which takes a list as its only argument and returns a new list, which what you get when you apply the function `f` to all the elements of the original list and collect the results into a new list. We'll be using currying a lot below.

Given all that, here's the derivation:

``````  (f >=> g) >=> h
= (concat . map g . f) >=> h                     -- definition of >=>
= concat . map h . (concat . map g . f)          -- definition of >=>
= concat . map h . concat . map g . f            -- remove unnecessary parentheses

f >=> (g >=> h)
= f >=> (concat . map h . g)                     -- definition of >=>
= concat . map (concat . map h . g) . f          -- definition of >=>
= concat . map ((concat . map h) . g) . f        -- equivalent
= concat . (map (concat . map h)) . (map g) . f  -- equation 1
= concat . map (concat . map h) . map g . f      -- remove unnecessary parentheses
= concat . map concat . map (map h) . map g . f  -- equation 1
``````

So we need to show that:

``````  concat . map h . concat . map g . f  =  concat . map concat . map (map h) . map g . f
``````

which will be true if we can show that:

``````  concat . map h . concat  =  concat . map concat . map (map h)
``````

Let's do that:

``````  -- add parentheses for clarity:
concat . (map h . concat) = concat . map concat . map (map h)
-- use equation 2:
concat . concat . map (map h)  =  concat . map concat . map (map h)
(concat . concat) . map (map h)  =  concat . map concat . map (map h)
-- use equation 3:
concat . map concat . map (map h)  =  concat . map concat . map (map h)
``````

and we're done. Whew! In fact, Haskell programmers very rarely do derivations of this kind, but they are necessary to show that a purported monad really is a monad.

#### ASIDE: Deriving the `map`/`concat` identities (equations 1, 2, and 3)

Preliminaries:

To prove these identities, we will need to first prove a few simpler ones (math is hard!). They are:

``````  -- Equation 4:
concat (x:xs) = x ++ concat xs
-- Equation 5:
concat (x ++ y) = concat x ++ concat y
-- Equation 6:
map f (x ++ y) = map f x ++ map f y
``````

Equation 4 follows from the definition of `concat`. Equation 5 is easily proved by induction on the length of `x` and using equation 4:

``````  -- base case: x is an empty list
concat ([] ++ y) = concat [] ++ concat y
concat y = [] ++ concat y  -- definition of concat []
concat y = concat y        -- definition of ++
-- OK

-- inductive case: x is non-empty; call its parts x1 (head) and xs (tail)
concat ((x1:xs) ++ y)
= concat (x1 : (xs ++ y))      -- definition of ++
= x1 ++ concat (xs ++ y)       -- equation 4
= x1 ++ concat xs ++ concat y  -- inductive hypothesis

concat (x1:xs) ++ concat y
= x1 ++ concat xs ++ concat y  -- equation 4
-- OK, so Q.E.D.
``````

Equation 6 is proved similarly:

``````  -- base case: x is an empty list
map f ([] ++ y) = map f [] ++ map f y
map f y = [] ++ map f y
map f y = map f y
-- OK

-- inductive case: x is non-empty; call its parts x1 (head) and xs (tail)
map f (x ++ y)
= map f ((x1:xs) ++ y)
= map f (x1 : (xs ++ y))            -- definition of ++
= f x1 : map f (xs ++ y)            -- definition of map
= f x1 : (map f xs ++ map f y)      -- inductive hypothesis
= (f x1 : map f xs) ++ map f y      -- definition of ++
= map f (x1:xs) ++ map f y          -- definition of map
= map f x ++ map f y                -- definition of x
-- OK, so Q.E.D.
``````

With that out of the way, let's get to the proofs of equations 1, 2, and 3.

Equation 1:

``````   map (f . g)  =  map f . map g
``````

Use induction on the length of the implicit list argument on both sides, as well as the definition of `map`:

``````   -- base case: empty list
map (f . g) [] = []
(map f . map g) [] = map f (map g []) = map f [] = []
-- OK

-- inductive case: non-empty list
map (f . g) (x:xs)
= ((f . g) x) : (map (f . g) xs)        -- definition of map
= (f (g x)) : (map (f . g) xs)          -- definition of .
(map f . map g) (x:xs)
= map f (map g (x:xs))                  -- definition of .
= map f ((g x) : (map g xs))            -- definition of map
= (f (g x)) : (map f (map g xs))        -- definition of map
= (f (g x)) : ((map f . map g) xs)      -- definition of .
= (f (g x)) : (map (f . g) xs)          -- inductive hypothesis
-- OK, so Q.E.D.
``````

Equation 2:

``````  map f . concat =  concat . map (map f)
``````

Use induction on the length of the list argument:

``````  -- base case: empty list
(map f . concat) [] = map f (concat []) = map f [] = []
(concat . map (map f)) [] = concat (map (map f) []) = concat [] = []
-- OK

-- inductive case: non-empty list
(map f . concat) (x:xs)
= map f (concat (x:xs))                   -- definition of .
= map f (x ++ concat xs)                  -- equation 4
= map f x ++ (map f (concat xs))          -- equation 6
= map f x ++ ((map f . concat) xs)        -- definition of .
= map f x ++ ((concat . map (map f)) xs)  -- inductive hypothesis
= map f x ++ concat (map (map f) xs)      -- definition of .

(concat . map (map f)) (x:xs)
= concat (map (map f) (x:xs))             -- definition of .
= concat (map f x : map (map f) xs)       -- definition of map
= map f x ++ concat (map (map f) xs)      -- equation 4
-- OK, so Q.E.D.
``````

Equation 3:

``````  concat . concat  =  concat . map concat
``````

As usual, use induction on the length of the list argument:

``````  -- base case: empty list
(concat . concat) [] = concat (concat []) = concat [] = []
(concat . map concat) [] = concat (map concat []) = concat [] = []
-- OK

-- inductive case: non-empty list
(concat . concat) (x:xs)
= concat (concat (x:xs))                 -- definition of .
= concat (x ++ concat xs)                -- equation 4
= concat x ++ concat (concat xs)         -- equation 5

(concat . map concat) (x:xs)
= concat (map concat (x:xs))             -- definition of .
= concat (concat x : map concat xs)      -- definition of map
= concat x ++ concat (map concat xs)     -- equation 4
= concat x ++ (concat . map concat) xs   -- definition of .
= concat x ++ (concat . concat) xs       -- inductive hypothesis
= concat x ++ concat (concat xs)         -- definition of .
-- OK, so Q.E.D.
``````

By now, I hope you're fully convinced that the list monad is in fact a monad ;-)

A much more interesting question, of course, is this: what can we do with the list monad that was hard to do before? Here's a simple example: find all pairs of numbers between 1 and 6 that sum to the number 7 (the numbers might represent e.g. dice rolls). With the list monad, this is trivial:

``````  -- Using do-notation:
do n1 <- [1..6]
n2 <- [1..6]
if n1 + n2 == 7 then return (n1, n2) else []
-- Result: [(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)]
``````

This can also be written without the `do`-notation, though it's less clear:

``````  [1..6] >>= \n1 ->
[1..6] >>= \n2 ->
if n1 + n2 == 7 then return (n1, n2) else []
``````

How does this work? You should really sit down and work this out for yourself given the definitions of `>>=` and `return` for lists, but here's a hand-wavy explanation. Note that `[1..6]` is a monadic value in the list monad, so it delivers all of its values to `n1` (one at a time, of course), and then again to `n2`, and then if the sum is correct all the pairs `(n1, n2)` will be returned. So we're doing a computation on all elements of a list as easily as if it were computations on only single elements. That's what the list monad buys you.

If you've done any significant amount of Haskell programming, alarm bells are going off in your head right about now. "But wait!" I hear you cry. "Can't you just use a list comprehension to do this?" Indeed you can, and it looks like this:

``````  [(n1, n2) | n1 <- [1..6], n2 <- [1..6], n1 + n2 == 7]
``````

The list monad can in fact do anything that list comprehensions can do. Which syntax one prefers is a matter of taste and may also depend on the particular problem. In fact, Phil Walder, in the paper Comprehending Monads (there's a pun in that title, as there are in most of Phil's paper titles) suggested that the list comprehension syntax be extended to arbitrary monads. That proposal was eventually rejected in favor of the current notation.

The list monad is more than just an alternate version of list comprehensions, though. For one thing, there are many very generic functions that can work on instances of any monad; having a list monad means that those functions can work on lists as well. Furthermore, there is an extension to the `Monad` type class called `MonadPlus` which adds extra functionality to monads (specifically, it defines a "zero" element for a monad as well as a way of "adding" two monadic values). Lists turn out to be an instance of `MonadPlus` as well as of `Monad`, and this means that generic functions that work on all instances of `MonadPlus` will also work on lists. (For instance, there is a generalization of the `concat` function called `msum` which works for any instance of `MonadPlus`, including lists.) It's better to have generic functions that can work on large numbers of datatypes than to have to define new functions for each particular datatype, so this is a clear win.

## Next time

In the next installment I'll look at monads to deal with error handling.

• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic

#### Maybe

Anonymous

August 6 2010, 06:57:10 UTC 10 years ago

return Nothing = Nothing

PS: your tutorial is very intuitive and nice. Done a good job!

#### Re: Maybe

August 6 2010, 08:44:36 UTC 10 years ago Edited:  August 6 2010, 08:46:39 UTC

Thanks! I have two more articles nearly ready to post, so stay tuned. Anyway, return for the Maybe monad is just Just, because its argument is arbitrary (it's not restricted to be a Maybe type). Written out fully, it's:

return :: a -> Maybe a
return x = Just x
-- or just:
-- return = Just

Notice that a can be any type whatsoever, not just a Maybe type. The value returned from return (I know that sounds weird) will be a Maybe type, but the argument can be of any type.

#### Re: Maybe

August 6 2010, 09:15:49 UTC 10 years ago

It just occurred to me that I didn't fully answer your question. So, to be exact: return Nothing = Just Nothing.

#### Re: Maybe

September 5 2010, 15:15:59 UTC 10 years ago

I think I may have a related question. If the definition of "return" for the Maybe monad is

```  return x = Just x
```

then it doesn't seem to match what's built in to Haskell, viz:

```  *Main> return Nothing
Nothing
```

and

```  *Main> return (Just 3)
Just 3
```

Is there something I'm missing? Your tutorials are awesome, by the way, thanks.

#### Re: Maybe

September 6 2010, 05:14:02 UTC 10 years ago Edited:  September 6 2010, 05:15:36 UTC

James, Thanks for the compliment! Yeah, ghci can be confusing. What's going on when you type
```  ghci> return Nothing
```
is that you are using the "return" function of the IO monad, not the Maybe monad. This means that the type of (return Nothing) is actually (IO (Maybe a)). Similarly, (return (Just 3)) has type (IO (Maybe Int)) (actually, it's more general, but that will do for illustration). When ghci has to show the result of a computation of type (IO a), it just shows the value (of type a), so
```  ghci> return 10
10
```
This (return 10) has type (IO Int) and so ghci just prints the Int. But watch what happens when you specify the type manually:
```  ghci> return 10 :: Maybe Int
Just 10

ghci> return Nothing :: Maybe (Maybe a)
Just Nothing
```
I realize that this is confusing; this is probably the most confusing aspect of ghci. Compiling code from a file with ghc is much better behaved.

#### Re: Maybe

Anonymous

March 20 2011, 19:06:20 UTC 9 years ago

I actually made the same error when I tried to derive the return for the Maybe monad going through the tutorial. Specifically, if you define the monad as:

Nothing >>= _ = Nothing
Just x >>= f = f x
return Nothing = Nothing
return x = Just x

instead of simply return = Just, this actually doesn't follow the second Monad law for the case where mv = Just Nothing.

(Just Nothing) >>= return == (since Just x >>= f == f x by def. of >>=)
return Nothing == Nothing (by alternate definition of return).

But this contradicts the second monad law saying Just Nothing >>= return == Just Nothing.

Hope this is helps clear things up. Excellent tutorials by the way.

#### Re: Maybe

March 21 2011, 00:07:28 UTC 9 years ago

Thanks!

#### (Possible) eq. 6 proof & dice roll errors

Anonymous

December 7 2010, 00:18:23 UTC 9 years ago

Hey there,

I’m all very new to this, but I think I may have found some little errors:

1. In the Eq. 6 proof, the lines

= map f x1 : map f (xs ++ y) -- definition of map
= map f x1 : (map f xs ++ map f y) -- inductive hypothesis
= (map f x1 : map f xs) ++ map f y -- definition of ++

the first map on each line should be omitted, according to the definition of the map function.

2. In the dice roll function, the if and else branches don’t have the same types—(n1,n2) vs. [ ]. If I understand this all correctly, the tuple should be made into a list: [(n1,n2)].

Of course, if any of this is wrong, feel free to correct me!

Thanks a lot for these guides. Especially the monadic functions vs. monadic values discussion and the in-depth treatment of example monads are invaluable!

#### Re: (Possible) eq. 6 proof & dice roll errors

December 17 2010, 01:16:28 UTC 9 years ago

Thanks for your bug fixes! I'll have a corrected version up shortly. It's embarrassing to see these mistakes, but it's great to have readers who catch them. Thanks also for your positive comments -- I really appreciate them.

#### Re: (Possible) eq. 6 proof & dice roll errors

December 17 2010, 01:22:21 UTC 9 years ago

BTW the dice roll function is correct, as you can verify by typing into ghci or copying to a file and running from ghci. The "then" branch of the if is "return (n1, n2)" which is just [(n1, n2)] by the definition of return for the list monad. So both branches of the if have the same type.

#### Trivial typo

Anonymous

February 28 2011, 05:43:05 UTC 9 years ago

In your dice roll example, you say "find all pairs of numbers between 1 and 6 that sum to the number 7". It should be "sum to the number 6". Just thought I'd point that out.

#### Re: Trivial typo

March 3 2011, 23:53:43 UTC 9 years ago

Thanks for pointing this out! I meant 7, so I'll fix it and repost it shortly.