# Monads in 15 minutes: Backtracking and Maybe

This morning, a programmer visited #haskell and asked how to implement backtracking. Not surprisingly, most of the answers involved monads. After all, monads are ubiquitous in Haskell: They're used for IO, for probability, for error reporting, and even for quantum mechanics. If you program in Haskell, you'll probably want to understand monads. So where's the best place to start?

A friend of mine claims he didn't truly understand monads until he
understood `join`

. But once he figured that out, everything was
suddenly obvious. That's the way it worked for me, too. But relatively
few monad tutorials are based on `join`

, so there's an open niche in a crowded market.

This monad tutorial uses `join`

. Even better, it attempts to
cram everything you need to know about monads into 15 minutes. (Hey, everybody needs a gimmick, right?)

### Backtracking: The lazy way to code

We begin with a backtracking constraint solver. The idea: Given
possible values for `x`

and `y`

, we want to pick
those values which have a product of 8:

```
solveConstraint = do
x <- choose [1,2,3]
y <- choose [4,5,6]
guard (x*y == 8)
return (x,y)
```

Every time `choose`

is called, we save the current program
state. And every time `guard`

fails, we backtrack to a saved
state and try again. Eventually, we'll hit the right answer:

```
> take 1 solveConstraint
[(2,4)]
```

Let's build this program step-by-step in Haskell. When we're done, we'll have a monad. <!--more-->

### Implementing `choose`

How can we implement `choose`

in Haskell? The obvious version
hits a dead-end quickly:

```
-- Pick one element from the list, saving
-- a backtracking point for later on.
choose :: [a] -> a
choose xs = ...
```

We could be slightly sneakier, and return *all* the possible choices
as a list. We'll use `Choice`

whenever we talk
about these lists, just to keep things clear:

```
type Choice a = [a]
choose :: [a] -> Choice a
choose xs = xs
```

Running this program returns all the possible answers:

```
> choose [1,2,3]
[1,2,3]
```

Now, since Haskell is a lazy language, we can work with infinite numbers of choices, and only compute those we actually need:

```
> take 3 (choose [1..])
[1,2,3]
```

Because Haskell doesn't compute answers until we ask for them, we get the actual backtracking for free!

### Combining several choices

Now we have the list `[1,2,3]`

from our example. But what about
the list `[4,5,6]`

? Let's ignore `guard`

for a minute, and work on getting the final pairs of numbers, unfiltered by any constraint.

For *each* item in the first list, we
need to pair it with *every* item in the second list. We can do
that using `map`

and the following helper function:

```
pair456 :: Int -> Choice (Int,Int)
pair456 x = choose [(x,4), (x,5), (x,6)]
```

Sure enough, this gives us all 9 combinations:

```
> map pair456 (choose [1,2,3])
[[(1,4),(1,5),(1,6)],
[(2,4),(2,5),(2,6)],
[(3,4),(3,5),(3,6)]]
```

But now we have two layers of lists. We can fix that using
`join`

:

```
join :: Choice (Choice a) -> Choice a
join choices = concat choices
```

This collapses the two layers into one:

```
> join (map pair456 (choose [1,2,3]))
[(1,4),(1,5),(1,6),
(2,4),(2,5),(2,6),
(3,4),(3,5),(3,6)]
```

Now that we have `join`

and `map`

, we have two-thirds
of a monad! (Math trivia: In category theory, `join`

is usually
written μ.)

In Haskell, `join`

and `map`

are usually combined
into a single operator:

```
-- Hide the standard versions so we can
-- reimplement them.
import Prelude hiding ((>>=), return)
(>>=) :: Choice a -> (a -> Choice b) ->
Choice b
choices >>= f = join (map f choices)
```

This allows us to simplify our example even further:

```
> choose [1,2,3] >>= pair456
[(1,4),(1,5),(1,6),
(2,4),(2,5),(2,6),
(3,4),(3,5),(3,6)]
```

### Completing our monad: `return`

We're getting close! We only need to define the third
monad function (and then figure out what to do about `guard`

).

The missing function is almost too trivial to mention: Given a single value of
type `a`

, we need a convenient way to construct a value of type
`Choice a`

:

```
return :: a -> Choice a
return x = choose [x]
```

(More math trivia: `return`

is also known as `unit`

and η. That's a lot of names for a very simple idea.)

Let's start assembling the pieces. In the code below, ```
(\x ->
...)
```

creates a function with a single argument `x`

. Pay
careful attention to the parentheses:

```
makePairs :: Choice (Int,Int)
makePairs =
choose [1,2,3] >>= (\x ->
choose [4,5,6] >>= (\y ->
return (x,y)))
```

When run, this gives us a list of all possible combinations of `x`

and `y`

:

```
> makePairs
[(1,4),(1,5),(1,6),
(2,4),(2,5),(2,6),
(3,4),(3,5),(3,6)]
```

As it turns out, this is a really common idiom, so Haskell provides some nice syntactic sugar for us:

```
makePairs' :: Choice (Int,Int)
makePairs' = do
x <- choose [1,2,3]
y <- choose [4,5,6]
return (x,y)
```

This is equivalent to our previous implementation:

```
> makePairs'
[(1,4),(1,5),(1,6),
(2,4),(2,5),(2,6),
(3,4),(3,5),(3,6)]
```

### The final piece: `guard`

In our backtracking monad, we can represent failure as a choice between zero options. (And indeed, this is known as the "zero" for our monad. Not all useful monads have zeros, but you'll see them occasionally.)

```
-- Define a "zero" for our monad. This
-- represents failure.
mzero :: Choice a
mzero = choose []
-- Either fail, or return something
-- useless and continue the computation.
guard :: Bool -> Choice ()
guard True = return ()
guard False = mzero
```

And now we're in business:

```
solveConstraint = do
x <- choose [1,2,3]
y <- choose [4,5,6]
guard (x*y == 8)
return (x,y)
```

Note that since the return value of `guard`

is boring, we don't actually bind it to any variable. Haskell treats this as if we had written:

```
-- "_" is an anonymous variable.
_ <- guard (x*y == 8)
```

That's it!

```
> take 1 solveConstraint
[(2,4)]
```

### Another monad: `Maybe`

Every monad has three pieces: `return`

, `map`

and
`join`

. This pattern crops up everywhere. For example, we can
represent a computation which might fail using the `Maybe`

monad:

```
returnMaybe :: a -> Maybe a
returnMaybe x = Just x
mapMaybe :: (a -> b) -> Maybe a -> Maybe b
mapMaybe f Nothing = Nothing
mapMaybe f (Just x) = Just (f x)
joinMaybe :: Maybe (Maybe a) -> Maybe a
joinMaybe Nothing = Nothing
joinMaybe (Just x) = x
```

Once again, we can use `do`

to string together individual steps
which might fail:

```
tryToComputeX :: Maybe Int
tryToComputeX = ...
maybeExample :: Maybe (Int, Int)
maybeExample = do
x <- tryToComputeX
y <- tryToComputeY x
return (x,y)
```

Once you can explain how this works, you understand monads. And you'll start to see this pattern everywhere. There's something deep about monads and abstract algebra that I don't understand, but which keeps cropping up over and over again.

### Miscellaneous notes

In Haskell, monads are normally defined using the `Monad`

type
class. This requires you to define two functions: `return`

and
`>>=`

. The `map`

function for monads is actually
named `fmap`

, and you can find it in the `Functor`

type class.

Also, every monad should obey three fairly reasonable rules if you don't want bad things to happen:

```
-- Adding and collapsing an outer layer
-- leaves a value unchanged.
join (return xs) == xs
-- Adding and collapsing an inner layer
-- leaves a value unchanged.
join (fmap return xs) == xs
-- Join order doesn't matter.
join (join xs) == join (fmap join xs)
```

That's it! For more information, see Wadler's Monads for Functional Programming and the excellent All About Monads tutorial. And if you liked the backtracking monad, you'll also like The Reasoned Schemer.

(This tutorial is dedicated to "ivanm" on #haskell. I hope this helps! And many thanks to Reg Braithwaite for commenting on an early draft.)

**Update:** Replaced `mult456`

with `pair456`

, and explained what's going on with `guard`

in the final backtracking example.

Want to contact me about this article? Or if you're looking for something else to read, here's a list of popular posts.

`guard (x*y == 8)`

in the`do`

-body is short for`ignored <- guard (x*y == 8)`

. So you're really looking at this:`x`

and`y`

are integers, not lists: Remember that`xs >>= f`

is just`join (map f xs)`

. So the individual bindings expand to something that looks like:`x`

is clearly bound to an individual value from`xs`

. When I'm trying to understand something like this, I have the most luck if I go over things a couple of times (and maybe write a test program or two). Reading this kind of Haskell is more like reading math than it is like reading regular code. Definitely a chance of pace. :-) Good luck, and please don't hesitate to ask if you have any more questions!`liftM`

is guaranteed to exist, and that`fmap`

is left up to the whims of library authors. But still, the connection between`fmap`

and monads is pretty important from a mathematical perspective.`guard`

returns either`[()]`

(if is succeeds), or`[]`

(if it fails). So if the`guard`

succeeds, you can imagine it as:`map`

example, we can see how it works:`join`

, two branches of the computation disappear entirely:`x`

and`y`

in this example? Well, they're the arguments of the anonymous functions in my previous comment, so they'll be available when we need them in the final step. (It might help to read about closures if none of this makes any sense at all.) Alternatively, are you familiar with list comprehensions? If so, this program is equivalent to:`x*y`

doesn't equal`8`

, then there are no values to pick from for`ignored`

, and the final`(x,y)`

won't be computed. Anyway, I hope one of these perspectives will help you puzzle it out!A friend of mine claims he didn’t truly understand monads until he understood join.There's a reason why category theorists invariably define monads in terms of join rather than bind! As for your question about monads and algebra: I don't really understand monad transformers myself, so can't help with that bit, but there is indeed a deep connection between monads and algebraic theories. Any standard category theory book should help you here - try Borceux's Handbook of Categorical Algebra. Or just google for "category theory lecture notes". I found enlightenment came from considering this: an /algebra/ for a monad T on a category C is an object A and a morphism a:TA->A, satisfying some obvious compatibility conditions with eta and mu. Now, what is an algebra for the List monad, also known as the "free monoid" monad? How about the free group monad? Sorry if I'm teaching you to suck eggs here...arerelated to monads, at least according to Edmund Robinson’s Variations on Algebra: monadicity and generalisations of equational theories (which I haven't finished reading yet). A monad is a triple (M,η,μ), whereMis a functor, and η:a→M aand μ:M (M a)→M aare natural transformations. A monad morphism is a transformation from one monad to another, e.g., (M,η,μ) → (M′,η′,μ′). And you can build various interesting algebras by composing monad morphisms. And that's the bit I still haven't wrapped my brain completely around. :-)`choose`

function does nothing but make the code more readable; it's not actually needed, not even for the type declaration. The`guard`

is fairly sneaky. If the condition is true, it chooses a dummy value from a single-element list and throws it away. If the condition is false, though, it "chooses" an element from an empty list. Imagine, for a moment, the guard condition is always false. We bind`x`

to one of 3 values, and`y`

to one of 3 values, giving us 3×3=9 different possible answers. If we imagine that the`guard`

condition is always false, it would choose from 0 possibilities, giving us 3×3×0=0 possible answers. Do you see how the empty choice suppresses answers? It doesn't have to effect the`return`

statement directly, because we never make it there. Of course, if the`guard`

is only falsesomeof the time, then it only suppresses certain answers. I hope this helps! Please don't hesitate to ask more questions.isa monad. Or, if you want to look at it the other way around, a monad is a generalized comprehension that can be defined for almost any parameterized data type. For a more complicated monad, see Bayes' rule in Haskell. For a rather different monad, see SPJ's papers on Software Transactional Memory. Basically, by slightly generalizing list comprehensions, you get a tool which solves a surprisingly large and diverse set of problems. I'll write a longer post one of these days cataloging a bunch of useful monads. Until then, would anyone like to plug their favorite monads? :-)