Yet Another Monad Tutorial (part 8: more on state monads)
In the previous article, we learned what state monads were and how they worked. In this article we'll work through a complete (though very simple) example and we'll constrast Haskell's state handling with the equivalent code written in C.
The GCD function
To start with, we'll look at a simple function as you might write it in the C programming language:
int gcd(int x, int y) {
while (x != y) {
if (x < y) {
y = y - x;
} else {
x = x - y;
}
}
return x;
}
This function computes the greatest common divisor (GCD) of two integers x and
y. For instance, the GCD of 1024 and 40 is 8, because both 1024 and 40 are
divisible by 8, but there is no larger integer that divides both numbers evenly.
[This is not the most efficient way to write this function, but it's just for
illustration.]
Writing this function in idiomatic Haskell is trivial:
gcd :: Int -> Int -> Int
gcd a b | a == b = a
| a < b = gcd b a
| otherwise = gcd b (a - b)
(In fact, this function (actually, a generalization of it) is a library function
in Haskell and is implemented more efficiently.) However, if you compare this
function to the C function, you'll see that they solve the problem in somewhat
different ways. The C function works by changing the local state variables x
and y. The Haskell function reduces a given GCD computation to another one
(where one of the inputs is smaller) or to the final answer. There is no local
state being altered in the Haskell version (unless you think of the function
arguments as local state, which in fact is not a bad way to think about things).
I don't particularly care about the GCD function itself, but we can use the C version as a typical example of a function which works via a series of state transformations. So the question I want to answer in this article is: how can we write a version of GCD in Haskell that works via a series of state transformations, just like the C code does? If this was possible, then in principle any computation that works by state manipulations in C could be written in a similar form in Haskell. Put differently, this would be a way to write imperative code in Haskell.
GCD in state-passing style
We will edge our way into state monads gently, by first rewriting the gcd
function without using state monads. Recall from the previous article in this
series that any stateful function can be written directly in Haskell by
"threading the state" through the function. So for a function which can be
represented schematically as follows:
a --[access/modify state variables]--> b
you could write a real function with this type signature:
(a, s) -> (b, s)
where s is the state type (a tuple of all the state variables). I'll call
this style of writing stateful functions "state-passing style". In order to
write a function in state-passing style, the first thing you need to do is to
figure out what the type s of the state is going to be. In a GCD function,
there are two items of state: the integer x and the integer y. We'll use
Int as the integer type. There is no input type a to speak of; once the
state variables are input the computation can proceed to completion. The result
type b will also be an Int. So we can write a GCD function in state-passing
style with this type signature:
s -> (b, s)
which with the appropriate substitutions for s and b becomes:
(Int, Int) -> (Int, (Int, Int))
For clarity, I'm going to introduce a type alias now:
type GCDState = (Int, Int)
and then the type signature of GCD in state-passing style becomes:
GCDState -> (Int, GCDState)
In words: a GCD state transformer function starts off with certain values for
its state variables x and y (both Ints), and proceeds until it's done;
when it's done it will return the GCD (of type Int) and the final state of the
two state variables.
Writing this function is not particularly hard:
gcd' :: GCDState -> (Int, GCDState)
gcd' s =
let (x, y) = s in -- unpack the state into x, y
case compare x y of
EQ -> (x, s) -- if x == y, return x and the state tuple
LT -> gcd' (y, x) -- if x < y, flip the arguments
GT -> gcd' (y, x - y)
This function may look a bit odd, but in terms of computation it's doing the
exact same thing as the previous gcd function. We should also write a simple
helper function to give the same interface as the gcd function:
run_gcd' :: Int -> Int -> Int
run_gcd' x y = fst (gcd' (x, y))
Now we can test it:
ghci> gcd 1024 40
8
ghci> run_gcd' 1024 40
8
So far, so good. The next step will be to re-write this in terms of state monads. It's important to note that we're not going to do it that way because it confers any particular advantage in this specific case (it's not more efficient, or even more elegant), but just to show you how to write a function in Haskell in the imperative form that state monads allow. If there were a lot of local or global state variables, you can imagine that passing the state around explicitly would be very tedious to code; with a function written using state monads, all the state passing happens implicitly, which can be a significant win.
GCD using state monads (attempt 1)
In the previous article, we saw that state monads involved a data type called
State which had this definition:
data State s a = State (s -> (a, s))
The State data type wraps a function of the form s -> (a, s), where s is
the state type. We already have such a function: gcd'. In gcd' the state
type s is GCDState and the return value type a is Int. So we can write
a monadic version of gcd' like this:
gcd_s1 :: State GCDState Int
gcd_s1 = State gcd'
and run it using this function:
run_gcd_s1 :: Int -> Int -> Int
run_gcd_s1 x y = fst (runState gcd_s1 (x, y))
Let's write an expanded version of this so we don't have to depend on the gcd'
function:
gcd_s1' :: State GCDState Int
gcd_s1' = State (\s ->
let (x, y) = s in
case compare x y of
EQ -> (x, (x, y))
LT -> f (y, x)
GT -> f (y, x - y))
where
f :: GCDState -> (Int, GCDState)
f = runState gcd_s1'
run_gcd_s1' :: Int -> Int -> Int
run_gcd_s1' x y = fst (runState gcd_s1' (x, y))
gcd_s1' is just a State wrapper around a state transformer function which is
essentially the same as gcd'. The run_gcd_s1' function is similar to
run_gcd' (and is also essentially identical to similar functions to be
described below). What it does is take in the initial state values x and y
as its arguments and compute and return their GCD. It does this by first
extracting the state transformer function from gcd_s1' (which is what
runState does) and applying it to the initial state (x, y), which returns a
tuple of the final value and the final state. It then uses fst to extract the
final value and returns it.
Let's test it:
ghci> run_gcd_s1' 1024 40
8
This works, but this is not at all a typical way to use state monads. The whole
point of state monads is to build up a big state transformer from a bunch of
smaller state transformers using the >>= operator. gcd_s1' doesn't do that;
it just defines a big state transformer from the get-go. Doing it this way
completely misses the point of using state monads.
GCD using state monads (attempt 2)
To get any real traction out of state monads, we have to build up larger state
transformers from smaller ones using the >>= operator. I'll show you several
versions of this. Here's the first one:
gcd_s2 :: State GCDState Int
gcd_s2 =
do (x, y) <- getState
case compare x y of
EQ -> return x
LT -> do putState (y, x)
gcd_s2
GT -> do putState (y, x - y)
gcd_s2
where
getState :: State GCDState GCDState
getState = State (\(x, y) -> ((x, y), (x, y)))
putState :: GCDState -> State GCDState ()
putState (x', y') = State (\_ -> ((), (x', y')))
run_gcd_s2 :: Int -> Int -> Int
run_gcd_s2 x y = fst (runState gcd_s2 (x, y))
At this point, I'm not expecting you to understand this. I want to first
describe how this works intuitively, and then I'll show you a version without
the do notation and fill in the missing pieces.
Note on terminology: As in the previous article, I'm going to use the term "state transformer" to refer to state monadic values and "state transformer function" to refer to the functions stored inside state monadic values.
The state transformer function inside gcd_s2 starts by extracting the current
version of the state variables x and y using the getState state
transformer. If x and y are identical, x is returned (we could return y
instead; it makes no difference). If x is less than y, then we use the
putState state transformer to swap the values of x and y in the stored
state. Otherwise, we replace x by y and we replace y by x - y. In both
of the latter two cases we then invoke the state transformer gcd_s2 again.
This continues until x and y are equal, in which case x is returned as the
result.
There is a point of possible confusion here. The gcd_s2 in this code:
do putState (y, x)
gcd_s2
and in this code:
do putState (y, x - y)
gcd_s2
looks a bit like recursive calls to gcd_s2. This is the wrong way to think
about it! Instead, what this code is doing is combining two state transformers:
putState (y, x - y) (which has the type State GCDState ()) and gcd_s2
(which has type State GCDState Int) to make a single state transformer (of
type State GCDState Int). I'll dissect this in more detail below.
The getState state transformer wraps a state transformer function which takes
the current state, doesn't alter it, and returns it as a value. We wrote it as:
getState :: State GCDState GCDState
getState = State (\(x, y) -> ((x, y), (x, y)))
but it could be more generically written as:
getState :: State s s
getState = State (\st -> (st, st))
Recall that all state transformers have the form State (\st -> (val, st')),
where st represents the initial state, st' represents the final state, and
val represents the value returned from the state transformer. Here, the
initial state is identical to the final state, and the state is also the
returned value. That's why it's called getState; it gets the state and
returns it so it can be used by the rest of the code.
The function putState is not a state transformer; it's a function which
returns a state transformer given a GCDState value. The definition is:
putState :: GCDState -> State GCDState ()
putState (x', y') = State (\_ -> ((), (x', y')))
Again, it could be written more generically as:
putState :: GCDState -> State GCDState ()
putState s = State (\_ -> ((), s))
Given a GCDState value, putState returns a monadic value (state tranformer)
of type State GCDState (). This state transformer throws away the existing
state and replaces it with the state which was the argument to putState.
That's why putState is called putState: it puts its argument value (which is
a state) into the state being passed around from state transformer to state
transformer. It returns the unit value (()) because all putState does is
change the state; there is nothing to return, so the meaningless () value is
returned.
Let's look at the gcd_s2 function again, without the helper functions:
gcd_s2 :: State GCDState Int
gcd_s2 =
do (x, y) <- getState
case compare x y of
EQ -> return x
LT -> do putState (y, x)
gcd_s2
GT -> do putState (y, x - y)
gcd_s2
We can get more insight into how this works by rewriting gcd_s2 without the
do-notation (i.e. without syntactic sugar). That gives us this:
gcd_s2 :: State GCDState Int
gcd_s2 =
getState >>= (\(x, y) ->
case compare x y of
EQ -> return x
LT -> (putState (y, x) >> gcd_s2)
GT -> (putState (y, x - y) >> gcd_s2))
(If you don't understand how this desugaring works, you should re-read the earlier articles in the series.)
It's even more informative if we mark off all the state transformers that are
being combined into the final state transformer. We'll use the notation ${ ...
}$ to mark off each state transformer (this is not Haskell syntax).
-- WARNING: Not Haskell syntax!
gcd_s2 :: State GCDState Int
gcd_s2 =
${
${ getState }$ >>=
\(x, y) ->
${
case compare x y of
EQ -> ${ return x }$
LT -> ${ ${ putState (y, x) }$ >> ${ gcd_s2 }$ }$
GT -> ${ ${ putState (y, x - y) }$ >> ${ gcd_s2 }$ }$
}$
}$
From this we can see that
- The entire monadic value
gcd_s2is a state transformer. - It is composed of two state transformers:
getState- the
casestatement that is the right-hand side of the anonymous function starting with\(x, y) ->
- Each case of the
caseexpression contains one or more state transformers:- the
EQcase contains the state transformerreturn x - the
LTcase contains the combination of two state transformers:putState (y, x)gcd_s2
- the
GTcase contains the combination of two state transformers:putState (y, x - y)gcd_s2
- the
That's a lot of state transformers! The overall state transformer gcd_s2 is
constructed out of six smaller state transformers (some repeated), which are
combined to give bigger state transformers until gcd_s2 has been constructed.
And this is a simple example! Fortunately, once you understand what's going
on, you rarely have to think about things in this level of detail.
Let's see how the smaller state transformers are built up to give larger ones.
First off, consider the LT and GT cases of the case expression:
putState (y, x) >> gcd_s2
putState (y, x - y) >> gcd_s2
In both of these cases, the value on the left-hand side of the >> operator has
the type State GCDState () and the value on the right-hand side has the type
State GCDState Int. We use the >> operator instead of the >>= operator
because the return value of the putState state transformers has the unit type
(), which is unimportant (i.e. we can throw it away). What these compound
state transformers are doing is:
- changing the stored state;
- passing this stored state on to the
gcd_s2state transformer.
In other words, they are creating a new state transformer which is like the
gcd_s2 state transformer except that it does something to the state before
passing it to gcd_s2. For instance, in the first case, it flips the x and
y state values before passing the state on to gcd_s2. As I said above, this
is not a recursive call of a function, because gcd_s2 isn't a function.
It's more like a recursive data definition. For instance, consider this:
ints :: [Integer]
ints = 1 : ints
The value ints is defined in terms of itself, and similarly, the value
gcd_s2 is defined in terms of itself.
The other interesting part of the definition is this:
getState >>= (\(x, y) -> case compare x y of ...)
The left-hand side of this expression is a state transformer (state monadic
value) while the right-hand side is a state monadic function i.e. a function
which takes the state (x, y) as its argument and returns a new state
transformer (state monadic value), which is the case expression. What is
happening here is that getState is returning the state tuple (x, y) as its
return value (and not changing the state); this return value is unpacked into
the x and y values that the case expression sees. The case expression
uses these x and y values to determine which state transformer to use. For
a particular value of x and y, the overall state transformer gcd_s2 will
be a combination of getState and the state transformer selected from the
case statement.
A Sample Evaluation
Let's look at how this plays out in the evaluation of run_gcd_s2 1024 40,
which will evaluate to 8. This is going to be a bit hairy, but you should be
able to follow along given what you've already learned.
The expression:
run_gcd_s2 1024 40
reduces to:
fst (runState gcd_s2 (1024, 40))
Recall the definition of runState from last time:
runState :: State s a -> s -> (a, s)
runState (State f) init_st = f init_st
This could also be written more simply as:
runState :: State s a -> s -> (a, s)
runState (State f) = f
Adding some parentheses in the type signature, this becomes:
runState :: State s a -> (s -> (a, s))
runState (State f) = f
In words: runState takes a state transformer and extracts its corresponding
state transformer function, which, when applied to the initial state, yields a
tuple of the final return value and the final state. The fst call in our
expression just throws away the final state and returns the final return value,
so we don't have to concern ourselves with fst anymore. That means that what
we really have to evaluate is:
runState gcd_s2 (1024, 40)
Expanding out gcd_s2 gives this expression:
runState (getState >>= (\(x, y) -> case compare x y of ...)) (1024, 40)
Intuitively, what will happen here is that (1024, 40) will be the initial
state passed to the state transformer gcd_s2 (which is (getState >>= (\(x, y)
-> case compare x y of ...))). getState will extract the state (not changing
it) and will bind x to 1024 and y to 40, after which the case
statement will be evaluated and one of the three cases (EQ, LT, or GT)
will be chosen. In this case, x > y so the GT case will be chosen, and the
expression will reduce to:
runState (putState (40, 984) >> gcd_s2) (1024, 40)
Notice that the new state transformer is the state transformer to the right of
the GT clause of the case statement. Up to this point, the state hasn't
changed.
That was a bit hand-wavy, so I'm going to go through this last step in full
detail. Recall the definition of the >>= operator for state monads that we
derived in the previous article:
mv >>= g = State (\st ->
let (State ff) = mv
(y, st') = ff st
(State gg) = g y
in gg st')
Written in terms of runState (see the previous article), this becomes:
mv >>= g = State (\st ->
let (y, st') = runState mv st
in runState (g y) st')
The state transformer gcd_s2 is:
getState >>= (\(x, y) -> case compare x y of ...)
which becomes (with some name changes to avoid ambiguities):
State (\st ->
let (z, st') = runState getState st
in runState
((\(x'', y'') -> case compare x'' y'' of ...) z)
st')
The state st is just (x, y) in this case, so we can write this as:
State (\(x, y) ->
let (z, (x', y')) = runState getState (x, y)
in runState
((\(x'', y'') -> case compare x'' y'' of ...) z)
(x', y'))
Evaluating runState getState (x, y) gives the tuple ((x, y), (x, y)) (see
the definition above) so we have z = (x, y) and (x', y') = (x, y). This
gives us:
State (\(x, y) ->
runState
((\(x'', y'') -> case compare x'' y'' of ...) (x, y))
(x, y))
Simplifying:
State (\(x, y) ->
runState
(case compare x y of ...)
(x, y))
This is just a different way of writing gcd_s2. The expression runState
gcd_s2 extracts the function from inside the State constructor, so
runState gcd_s2 (1024, 40)
is the same as:
(\(x, y) ->
runState
(case compare x y of ...)
(x, y)) (1024, 40)
which simplifies to:
runState (case compare 1024 40 of ...) (1024, 40)
Let's expand out the case statement, substituting 1024 for x and 40 for
y:
runState
(case compare 1024 40 of
EQ -> return 1024
LT -> (putState (40, 1024) >> gcd_s2)
GT -> (putState (40, 984) >> gcd_s2))
(1024, 40)
The case statement will reduce to the GT clause in this case, giving us:
runState (putState (40, 984) >> gcd_s2) (1024, 40)
This was the result we got from our intuitive hand-wavy discussion above. So everything works! Hooray for rigor! ;-)
Since all subsequent steps follow a similar pattern, I'm going to skip a lot of
steps and just show you the essential points in the evaluation of the expression
from here on in. But in principle, every step could be evaluated rigorously
using the definition of >>= given above.
We now have to evaluate:
runState (putState (40, 984) >> gcd_s2) (1024, 40)
The putState state transformer will ignore the initial state (1024, 40) and
will instead make the state (40, 984), so this expression reduces to:
runState gcd_s2 (40, 984)
[Exercise for the reader: derive this rigorously.] We expand out gcd_s2 again
to give:
runState (getState >>= (\(x, y) -> case compare x y of ...)) (40, 984)
getState will bind x to 40 and y to 984. Since 40 < 984, the LT
case of the case statement will be chosen, and the expression will reduce to:
runState (putState (984, 40) >> gcd_s2) (40, 984)
This will reduce to:
runState gcd_s2 (984, 40)
Continuing along, we get:
runState gcd_s2 (904, 40)
--> runState gcd_s2 (864, 40)
and skipping a lot of similar steps we eventually arrive at:
--> runState gcd_s2 (64, 40)
--> runState gcd_s2 (24, 40)
--> runState gcd_s2 (40, 24)
--> runState gcd_s2 (16, 24)
--> runState gcd_s2 (24, 16)
--> runState gcd_s2 (8, 16)
--> runState gcd_s2 (16, 8)
--> runState gcd_s2 (8, 8)
--> (8, (8, 8))
And fst (8, (8, 8)) is 8, which is the GCD of 1024 and 40. Success!
That was a long way to go just to compute a GCD. The point was to see how state monads compute by chaining together state transformers. Once you understand this, using state monads is pretty straightforward.
The MonadState type class
There is a nifty type class called MonadState defined in the
module Control.Monad.State which has this definition:
class (Monad m) => MonadState s m | m -> s where
get :: m s
put :: s -> m ()
There is also a particular instance which is relevant to us:
instance MonadState s (State s) where
get = State (\s -> (s, s))
put s = State (\_ -> ((), s))
What this does is make it so that we don't have to define getState and
putState for our state monads, because they are identical to get and put.
So our GCD code can be re-written in a slightly simpler way:
gcd_s3 :: State GCDState Int
gcd_s3 =
do (x, y) <- get
case compare x y of
EQ -> return x
LT -> do put (y, x)
gcd_s3
GT -> do put (y, x - y)
gcd_s3
run_gcd_s3 :: Int -> Int -> Int
run_gcd_s3 x y = fst (runState gcd_s3 (x, y))
All that we've done here is substitute get for getState and put for
putState. Because of the instance declaration, any state monad is
automatically an instance of MonadState, so you can use get and put with
it.
The class definition:
class (Monad m) => MonadState s m | m -> s where
get :: m s
put :: s -> m ()
includes another functional dependency (we saw one of these in the articles on
error-handling monads). The | m -> s part means that the state type s is
uniquely determined by the monad m. This is easy to see in the instance
definition:
instance MonadState s (State s) where
get = State (\s -> (s, s))
put s = State (\_ -> ((), s))
Clearly, for the (State s) monad, the state type had better also be s or the
code won't make sense.
You might be wondering why get and put were defined as methods of a type
class rather than just as library functions i.e. like this:
get :: State s s
get = State (\s -> (s, s))
put :: s -> State s ()
put s = State (\_ -> ((), s))
In principle, this could have been done. However, defining get and put as
methods of a type class makes them more flexible. It turns out that the state
monad (State s) is not the only monad for which get and put can usefully
be defined. In particular, it's possible to combine monads together using what
are called monad transformers to get (for instance) a monad which does both
state manipulation and error handling. Such a monad would certainly want to
have its own get and put functions, but they would be slightly different
from the ones for the (State s) monad. Having get and put be methods of
the MonadState type class means that you can customize them for any monad for
which they make sense.
There is a simple but useful library function called modify which depends on
the MonadState type class. Its definition is:
modify :: (MonadState s m) => (s -> s) -> m ()
modify f =
do st <- get
put (f st)
[For fun:] We could define it more concisely as:
modify :: (MonadState s m) => (s -> s) -> m ()
modify f = get >>= (put . f)
What modify does is apply a function (of type (s -> s)) to the state,
putting the new state in place of the old one. We'll put it to good use below.
A Small Tweak
Here's a very small change to the run_gcd_s3 function:
run_gcd_s3 :: Int -> Int -> Int
run_gcd_s3 x y = evalState gcd_s3 (x, y)
Instead of fst (runState gcd_s3 (x, y)) we use evalState gcd_s3 (x, y).
This means the exact same thing, since evalState is defined as:
evalState :: State s a -> s -> a
evalState mv init_st = fst (runState mv init_st)
Since the evalState function is defined in the Control.Monad.State module,
it makes sense to use it.
Rolling your own while loop
At this point, we have written our GCD function as a sequence of state
transformers. Using get and put we can access or alter the state anywhere
we want, just like we could in imperative code in a language like C. However,
the code doesn't look like the corresponding C code. Just for fun, I'm going to
walk you through the process of defining a C-like while loop in Haskell.
We'll see that the code we end up with is an almost line-for-line copy of the C
code I showed you at the beginning of this article (modulo the obvious syntax
differences between C and Haskell).
A while loop is an inherently imperative construct. It takes two "arguments":
A test, which depends on the values of the state variables, and returns a boolean value;
A body, which is a state transformer acting on the state variables.
What's interesting is that, using state monads, we can write out the type
signature of while as a Haskell function very easily:
while :: (s -> Bool) -> State s () -> State s ()
The first argument to while is a function which takes a state value and
returns a boolean value indicating whether or not the loop body needs to be run
again. This is the test part of the while loop. The second argument is a
state transformer which corresponds to the body of the loop. It returns the
() (unit) type because while loops in C do not have a value; all they do is
change the state. The return value from while is a new state transformer
which executes the body of the loop until the test function returns False.
Here's the definition of while:
while :: (s -> Bool) -> State s () -> State s ()
while test body =
do st <- get
if (test st)
then do modify (execState body)
while test body
else return ()
The execState function, which we saw in the last article, takes a state
transformer and an initial state and returns the final state only. Here's its
definition:
execState :: State s a -> s -> s
execState mv init_st = snd (runState mv init_st)
So execState body (where body has the type State s ()) has the type s ->
s, which means it can be passed as an argument to the modify function to
modify the state. Essentially, what this code says is that you first test the
state to see if a condition applies; if so, you modify the state according to
the body state transformer and run while again; if not, you're done, so just
return ().
Think about it: we've defined a conditional as basic as while as a simple
function on state transformers! Most languages need to have while loops
built in, but Haskell doesn't. To me, this is all kinds of awesome.
Now let's rewrite the GCD state transformer in terms of while:
gcd_s4 :: State GCDState Int
gcd_s4 = do while (\(x, y) -> x /= y)
(do (x, y) <- get
if x < y
then put (x, (y - x))
else put ((x - y), y))
(x, _) <- get
return x
run_gcd_s4 :: Int -> Int -> Int
run_gcd_s4 x y = evalState gcd_s4 (x, y)
Notice that the test condition is a function from state to state, simply testing
whether the two components of the state are the same. The body of the while
loop is the inner do-expression, and after that the x component of the state
is extracted and returned.
This is already starting to look pretty close to the C code for the GCD function. With some helper functions, we can make it look closer still:
gcd_s5 :: State GCDState Int
gcd_s5 = do while (\(x, y) -> x /= y)
(do (x, y) <- get
if x < y
then putY (y - x)
else putX (x - y))
getX
where
putX :: Int -> State GCDState ()
putX i = do (_, y) <- get
put (i, y)
putY :: Int -> State GCDState ()
putY j = do (x, _) <- get
put (x, j)
getX :: State GCDState Int
getX = do (x, _) <- get
return x
run_gcd_s5 :: Int -> Int -> Int
run_gcd_s5 x y = evalState gcd_s5 (x, y)
All we've done here is define putX, putY, and getX as more specific
versions of put and get (more specific in the sense that they don't put or
get the entire state at once). The core of the state transformer:
gcd_s5 =
do while (\(x, y) -> x /= y)
(do (x, y) <- get
if x < y
then putY (y - x)
else putX (x - y))
getX
is very close to the C code:
int gcd(int x, int y) {
while (x != y) {
if (x < y) {
y = y - x;
} else {
x = x - y;
}
}
return x;
}
With the exception of the line do (x, y) <- get, which is needed to extract
the state components from the (hidden) state, every line in the Haskell code has
an exact counterpart in the C code. So you can do imperative programming in
Haskell in a manner quite similar to the way it's done in C.
Exercises
To test your understanding, try these exercises:
- Write a factorial function using state monads.
- Write a fibonacci function using state monads.
A fibonacci function is defined functionally for non-negative integers as:
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
Note that the core of each solution will be a state transformer (not a
function), and there will need to be a run_XXX function to invoke the state
transformer (presumably using runState).
Have fun!
Wrapping up
In the previous article and this one, I've shown you what state monads are, how they are defined, and how to use them. You can use state monads to simulate either local or global state. If you're simulating global state, the state transformers are defined at the top-level, whereas if you're simulating local state, they are local to the function. Either way, the principle is the same.
There are other ways to do imperative programming in Haskell. You can define
mutable variables in the IO monad; they are called IORefs. There is also a
monad called the ST monad which can define locally mutable variables called
STRefs. You can define mutable array types in both the IO and ST monads.
What's cool about all this is that in Haskell you can specify a wide variety of different computational strategies:
- pure functions
- functions which throw and catch exceptions
- functions that manipulate local or global state
- functions that do input/output (e.g. file or terminal)
or, using monad transformers, any combination of the above. This flexibility is what led Simon Peyton-Jones, one of the lead Haskell designers (and another person whose shoes I am not fit to shine), to declare "Haskell is the world's finest imperative language." In contrast, in most languages you don't have a choice: every function can do everything. This means that it's harder to prevent bugs in those languages. Monads allow us to say that a particular function has particular effects and no others, and this is one of the keys to their usefulness.
Next time
I need to take a break from blogging, but when I come back I'm going to talk
about the IO monad in more detail. See you then!
Comments