# 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

1. The entire monadic value `gcd_s2` is a state transformer.
2. It is composed of two state transformers:
1. `getState`
2. the `case` statement that is the right-hand side of the anonymous function starting with `\(x, y) ->`
3. Each case of the `case` expression contains one or more state transformers:
1. the `EQ` case contains the state transformer `return x`
2. the `LT` case contains the combination of two state transformers:
1. `putState (y, x)`
2. `gcd_s2`
3. the `GT` case contains the combination of two state transformers:
1. `putState (y, x - y)`
2. `gcd_s2`

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:

1. changing the stored state;
2. 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":

1. A test, which depends on the values of the state variables, and returns a boolean value;

2. 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:

1. Write a factorial function using state monads.
2. 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:

1. pure functions
2. functions which throw and catch exceptions
3. functions that manipulate local or global state
4. 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!

• #### Yet Another Monad Tutorial (part 7: state monads)

In this article we'll look at a very interesting class of monads: state monads. The State monad Up to this point, our approach has consisted…

• #### Yet Another Monad Tutorial (part 6: more on error-handling monads)

In the previous article we discussed error-handling strategies in Haskell and derived the Either e monad for structured error handling. In this…

• #### Yet Another Monad Tutorial (part 5: error-handling monads)

In the previous article we showed how to derive and use the Maybe and list monads. In this article and the next we're going to look at how to use…

• #### Error

Anonymous comments are disabled in this journal

default userpic