Haskell/Understanding monads/State

From Wikibooks, open books for an open world
Jump to: navigation, search

If you have programmed in any other language before, you likely wrote some functions that "kept state". For those new to the concept, a state is one or more variables that are required to perform some computation but are not among the arguments of the relevant function. Object-oriented languages, like C++, suggest extensive use of state variables within objects in the form of member variables. Programs written in procedural languages, like C, typically use variables declared outside the current scope to keep track of state.

In Haskell, however, such techniques are not as straightforward to apply. They require mutable variables and imply functions will have hidden dependencies, which is at odds with Haskell's functional purity. Fortunately, in most cases it is possible to avoid such extra complications and keep track of state in a functionally pure way. We do so by passing the state information from one function to the next, thus making the hidden dependencies explicit. The State type is a tool crafted to make this process of threading state through functions more convenient. In this chapter, we will see how it can assist us in a typical problem involving state: generating pseudo-random numbers.

Pseudo-Random Numbers[edit]

Generating actual random numbers is far from easy. Computer programs almost always use pseudo-random numbers instead. They are called "pseudo" because they are not truly random. Rather, they are genererated by algorithms (the pseudo-random number generators) which take an initial state (commonly called the seed) and produce from it a sequence of numbers that have the appearance of being random.[1] Every time a pseudo-random number is requested, state somewhere must be updated, so that the generator can be ready for producing a fresh, different random number. Sequences of pseudo-random numbers can be replicated exactly if the initial seed and the generating algorithm are known.

Implementation in Haskell[edit]

Producing a pseudo-random number in most programming languages is very simple: there is a function somewhere in the libraries that provides a pseudo-random value (perhaps even a truly random one, depending on how it is implemented). Haskell has a similar one in the System.Random module from the random package:

GHCi> :m System.Random
GHCi> :t randomIO
randomIO :: Random a => IO a
GHCi> randomIO

randomIO is an IO action. It couldn't be otherwise, as it makes use of mutable state, which is kept out of reach from our Haskell programs. Thanks to this hidden dependency, the pseudo-random values it gives back can be different every time.

Example: Rolling Dice[edit]

randomRIO (1,6)

Suppose we are coding a game in which at some point we need an element of chance. In real-life games that is often obtained by means of dice. So, let's create a dice-throwing function. We'll use the IO function randomRIO, which allows us to specify a range from which the pseudo-random values will be taken. For a 6 die, the call will be randomRIO (1,6).

import Control.Monad
import System.Random

rollDiceIO :: IO (Int, Int)
rollDiceIO = liftM2 (,) (randomRIO (1,6)) (randomRIO (1,6))

That function rolls two dice. Here, liftM2 is used to make the non-monadic two-argument function (,) work within a monad. The (,) is the non-infix version of the tuple constructor. Thus, the two die rolls will be returned as a tuple in IO.

  1. Implement a function rollNDiceIO :: Int -> IO [Int] that, given an integer (a number of die rolls), returns a list of that number of pseudo-random integers between 1 and 6.

Getting Rid of IO[edit]

A disadvantage of randomIO is that it requires us to use IO and store our state outside the program, where we can't control what happens to it. We would rather only use I/O when there is an unavoidable reason to interact with the outside world.

To avoid bringing IO into play, we can build a local generator. The random and mkStdGen functions in System.Random allow us to generate tuples containing a pseudo-random number together with an updated generator to use the next time the function is called.

GHCi> :m System.Random
GHCi> let generator = mkStdGen 0           -- "0" is our seed
GHCi> :t generator
generator :: StdGen
GHCi> generator
1 1
GHCi> :t random
random :: (RandomGen g, Random a) => g -> (a, g)
GHCi> random generator :: (Int, StdGen)
(2092838931,1601120196 1655838864)


In random generator :: (Int, StdGen), we use the :: to introduce a type annotation, which is essentially a type signature that we can put in the middle of an expression. Here, we are saying that the expression to the right, random generator has type (Int, StdGen). It makes sense to use a type annotation here because, as we will discuss later, random can produce values of different types, so if we want it to give us an Int we'd better specify it in some way.

While we managed to avoid IO, there are new problems. First and foremost, if we want to use generator to get random numbers, the obvious definition...

GHCi> let randInt = fst . random $ generator :: Int
GHCi> randInt

... is useless. It will always give back the same value, 2092838931, as the same generator in the same state will be used every time. To solve that, we can take the second member of the tuple (that is, the new generator) and feed it to a new call to random:

GHCi> let (randInt, generator') = random generator :: (Int, StdGen)
GHCi> randInt                            -- Same value
GHCi> random generator' :: (Int, StdGen) -- Using new generator' returned from “random generator”
(-2143208520,439883729 1872071452)

That, of course, is clumsy and rather tedious, as we now need to deal with the fuss of carefully passing the generator around.

Dice without IO[edit]

We can re-do our dice throw with our new approach using the randomR function:

GHCi> randomR (1,6) (mkStdGen 0)
(6, 40014 40692)

The resulting tuple combines the result of throwing a single die with a new generator. A simple implementation for throwing two dice is then:

clumsyRollDice :: (Int, Int)
clumsyRollDice = (n, m)
        (n, g) = randomR (1,6) (mkStdGen 0)
        (m, _) = randomR (1,6) g
  1. Implement a function rollDice :: StdGen -> ((Int, Int), StdGen) that, given a generator, return a tuple with our random numbers as first element and the last generator as the second.

The implementation of clumsyRollDice works as an one-off, but we have to manually pass the generator g from one where clause to the other. This approach becomes increasingly cumbersome as our programs get more complex, which means we have more values to shift around. It is also error-prone: what if we pass one of the middle generators to the wrong line in the where clause?

What we really need is a way to automate the extraction of the second member of the tuple (i.e. the new generator) and feed it to a new call to random. This is where the State comes into the picture.

Introducing State[edit]


In this chapter we will use the state monad provided by the module Control.Monad.Trans.State of the transformers package. By reading Haskell code in the wild, you will soon meet Control.Monad.State, a module of the closely related mtl package. The differences between these two modules need not concern us at the moment; everything we discuss here also applies to the mtl variant.

The Haskell type State describes functions that consume a state and produce both a result and an updated state, which are given back in a tuple.

The state function is wrapped by a data type definition which comes along with a runState accessor so that pattern matching becomes unnecessary. For our current purposes, the State type might be defined as:

newtype State s a = State { runState :: s -> (a, s) }

Here, s is the type of the state, and a the type of the produced result. Calling the type State is arguably a bit of a misnomer because the wrapped value is not the state itself but a state processor.


Note that we defined the data type with the newtype keyword, rather than the usual data. newtype can be used only for types with just one constructor and just one field. It ensures that the trivial wrapping and unwrapping of the single field is eliminated by the compiler. For that reason, simple wrapper types such as State are usually defined with newtype. Would defining a synonym with type be enough in such cases? Not really, because type does not allow us to define instances for the new data type, which is what we are about to do...

Where did the State constructor go?[edit]

When you start using Control.Monad.Trans.State, you will quickly notice there is no State constructor available. That was the reason for the "for our current purposes" caveat a few paragraphs ago, when introducing the type. The transformers package implements the State type in a somewhat different way. The differences do not affect how we use or understand State; except that, instead of a State constructor, Control.Monad.Trans.State exports a state function,

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

which does the same job. As for why the implementation is not the obvious one we presented above, we will get back to that a few chapters down the road.

Instantiating the Monad[edit]

So far, all we have done was to wrap a function type and give it a name. There is another ingredient, however: State is a monad, and that gives us very handy ways of using it. Unlike the instances of Functor or Monad we have seen so far, State has two type parameters. Since the type class only allows one parametrised parameter, the last one, we have to indicate the other one, s, will be fixed.

instance Monad (State s) where

That means there are actually many different State monads, one for each possible type of state - State String, State Int, State SomeLargeDataStructure, and so forth. Naturally, we only need to write one implementation of return and (>>=); the methods will be able to deal with all choices of s.

The return function is implemented as:

return :: a -> State s a
return x = state ( \ st -> (x, st) )

Giving a value (x) to return produces a function which takes a state (st) and returns it unchanged, together with value we want to be returned. As a finishing step, the function is wrapped up with the state function.

Binding is a bit intricate:

(>>=) :: State s a -> (a -> State s b) -> State s b
pr >>= k = state $ \ st ->
   let (x, st') = runState pr st -- Running the first processor on st.
   in runState (k x) st'       -- Running the second processor on st'.

(>>=) is given a state processor (pr) and a function (k) that is used to create another processor from the result of the first one. The two processors are combined into a function that takes the initial state (st) and returns the second result and the third state (i.e. the output of the second processor). Overall, (>>=) here allows us to run two state processors in sequence, while allowing the result of the first stage to influence what happens in the second one.

Schematic representation of how bind creates a new state processor (pAB) from a state processor (pA) and a processor-making function (f). s1, s2 and s3 are states. v1 and v2 are values. pA, pB and pAB are state processors. The wrapping and unwrapping by state/runState is implicit.

One detail in the implementation is how runState is used to undo the State wrapping, so that we can reach the function that will be applied to the states. The type of runState pr, for instance, is s -> (s, a).

Setting and Accessing the State[edit]

The monad instance allows us to manipulate various state processors, but you may at this point wonder where exactly the original state comes from in the first place. That issue is handily dealt with by the function put:

put newState = state $ \_ -> ((), newState)

Given a state (the one we want to introduce), put generates a state processor which ignores whatever state it receives, and gives back the state we originally provided to put. Since we don't care about the result of this processor (all we want to do is to replace the state), the first element of the tuple will be (), the universal placeholder value.[2]

As a counterpart to put, there is get:

get = state $ \st -> (st, st)

The resulting state processor gives back the state st it is given in both as a result and as a state. That means the state will remain unchanged, and that a copy of it will be made available for us to manipulate.

Getting Values and State[edit]

As we have seen in the implementation of (>>=), runState is used to unwrap the State a b value to get the actual state processing function, which is then applied to some initial state. Other functions which are used in similar ways are evalState and execState. Given a State a b and an initial state, the function evalState will give back only the result value of the state processing, whereas execState will give back just the new state.

evalState :: State s a -> s -> a
evalState pr st = fst (runState pr st)

execState :: State s a -> s -> s
execState pr st = snd (runState pr st)

Dice and state[edit]

Time to use the State monad for our dice throw examples.

import Control.Monad.Trans.State
import System.Random

We want to generate Int dice throw results from a pseudo-random generator of type StdGen. Therefore, the type of our state processors will be State StdGen Int, which is equivalent to StdGen -> (Int, StdGen) bar the wrapping.

We can now implement a processor that, given a StdGen generator, produces a number between 1 and 6. Now, the type of randomR is:

-- The StdGen type we are using is an instance of RandomGen.
randomR :: (Random a, RandomGen g) => (a, a) -> g -> (a, g)

Doesn't it look familiar? If we assume a is Int and g is StdGen it becomes:

randomR (1, 6) :: StdGen -> (Int, StdGen)

We already have a state processing function! All that is missing is to wrap it with state:

rollDie :: State StdGen Int
rollDie = state $ randomR (1, 6)

For illustrative purposes, we can use get, put and do-notation to write rollDie in a very verbose way which displays explicitly each step of the state processing:

rollDie :: State StdGen Int
rollDie = do generator <- get
             let (value, newGenerator) = randomR (1,6) generator
             put newGenerator
             return value

Let's go through each of the steps:

  1. First, we take out the pseudo-random generator from the monadic context with <-, so that we can manipulate it.
  2. Then, we use the randomR function to produce an integer between 1 and 6 using the generator we took. We also store the new generator graciously returned by randomR.
  3. We then set the state to be the newGenerator using put, so that any further randomR in the do-block, or further on in a (>>=) chain, will use a different pseudo-random generator.
  4. Finally, we inject the result back into the State StdGen monad using return.

We can finally use our monadic die. As before, the initial generator state itself is produced by the mkStdGen function.

GHCi> evalState rollDie (mkStdGen 0)

Why have we involved monads and built such an intricate framework only to do exactly what fst $ randomR (1,6) already does? Well, consider the following function:

rollDice :: State StdGen (Int, Int)
rollDice = liftM2 (,) rollDie rollDie

We obtain a function producing two pseudo-random numbers in a tuple. Note that these are in general different:

GHCi> evalState rollDice (mkStdGen 666)

Under the hood, state is being passed through (>>=) from one rollDie computation to the other. Doing that was previously very clunky using randomR (1,6) alone because we had to pass state manually. Now, the monad instance is taking care of that for us. Assuming we know how to use the lifting functions, constructing intricate combinations of pseudo-random numbers (tuples, lists, whatever) has suddenly become much easier.

  1. Similarly to what was done for rollNDiceIO, implement a function rollNDice :: Int -> State StdGen [Int] that, given an integer, returns a list with that number of pseudo-random integers between 1 and 6.
  2. Write an instance of Functor for State s. Your final answer should not use anything that mentions Monad in its type (that is, return, (>>=), etc.). Then, explain in a few words what the fmap you wrote does.(Hint: If you get stuck, have another look at the comments about liftM at the very end of Understanding monads.)
  3. Besides put and get, there are also
    modify :: (s -> s) -> State s ()
    which modifies the current state using a function, and
    gets :: (s -> a) -> State s a
    which produces a modified copy of the state while leaving the state itself unchanged. Write implementations for them.

Pseudo-random values of different types[edit]

Until now, we have used only Int as type of the value produced by the pseudo-random generator. However, looking at the type of randomR shows we are not restricted to Int. It can generate values of any type in the Random class from System.Random. There already are instances for Int, Char, Integer, Bool, Double and Float, so you can immediately generate any of those.

Because State StdGen is "agnostic" in regard to the type of the pseudo-random value it produces, we can write a similarly "agnostic" function that provides a pseudo-random value of unspecified type (as long as it is an instance of Random):

getRandom :: Random a => State StdGen a
getRandom = state $ random generator

Compared to rollDie, this function does not specify the Int type in its signature and uses random instead of randomR; otherwise, it is just the same. getRandom can be used for any instance of Random:

GHCi> evalState getRandom (mkStdGen 0) :: Bool
GHCi> evalState getRandom (mkStdGen 0) :: Char
GHCi> evalState getRandom (mkStdGen 0) :: Double
GHCi> evalState getRandom (mkStdGen 0) :: Integer

Indeed, it becomes quite easy to conjure all these at once:

someTypes :: State StdGen (Int, Float, Char)
someTypes = liftM3 getRandom getRandom getRandom

allTypes :: State StdGen (Int, Float, Char, Integer, Double, Bool, Int)
allTypes = liftM (,,,,,,) getRandom
                     `ap` getRandom
                     `ap` getRandom
                     `ap` getRandom
                     `ap` getRandom
                     `ap` getRandom
                     `ap` getRandom

For allTypes, since there is no liftM7 (the standard libraries only go to liftM5) we have used the ap function from Control.Monad instead. ap fits multiple computations into an application of a multiple argument function, which here is the (lifted) 7-element-tuple constructor. To understand ap further, look at its signature:

ap :: (Monad m) => m (a -> b) -> m a -> m b

Remember then that the type variable a in Haskell can be replaced by a function type as well as a regular value one, and compare to:

GHCi>:t liftM (,,,,,,) getRandom
liftM (,,,,,) getRandom :: (Random a1) =>
                           State StdGen (b -> c -> d -> e -> f -> g
                               -> (a1, b, c, d, e, f, g))

The monad m obviously becomes State StdGen, while ap's first argument is a function b -> c -> d -> e -> f -> g -> (a1, b, c, d, e, f, g). Applying ap over and over (in this case 6 times), we finally get to the point where b is an actual value (in our case, a 7-element tuple), not another function. To sum it up, ap applies a function-in-a-monad to a monadic value (compare with liftM/fmap, which applies a function not in a monad to a monadic value).

So much for understanding the implementation. Function allTypes provides pseudo-random values for all default instances of Random; an additional Int is inserted at the end to prove that the generator is not the same, as the two Ints will be different.

GHCi> evalState allTypes (mkStdGen 0)
  1. If you are not convinced that State is worth using, try to implement a function equivalent to evalState allTypes without making use of monads, i.e. with an approach similar to clumsyRollDice above.


  1. A common source of seeds is the current date and time as given by the internal clock of the computer. Assuming the clock is functioning correctly, it can provide unique seeds suitable for most day-to-day needs (as opposed to applications which demand high-quality randomness, as in cryptography or statistics).
  2. The technical term for both () and its type is unit.