Thinking Functionally with Haskell (40 page)

Finally, there are two rules that can be proved from the translation rules above:

But one has to be careful; the nested
do
s in

are necessary if
stmts2
and
stmts3
contain more than one action.

Monad laws

The monad laws say nothing much more than that expressions involving
return
and
(>>=)
simplify in just the way one would expect. There are three laws and we are going to state them in three different ways. The first law states that
return
is a right identity element of
(>>=)
:
(p >>= return) = p

In
do
-notation the law reads:

do {x <- p; return x} = do {p}

The second law says that
return
is also a kind of left identity element:
(return e >>= f) = f e

In
do
-notation the law reads:

do {x <- return e; f x} = do {f e}

The third law says that
(>>=)
is kind of associative:

((p >>= f) >>= g) = p >>= (\x -> (f x >>= g))
In
do
-notation the law reads:

The last line makes use of the un-nesting property of
do
-notation.

For the third way of stating the monad laws, consider the operator
(>=>)
defined by

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
(f >=> g) x = f x >>= g

This operator is just like function composition except that the component functions each have type
x -> m y
for appropriate
x
and
y
, and the order of composition is from left to right rather than from right to left. This operator, which is called
(left to right) Kleisli composition
, is defined in the Haskell library
Control.Monad
. There is a dual version,
(right to left) Kleisli composition
,
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
whose definition we leave as an easy exercise.

The point is that we can define
(>>=)
in terms of
(>=>)
:
(p >>= f) = (id >=> f) p

More briefly,
(>>=) = flip (id >=>)
. We also have the
leapfrog
rule:
(f >=> g) . h = (f . h) >=> g

The proof is left as an exercise.

In terms of
(>=>)
the three monad laws say simply that
(>=>)
is associative with identity
return
. Any set of values with an associative binary operation and an identity element is called a
monoid
, and the word ‘monad’ was probably adopted because of the pun with monoid. Be that as it may, this is certainly the shortest way of stating the monad laws.

One additional and instructive way of describing the monad laws is considered in the exercises.

If it wasn’t for the problem of how to sequence input–output actions correctly, monads probably wouldn’t have appeared in Haskell. But once it was appreciated
what they could do, all kinds of other uses quickly followed. We have seen with the
Maybe
monad how chains of computations that involve passing information back up the chain can be simplified with monadic notation. Another primary use of monads is a way to handle
mutable
structures, such as arrays, that rely for their efficiency on being able to update their values, destroying the original structure in the process.

Mutable structures are introduced through the State-Thread monad
ST s
which we will consider in a subsequent section. Before getting on to the particular properties of this monad, we start by considering a simpler monad, called
State s
, for manipulating an explicit state
s
. You can think of the type
State s a
as being
type State s a = s -> (a,s)

An action of type
State s a
takes an initial state and returns a value of type
a
and a new state. It is tempting, but wrong, to think of
IO a
as synonymous with
State World a
. The state component
s
in
State s a
can be exposed and manipulated, but we can’t expose and manipulate the world.

Specifically, as well as the monad operations
return
and
(>>=)
, five other functions are provided for working with the state monad:
put
:: s -> State s ()

get
:: State s s

state
:: (s -> (a,s)) -> State s a

runState
:: State s a -> (s -> (a,s))
evalState :: State s a -> s -> a

The function
put
puts the state into a given configuration, while
get
returns the current state. Each of these two operations can be defined in terms of
state
:
put s = state (\_ -> ((),s))

get
= state (\s -> (s,s))

On the other hand,
state
can also be defined using
put
and
get
:
state f = do {s <- get; let (a,s') = f s;

put s'; return a}

Haskell permits an abbreviated form of
let
expressions in
do
expressions (and also in list comprehensions). We have
do {let decls; stmts} = let decls in do {stmts}

The function
runState
is the inverse of
state
: it takes both an action and an
initial state and returns the final value and the final state after performing the action (something the
IO
monad cannot do). The function
evalState
is defined by
evalState m s = fst (runState m s)

and returns just the value of the stateful computation.

Here is an example of the use of
State
. In
Section 7.6
we constructed the following program for building a binary tree out of a given nonempty list of values:

build :: [a] -> BinTree a

build xs = fst (build2 (length xs) xs)

build2 1 xs = (Leaf (head xs),tail xs)

build2 n xs = (Fork u v, xs'')

where (u,xs') = build2 m xs

(v,xs'')
= build2 (n-m) xs'

m
= n `div` 2

The point to appreciate here is that
build2
is essentially a function that manipulates a state of type
[a]
, returning elements of
BinTree a
as its result. Another way of writing
build
is as follows:

build xs = evalState (build2 (length xs)) xs

build2 :: Int -> State [a] (BinTree a)

build2 1 = do {x:xs <- get;

put xs;

return (Leaf x)}

build2 n = do {u <- build2 m;

v <- build2 (n-m);

return (Fork u v)}

where m = n `div` 2

All the work in manipulating the state explicitly is done when building a leaf. The state is accessed and its first element is chosen as the label associated with a
Leaf
; the remaining list then is installed as the new state. Whereas the first version of
build2 n
threads the state explicitly, the second version hides this machinery under a monadic hood.

Notice in the first line of
build2
we have a statement
x:xs <- get
in which the left-hand side is a
pattern
rather than a simple variable. If the current state happens to be the empty list, the action fails with a suitable error message. For example,
ghci> runState (do {x:xs <- get; return x}) ""

*** Exception: Pattern match failure in do expression ...

Of course this behaviour cannot arise with
build2 1
because the definition only applies when the state is a singleton list. We leave it as an exercise to say what
build []
does.

As another example, consider the problem of producing a pseudo-random integer in a specified interval. Imagine we have a function
random :: (Int,Int) -> Seed -> (Int,Seed)

that takes a pair of integers as the specified interval and then a seed, and calculates a random integer and a new seed. The new seed is used for obtaining further random values. Rather than be explicit about what a seed is, suppose there is a function
mkSeed :: Int -> Seed

that makes a seed from a given integer. Now if we wanted to roll a pair of dice, we could write

diceRoll :: Int -> (Int,Int)

diceRoll n = (x,y)

where (x,s1) = random (1,6) (mkSeed n)

(y,s2) = random (1,6) s1

But we could also write

The function
randomS :: (Int,Int) -> State Seed Int
takes an interval and returns an action. The second version of
diceRoll
is a little longer than the first, but is arguably more easy to write. Imagine that instead of two dice we had five, as in liar dice. The first method would involve a chain of where-clauses expressing the linkage between five values and five seeds, something that would be easy to mistype, but the second version is easily extended and harder to get wrong.

One final point. Consider

evalState (do {undefined; return 0}) 1

Does this raise an exception, or does it return zero? In other words, is the monad

State
strict, as the
IO
monad is, or is it lazy? The answer is that it can be both. There are two variants of the state monad, one of which is lazy and the other of which is strict. The difference lies in how the operation
(>>=)
is implemented. Haskell provides the lazy variant by default, in
Control.Monad.State.Lazy
, but you can ask for the strict variant, in
Control.Monad.State.Strict
if you want.

The state-thread monad, which resides in the library
Control.Monad.ST
, is a different kettle of fish entirely from the state monad, although the kettle itself looks rather similar. Like
State s a
you can think of this monad as the type
type ST s a = s -> (a,s)

but with one very important difference: the type variable
s
cannot be instantiated to specific states, such as
Seed
or
[Int]
. Instead it is there only to
name
the state. Think of
s
as a label that identifies one particular state
thread
. All mutable types are tagged with this thread, so that actions can only affect mutable values in their own state thread.

One kind of mutable value is a
program variable
. Unlike variables in Haskell, or mathematics for that matter, program variables in imperative languages can change their values. They can be thought of as
references
to other values, and in Haskell they are entities of type
STRef s a
. The
s
means that the reference is local to the state thread
s
(and no other), and the
a
is the type of value being referenced. There are operations, defined in
Data.STRef
, to create, read from and write to references:

newSTRef
:: a -> ST s (STRef s a)

readSTRef
:: STRef s a -> ST s a

writeSTRef :: STRef s a -> a -> ST s ()

Here is an example. Recall
Section 7.6
where we gave the following definition of the Fibonacci function:

fib :: Int -> Integer

fib n
= fst (fib2 n)

fib2 0 = (0,1)

fib2 n = (b,a+b) where (a,b) = fib2 (n-1)

Evaluating
fib
takes linear time, but the space involved is not constant (even ignoring the fact that arbitrarily large integers cannot be stored in constant space): each recursive call involves fresh variables
a
and
b
. By contrast, here is a definition of
fib
in the imperative language Python:

def fib (n):

a,b = 0,1

for i in range (0,n):

a,b = b,a+b

return a

The definition manipulates two program variables
a
and
b
, and runs in constant space (at least, for small integers). We can translate the Python code almost directly into Haskell:

fibST :: Int -> ST s Integer

fibST n = do {a <- newSTRef 0;

b <- newSTRef 1;

repeatFor n

(do {x <- readSTRef a;