You are viewing mvanier

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

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

  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!

Comments

I'm glad you decided to post this YAHMT (yet another Haskell monad tutorial), because it's the best I've seen so far. Please come back soon and continue. Whatever you're doing for a living is less important than this ;-)

I 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?

Thanks!

Bartosz, thanks so much for your kind comments. I really appreciate hearing from people who like my tutorials. I really will get back to this, but right now my teaching schedule is occupying me full-time -- sorry! Writing monad tutorials is more fun than most of the teaching I do, so expect more in the future.

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!

Re: Thanks!

Mike, I posted a link to your tutorial in my wordpress blog, so you might see some hits coming from there.

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?

Re: Thanks!

Bartosz,

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/html/libraries/base-4.2.0.0/System-IO-Unsafe.html#v:unsafeInterleaveIO

Thank you + MOAR! (please)

I've read dozens (literally) of monad tutorials, but your series has given me some valuable new insights into the whole monad thing. I hope you write more when you have time. If you need inspiration, here are some things that I would like to know more about. But really, anything you write will probably be exactly what I need next.

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

Re: Thank you + MOAR! (please)

Thanks for your comments! I definitely plan to write about monad transformers at some point. They are a classic example of something that sounds much worse than they are. Mostly it just involves a lot of bookkeeping when creating the monad transformer to make sure everything works right. Using transformers is usually pretty straightforward (at least in the cases I've encountered). I'm not as clear about your second point, so if you want to add any details I might be able to come up with something eventually.

Re: Thank you + MOAR! (please)

The second point is a bit difficult to explain, but this question I posted to the beginners mailing list will give you an example of the type of thing that I mean:

http://article.gmane.org/gmane.comp.lang.haskell.beginners/6055

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.lang.haskell.beginners/6067

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 11

hey there I just wanted to comment your blog and say that I really enjoyed reading your blog post here. It was very informative and I also digg the way you write! Keep it up and I’ll be back to read more soon mate

Re: painter 11

Thanks!

(Anonymous)

sms

Excellent posting. Undoubtedly you are an expert of such writing topics. It is just the first time I went through your post and to tell the truth it succeeds in making me visit here now and then.And yes i have digg your site mvanier.livejournal.com .

Thank you

I really enjoyed reading your article specially State monads. It would be great if you can post some articles about about Monad transformer .

Re: Thank you

That is an excellent idea and it's likely that that will be the next article in the series.

Please continue your blog AND write a book

Your crystal-clear and well-written articles on Haskell have helped me (a newbie) to understand the language more than almost any other source.

('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.

Re: Please continue your blog AND write a book

Thanks so much! I will be continuing, hopefully early in the new year. I have a new baby, so life is hectic :-)

Actually, 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 :-)
Hi Mike,

I 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 :)
Thanks for the report! I've fixed the typo.

August 2010

S M T W T F S
1234567
891011121314
15161718192021
22232425262728
293031    
Powered by LiveJournal.com