### 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 `Int`

s), 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_s2`

is a state transformer. - It is composed of two state transformers:
`getState`

- the
`case`

statement that is the right-hand side of the anonymous function starting with`\(x, y) ->`

- Each case of the
`case`

expression contains one or more state transformers:- the
`EQ`

case contains the state transformer`return x`

- the
`LT`

case contains the combination of two state transformers:`putState (y, x)`

`gcd_s2`

- the
`GT`

case 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_s2`

state 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 `IORef`

s. There is also a
monad called the `ST`

monad which can define locally mutable variables called
`STRef`

s. 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!

bartoszI wonder if you could digress, just a little bit, into category theory to give some insight into monads as functors and all this lifting business. I understand a functor that lifts a function on some type to lists of that type. I also understand the list monad. But how are those two related?

mvanierThanks!As for category theory, I'm not an expert (yet, anyway). Every monad (not just the list monad) is also a functor because functors define a map-like function and the monadic bind and return functions can be expressed in terms of three functions called map, join, and unit. Unit is just return with a different name, map is the map from functors, and join is something else. This is actually the standard way to describe monads in category theory texts; sometimes they are called "triples" because there are three characteristic functions. It's actually quite easy to derive the monadic bind operator from map, join and unit, and I may write that up sometime.

However, I stand by the statement I made in the first installment of this series: you don't need to know category theory to understand Haskell monads. Sure, it's nice and might provide a good framework, but it isn't essential.

Thanks again for your input!

bartoszRe: Thanks!I know the facts about functors and monads, but I'd like to develop better intuitive understanding. For instance, your explanation of operator >>= in terms of function composition was an eye-opener for me. Once I got that, the rest just followed.

BTW, what's a good way of thinking about side effects. Do they, conceptually, happen at the end of the do block? What if you have two different side-effects monads and execute two do blocks, one for each monad. Can their side effects interleave?

mvanierRe: Thanks!Thanks for the promotion! ;-) I'm really glad you like my approach.

I want to defer a full explanation of your question for my next blog post (about the IO monad) as there are a bunch of subtleties. The critical thing is that all operations occur in the correct sequence. If you have two do blocks in the IO monad, then they are both are executing inside another do block (i.e. in the IO monad, whether or not there is an actual do block); this means that they happen in sequence (no interleaving). If you want to execute an IO action outside of the IO monad there is unsafeInterleaveIO which can indeed interleave IO actions (and bad things can happen if you don't know what you're doing). See, for reference:

http://haskell.org/ghc/docs/6.12.1/h

mhwombatThank you + MOAR! (please)- Monad transformers. I'm doing some stuff with RandT right now, and if it hadn't been for the folks on beginners-haskell, I never would have figured out how to use it. I've got it working, but I probably only understand 80% of what I'm doing.

- Working with multiple monads at once. For example, I experimented with having a record structure with components that are monads, and the record as a whole was a monad too. I ran into some difficulties with that approach, but I wasn't sure whether that was because of my lack of knowledge, or because what I was trying to do was A Bad Idea.

mvanierRe: Thank you + MOAR! (please)mhwombatRe: Thank you + MOAR! (please)http://article.gmane.org/gmane.comp.lan

I got this excellent reply from Brent Yorgey, which solved that problem and showed me a better approach (using an adapter) to accomplish what I needed

http://article.gmane.org/gmane.comp.lan

That particular problem is sorted now, but perhaps it gives you an idea of the type of thing that has given me problems. But as I said before, whatever you write next will probably be just what I need to read.

(Anonymous)painter 11mvanierRe: painter 11(Anonymous)smsmukesh tiwariThank youmvanierRe: Thank youfitzrovianPlease continue your blog AND write a book('Learn You a Haskell for Great Good' has been equally helpful to me, but this is pitched at a less advanced level than your blog. However, I repeatedly read your articles on Monads before I read LYAHFGG.)

I'd love you to resume your blog and perhaps even write a book on Haskell because you understand the language profoundly and write so cogently.

mvanierRe: Please continue your blog AND write a bookActually, there are many parts of Haskell that I don't fully understand yet. But I do think I'm good at explaining the parts that I do understand, and I'm glad you feel the same way. It also motivates me to learn more about my weak areas so I can blog about them :-)

ext_1732116I found a small typo in the section explaining the MonadState type class:

put :: s -> State s ()

put :: State (\_ -> ((), s))

should be:

put :: s -> State s ()

put s =State (\_ -> ((), s))Additionally, i wanted to ask whether a function like gcd_s4 can considered to be imperative? In a language like C it was always easy to distinguish between imperative and recurisve functions.

I found your monad tutorial series a great pleasure to read and remain hoping for a continuation :)

mvanier