*A Gentle Introduction to Haskell, Version 98*

back next top

This section is perhaps less "gentle" than the others. Here we
address not only the language features that involve monads but also
try to reveal the bigger picture: why monads are such an important
tool and how they are used. There is no
single way of explaining monads that works for everyone; more
explanations can be found at `haskell.org`. Another good
introduction to practical programming using monads is Wadler's
*Monads for Functional Programming* [10].

A monad is constructed on top of a polymorphic type such as `IO`. The
monad itself is defined by instance declarations
associating the type with the some or all of the
monadic classes, `Functor`, `Monad`,
and `MonadPlus`. None of the monadic classes are derivable. In addition
to `IO`, two other types in the Prelude are members of the monadic
classes: lists (`[]`) and `Maybe`.

Mathematically, monads are governed by set of *laws* that should hold
for the monadic operations. This idea of laws is not unique to
monads: Haskell includes other operations that are
governed, at least informally, by laws. For example, `x /= y` and
`not (x == y)` ought to be the same for any type of values being
compared. However, there is no guarantee of this: both `==` and `/=` are
separate methods in the `Eq` class and there is no way to assure that
`==` and `=/` are related in this manner.
In the same sense, the monadic laws presented here are not enforced by
Haskell, but ought be obeyed by any instances of a monadic class.
The monad laws give insight into the underlying structure of monads:
by examining these laws, we hope to give a feel for how monads are
used.

The `Functor` class, already discussed in section
5, defines a
single operation: `fmap`. The map function applies an operation to the
objects inside a container (polymorphic types can be thought of as
containers for values of another type), returning a container of the
same shape.
These laws apply to `fmap` in the class `Functor`:

fmap id | = | id |

fmap (f . g) | = | fmap f . fmap g |

These laws ensure that the container shape is unchanged by
`fmap` and that the contents of the container are not re-arranged by
the mapping operation.

The `Monad` class defines two basic operators: `>>=` (bind) and `return`.
`
infixl 1 >>, >>=
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a
fail :: String -> m a
m >> k = m >>= \_ -> k
`The bind operations,

The precise meaning of binding depends, of course, on the monad. For
example, in the IO monad, `x >>= y` performs two actions sequentially,
passing the result of the first into the second. For the other
built-in monads, lists and the `Maybe` type, these monadic operations
can be understood in terms of passing zero or more values from one
calculation to the next. We will see examples of this shortly.

The `do` syntax provides a simple shorthand for chains of monadic
operations. The essential translation of `do` is captured in the
following two rules:
`
do e1 ; e2 = e1 >> e2
do p <- e1; e2 = e1 >>= \p -> e2
`When the pattern in this second form of

do p <- e1; e2 = e1 >>= (\v -> case v of p -> e2; _ -> fail "s")

The laws which govern `>>=` and `return` are:

return a >>= k | = | k a |

m >>= return | = | m |

xs >>= return . f | = | fmap f xs |

m >>= (\x -> k x >>= h) | = | (m >>= k) >>= h |

The class `MonadPlus` is used for monads that have a *zero* element
and a *plus* operation:
`
class (Monad m) => MonadPlus m where
mzero :: m a
mplus :: m a -> m a -> m a
`The zero element obeys the following laws:

m >>= \x -> mzero | = | mzero |

mzero >>= m | = | mzero |

For lists, the zero value is `[]`, the empty list. The I/O monad has
no zero element and is not a member of this class.

The laws governing the `mplus` operator are as follows:

m `mplus` mzero | = | m |

mzero `mplus` m | = | m |

The `mplus` operator is ordinary list concatenation in the list monad.

For lists, monadic binding involves joining together a set of
calculations for each value in the list. When used with lists, the
signature of `>>=` becomes:
`
(>>=) :: [a] -> (a -> [b]) -> [b]
`That is, given a list of

[(x,y) | x <- [1,2,3] , y <- [1,2,3], x /= y]

do x <- [1,2,3]

y <- [1,2,3]

True <- return (x /= y)

return (x,y)

[1,2,3] >>= (\ x -> [1,2,3] >>= (\y -> return (x/=y) >>=

(\r -> case r of True -> return (x,y)

_ -> fail "")))

mvLift2 :: (a -> b -> c) -> [a] -> [b] -> [c]

mvLift2 f x y = do x' <- x

y' <- y

return (f x' y')

mvLift2 (+) [1,3] [10,20,30] | => | [11,21,31,13,23,33] |

mvLift2 (\a b->[a,b]) "ab" "cd" | => | ["ac","ad","bc","bd"] |

mvLift2 (*) [1,2,4] [] | => | [] |

This function is a specialized version of the `LiftM2` function in the
monad library. You can think of it as transporting a function from
outside the list monad, `f`, into the list monad in which computations
take on multiple values.

The monad defined for `Maybe` is similar to the list monad: the value
`Nothing` serves as `[]` and `Just x` as `[x]`.

Briefly, a state monad built around a state type `S` looks
like this:
`
data SM a = SM (S -> (a,S)) -- The monadic type
instance Monad SM where
-- defines state propagation
SM c1 >>= fc2 = SM (\s0 -> let (r,s1) = c1 s0
SM c2 = fc2 r in
c2 s1)
return k = SM (\s -> (k,s))
-- extracts the state from the monad
readSM :: SM S
readSM = SM (\s -> (s,s))
-- updates the state of the monad
updateSM :: (S -> S) -> SM () -- alters the state
updateSM f = SM (\s -> ((), f s))
-- run a computation in the SM monad
runSM :: S -> SM a -> (a,S)
runSM s0 (SM c) = c s0
`This example defines a new type,

This instance declaration defines the `plumbing' of the monad: how to
sequence two computations and the definition of an empty computation.
Sequencing (the `>>=` operator) defines a computation (denoted by the
constructor `SM`) that passes an initial
state, `s0`, into `c1`, then passes the value coming out of this
computation, `r`, to the function that returns the second computation,
`c2`. Finally, the state coming out of `c1` is passed into `c2` and
the overall result is the result of `c2`.

The definition of `return` is easier: `return` doesn't change the
state at all; it only serves to bring a value into the monad.

While `>>=` and `return` are the basic monadic sequencing operations,
we also need some *monadic primitives*. A monadic primitive is
simply an operation that uses the insides of the monad abstraction and
taps into
the `wheels and gears' that make the monad work. For example, in the
`IO` monad, operators such as `putChar` are primitive since they deal
with the inner workings of the `IO` monad. Similarly, our state monad
uses two primitives: `readSM` and `updateSM`. Note that these depend
on the inner structure of the monad - a change to the definition of
the `SM` type would require a change to these primitives.

The definition of `readSM` and `updateSM` are simple: `readSM` brings
the state out of the monad for observation while `updateSM` allows the
user to alter the state in the monad. (We could also have used
`writeSM` as a primitive but update is often a more natural way of
dealing with state).

Finally, we need a function that runs computations in the monad,
`runSM`. This takes an initial state and a computation and yields
both the returned value of the computation and the final state.

Looking at the bigger picture, what we are trying to do is define an
overall computation as a series of steps (functions with type
`SM a`), sequenced using `>>=` and `return`. These steps may interact
with the state (via `readSM` or `updateSM`) or may ignore the state.
However, the use (or non-use) of the state is hidden: we don't invoke
or sequence our computations differently depending on whether or not
they use `S`.

Rather than present any examples using this simple state monad, we
proceed on to a more complex example that includes the state monad.
We define a small *embedded language* of resource-using
calculations.
That is, we build a special purpose language implemented as a set of Haskell
types and functions. Such languages use the basic tools of Haskell,
functions and types, to build a library of operations
and types specifically tailored to a domain of interest.

In this example, consider a computation that requires some sort of
resource. If the resource is available, computation proceeds; when the
resource is unavailable, the computation suspends. We use the type `R
`to denote a computation using resources controlled by our monad.
The definition of `R` is as follows:
`
data R a = R (Resource -> (Resource, Either a (R a)))
`Each computation is a function from available resources to remaining
resources, coupled with either a result, of type

The `Monad` instance for `R` is as follows:
`
instance Monad R where
R c1 >>= fc2 = R (\r -> case c1 r of
(r', Left v) -> let R c2 = fc2 v in
c2 r'
(r', Right pc1) -> (r', Right (pc1 >>= fc2)))
return v = R (\r -> (r, (Left v)))
`The

- a value,
`v`, and remaining resources, which are used to determine the next computation (the call`fc2 v`), or - a suspended computation,
`pc1`, and resources remaining at the point of suspension.

This instance declaration defines the basic structure of the monad but
does not determine how resources are used. This monad could be
used to control many types of resource or implement many different
types of resource usage policies. We will demonstrate a very simple
definition of resources as an example: we choose `Resource` to be an
`Integer`, representing available computation steps:
`
type Resource = Integer
`This function takes a step unless no steps are available:

step :: a -> R a

step v = c where

c = R (\r -> if r /= 0 then (r-1, Left v)

else (r, Right c))

So far, we have the tools to define a sequence of "resourceful"
computations (the monad) and we can express a form of resource usage
using `step`. Finally, we need to address how computations in this
monad are expressed.

Consider an increment function in our monad:
`
inc :: R Integer -> R Integer
inc i = do iValue <- i
step (iValue+1)
`This defines increment as a single step of computation. The

This definition isn't particularly satisfying, though, compared to the
standard definition of the increment function. Can we instead "dress
up" existing operations like `+` so that they work in our monadic
world? We'll start with a set of `lifting` functions. These
bring existing functionality into the monad. Consider the definition
of `lift1` (this is slightly different from the `liftM1` found in the
`Monad` library):
`
lift1 :: (a -> b) -> (R a -> R b)
lift1 f = \ra1 -> do a1 <- ra1
step (f a1)
`This takes a function of a single argument,

inc :: R Integer -> R Integer

inc i = lift1 (i+1)

lift2 :: (a -> b -> c) -> (R a -> R b -> R c)

lift2 f = \ra1 ra2 -> do a1 <- ra1

a2 <- ra2

step (f a1 a2)

Using `lift2`, we can create a new version of `==` in the `R` monad:
`
(==*) :: Ord a => R a -> R a -> R Bool
(==*) = lift2 (==)
`We had to use a slightly different name for this new function since

instance Num a => Num (R a) where

(+) = lift2 (+)

(-) = lift2 (-)

negate = lift1 negate

(*) = lift2 (*)

abs = lift1 abs

fromInteger = return . fromInteger

inc :: R Integer -> R Integer

inc x = x + 1

To express interesting computations in `R` we will need a
conditional. Since we can't use `if` (it requires that the test be of
type `Bool` instead of `R Bool`), we name the function `ifR`:
`
ifR :: R Bool -> R a -> R a -> R a
ifR tst thn els = do t <- tst
if t then thn else els
`Now we're ready for a larger program in the

fact :: R Integer -> R Integer

fact x = ifR (x ==* 0) 1 (x * fact (x-1))

We're now ready to actually run some programs. This function runs a
program in `M` given a maximum number of computation steps:
`
run :: Resource -> R a -> Maybe a
run s (R p) = case (p s) of
(_, Left v) -> Just v
_ -> Nothing
`We use the

run 10 (fact 2) | => | Just 2 |

run 10 (fact 20) | => | Nothing |

Finally, we can add some more interesting functionality to this
monad. Consider the following function:
`
(|||) :: R a -> R a -> R a
`This runs two computations in parallel, returning the value of the
first one to complete. One possible definition of this function is:

c1 ||| c2 = oneStep c1 (\c1' -> c2 ||| c1')

where

oneStep :: R a -> (R a -> R a) -> R a

oneStep (R c1) f =

R (\r -> case c1 1 of

(r', Left v) -> (r+r'-1, Left v)

(r', Right c1') -> -- r' must be 0

let R next = f c1' in

next (r+r'-1))

We can now evaluate expressions like `run 100 (fact (-1) ||| (fact 3))
`without looping since the two calculations are interleaved. (Our
definition of `fact` loops for `-1`).
Many variations are possible on this basic
structure. For example, we could extend the state to include a trace
of the computation steps. We could also embed this monad inside the
standard `IO` monad, allowing computations in `M` to interact with the
outside world.
While this example is perhaps more advanced than others in this tutorial,
it serves to illustrate the power of monads as a tool for defining the
basic semantics of a system. We also present this example as a model
of a small *Domain Specific Language*, something Haskell is
particularly good at defining. Many other DSLs have been developed in
Haskell; see `haskell.org` for many more examples. Of particular
interest are Fran, a language of reactive animations, and Haskore, a
language of computer music.

back next top