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.
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 thedo
-body is short forignored <- guard (x*y == 8)
. So you're really looking at this:x
andy
are integers, not lists: Remember thatxs >>= f
is justjoin (map f xs)
. So the individual bindings expand to something that looks like:x
is clearly bound to an individual value fromxs
. 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 thatfmap
is left up to the whims of library authors. But still, the connection betweenfmap
and monads is pretty important from a mathematical perspective.guard
returns either[()]
(if is succeeds), or[]
(if it fails). So if theguard
succeeds, you can imagine it as:map
example, we can see how it works:join
, two branches of the computation disappear entirely:x
andy
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 equal8
, then there are no values to pick from forignored
, and the final(x,y)
won't be computed. Anyway, I hope one of these perspectives will help you puzzle it out!choose
function does nothing but make the code more readable; it's not actually needed, not even for the type declaration. Theguard
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 bindx
to one of 3 values, andy
to one of 3 values, giving us 3×3=9 different possible answers. If we imagine that theguard
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 thereturn
statement directly, because we never make it there. Of course, if theguard
is only false some of the time, then it only suppresses certain answers. I hope this helps! Please don't hesitate to ask more questions.