Haskell/Understanding monads/State
If you programmed in any language before, chances are you wrote some functions that "kept state". In case you did not encounter the concept before, a state is one or more variables that are required to perform some computation, but are not among the arguments of the relevant function. In fact, objectoriented languages like C++ make extensive usage of state variables in objects in the form of member variables. Procedural languages like C use variables declared outside the current scope to keep track of state. In Haskell, however, such techniques can not be applied in a straightforward way, as they require mutable variables and thus clash with the default expectation of functional purity. We can very often keep track of state by passing parameters from function to function or by pattern matching of various sorts, but in some cases it is appropriate to find a more general or convenient solution. We will consider the common example of generation of pseudorandom numbers with pure functions, and find out how the State
monad can make such a task easier.
PseudoRandom Numbers[edit]
Generating actual random numbers is a very complicated subject; we will consider pseudorandom numbers. They are called "pseudo" because they are not really random, they only look like it. Starting from an initial state (commonly called the seed), pseudorandom number generators produce a sequence of numbers that have the appearance of being random.
Every time a pseudorandom number is requested, a global state is updated: that's the part we have problems with in Haskell, since it is a side effect from the point of view of the function requesting the number. Sequences of pseudorandom numbers can be replicated exactly if the initial seed and the algorithm is known.
Implementation in Haskell[edit]
Producing a pseudorandom number in most programming languages is very simple: there is usually a function, such as C or C++'s rand()
, that provides a pseudorandom value (or a random one, depending on the implementation). Haskell has a similar one in the System.Random
module:
> :m System.Random > :t randomIO randomIO :: Random a => IO a > randomIO 1557093684
Obviously, save eerie coincidences, the value you will obtain will be different. A disadvantage of randomIO
is that it requires us to utilise the IO
monad, which breaks purity requirements. Usage of the IO
monad is dictated by the process of updating the global generator state, so that the next time we call randomIO
the value will be different.
Implementation with Functional Purity[edit]
In general, we do not want to use the IO
monad if we can help it, because of the loss of guarantees on no side effects and functional purity. Indeed, we can build a local generator (as opposed to the global generator, invisible to us, that randomIO
uses) using mkStdGen
, and use it as seed for the random
function, which in turn returns a tuple with the pseudorandom number that we want and the generator to use the next time:
> :m System.Random > let generator = mkStdGen 0  "0" is our seed > generator 1 1 > random generator :: (Int, StdGen) (2092838931,1601120196 1655838864)
While we have now regained functional purity, there are new problems to bother us. First and foremost, if we want to use generator
to get random numbers, the obvious definition...
> let randInt = fst . random $ generator :: Int > randInt 2092838931
...is useless, as it will always give back the same value, 2092838931
, no matter how many times random
is called, for the same generator is always used. Of course we can take the second member of the tuple (i.e. the new generator) and feed it to a new call to random
:
> let (randInt, generator') = random generator :: (Int, StdGen) > randInt  Same value 2092838931 > random generator' :: (Int, StdGen)  Using new generator' returned from “random generator” (2143208520,439883729 1872071452)
That, however, keeps us from having a function which simply gives back a new value, without the fuss of having to pass the generator around. 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
; and that is where the State
monad comes into the picture.
Definition of the State Monad[edit]
Note
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
is in essence a function that consumes state, and produces a result and the state after the result has been extracted. The 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 definition is equivalent to:
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. The name State
for the type is arguably a bit of a misnomer, as the wrapped value is not the state itself but a state processor.
Before You Ask...[edit]
What in the world did we mean by "for our current purposes" two paragraphs above? The subtlety is that the transformers
package implements the State
type in a somewhat different way. The differences do not affect how we use or understand State
; as a consequence of them, however, Control.Monad.Trans.State
does not export a State
constructor. Rather, there is 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.
newtype[edit]
You will also have noticed 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 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
. One might ask whether defining a synonym with type
would be enough in such cases. type
, however, does not allow us to define instances for the new data type, which is what we are about to do...
Instantiating the Monad[edit]
Note also that, in contrast to the monads we have met thus far, State
has two type parameters. This means that, when we instantiate the monad, we are actually leaving the parameter for the state type:
instance Monad (State s) where
This means that the "real" monad could be State String
, State Int
, or State SomeLargeDataStructure
, but not State
on its own.
The return
function is implemented as:
return :: a > State s a return x = state ( \st > (x, st) )
In words, giving a value to return
produces a function, wrapped in the State
constructor: this function takes a state value, and returns it unchanged as the second member of a tuple, together with the specified result value.
Binding is a bit intricate:
(>>=) :: State s a > (a > State s b) > State s b processor >>= processorGenerator = state $ \st > let (x, st') = runState processor st in runState (processorGenerator x) st'
The idea is that, given a state processor and a function that can generate another processor given the result of the first one, these two processors are combined to obtain a function that takes the initial state, and returns the second result and state (i.e. after the second function has processed them).
The diagram shows this schematically, for a slightly different, but equivalent form of the ">>=" (bind) function, given below (where wpA and wpAB are wrapped versions of pA and pAB).
 pAB = s1 > pA > (v2,s2) > pB > (v3,s3) wpA >>= f = wpAB where wpAB = state $ \s1 > let pA = runState wpA (v2, s2) = pA s1 pB = runState $ f v2 (v3,s3) = pB s2 in (v3,s3)
Setting and Accessing the State[edit]
The monad instantiation 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. State s
is also an instance of the MonadState
class, which provides two additional functions:
put newState = state $ \_ > ((), newState)
This function will generate a state processor given a state. The processor's input will be disregarded, and the output will be a tuple carrying the state we provided. Since we do not care about the result (we are discarding the input, after all), the first element of the tuple will be, so to say, "null".^{[1]}
The specular operation is to read the state. This is accomplished by get
:
get = state $ \st > (st, st)
The resulting state processor is going to produce the input st
in both positions of the output tuple  that is, both as a result and as a state, so that it may be bound to other processors.
Getting Values and State[edit]
From the definition of State
, we know that runState
is an accessor to apply to a State a b
value to get the stateprocessing function; this function, given an initial state, will return the extracted value and the new state. Other similar, useful functions are evalState
and execState
, which work in a very similar fashion.
Function evalState
, given a State a b
and an initial state, will return the extracted value only, whereas execState
will return only the new state; it is possibly easiest to remember them as defined as:
evalState :: State s a > s > a evalState processor st = fst ( runState processor st ) execState :: State s a > s > s execState processor st = snd ( runState processor st )
Example: Rolling Dice[edit]
Suppose we are coding a game in which at some point we need an element of chance. In reallife games that is often obtained by means of dice, which we will now try to simulate with Haskell code. For starters, we will consider the result of throwing two dice: to do that, we resort to the function randomR
, which allows to specify an interval from which the pseudorandom values will be taken; in the case of a die, it is randomR (1,6)
.
In case we are willing to use the IO
monad, the implementation is quite simple, using the IO
version of randomR
:
import Control.Monad import System.Random rollDiceIO :: IO (Int, Int) rollDiceIO = liftM2 (,) (randomRIO (1,6)) (randomRIO (1,6))
Here, liftM2
is used to make the nonmonadic twoargument function (,)
work within a monad, so that the two numbers will be returned (in IO
) as a tuple.
Exercises 


Getting Rid of the IO
Monad[edit]
Now, suppose that for any reason we do not want to use the IO
monad: we might want the function to stay pure, or need a sequence of numbers that is the same in every run, for repeatability.
To do that, we can produce a generator using the mkStdGen
function in the System.Random
library:
> mkStdGen 0 1 1
The argument to mkStdGen
is an Int
that functions as a seed. With that, we can generate a pseudorandom integer number in the interval between 1 and 6 with:
> randomR (1,6) (mkStdGen 0) (6,40014 40692)
We obtained a tuple with the result of the dice throw (6) and the new generator (40014 40692). A simple implementation that produces a tuple of two pseudorandom integers is then:
clumsyRollDice :: (Int, Int) clumsyRollDice = (n, m) where (n, g) = randomR (1,6) (mkStdGen 0) (m, _) = randomR (1,6) g
When we run the function, we get:
> clumsyRollDice (6, 6)
The implementation of clumsyRollDice
works, but we have to manually write the passing of generator g
from one where
clause to the other. This is pretty easy now, but will become increasingly cumbersome if we want to produce large sets of pseudorandom numbers. It is also errorprone: what if we pass one of the middle generators to the wrong line in the where
clause?
Exercises 


Introducing State
[edit]
We will now try to solve the clumsiness of the previous approach introducing the State StdGen
monad. For convenience, we give it a name with a type synonym:
import Control.Monad.Trans.State import System.Random type GeneratorState = State StdGen
Remember, however, that a GeneratorState Int
is in essence a StdGen > (Int, StdGen)
function, so it is not really the generator state, but a processor of the generator state. The generator state itself is produced by the mkStdGen
function. Note that GeneratorState
does not specify what type of values we are going to extract, only the type of the state.
We can now produce a function that, given a StdGen
generator, outputs a number between 1 and 6:
rollDie :: GeneratorState Int rollDie = do generator < get let (value, newGenerator) = randomR (1,6) generator put newGenerator return value
The do
notation is in this case much more readable; let's go through each of the steps:
 First, we take out the pseudorandom generator with
<
in conjunction withget
.get
overwrites the monadic value (The 'a' in 'm a') with the state, and thus generator is bound to the state. (If in doubt, recall the definition ofget
and>>=
above).  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 byrandomR
.  We then set the state to be the
newGenerator
using theput
function, so that the next call will use a different pseudorandom generator;  Finally, we inject the result into the
GeneratorState
monad usingreturn
.
We can finally use our monadic die:
> evalState rollDie (mkStdGen 0) 6
At this point, a legitimate question is why we have involved monads and built such an intricate framework only to do exactly what fst $ randomR (1,6)
does. The answer is illustrated by the following function:
rollDice :: GeneratorState (Int, Int) rollDice = liftM2 (,) rollDie rollDie
We obtain a function producing two pseudorandom numbers in a tuple. Note that these are in general different:
> evalState rollDice (mkStdGen 666) (6,1)
That is because, under the hood, the monads are passing state to each other. This used to be very clunky using randomR (1,6)
, because we had to pass state manually; now, the monad is taking care of that for us. Assuming we know how to use the lifting functions, constructing intricate combinations of pseudorandom numbers (tuples, lists, whatever) has suddenly become much easier.
Exercises 


Pseudorandom values of different types[edit]
Until now, absorbed in the die example, we considered only Int
as the type of the produced pseudorandom number. However, already when we defined the GeneratorState
monad, we noticed that it did not specify anything about the type of the returned value. In fact, there is one implicit assumption about it, and that is that we can produce values of such a type with a call to random
.
Values that can be produced by random
and similar function are of types that are instances of the Random
class (capitalised). There are default implementations for Int
, Char
, Integer
, Bool
, Double
and Float
, so you can immediately generate any of those.
Since we noticed already that the GeneratorState
is "agnostic" in regard to the type of the pseudorandom value it produces, we can write down a similarly "agnostic" function, analogous to rollDie
, that provides a pseudorandom value of unspecified type (as long as it is an instance of Random
):
getRandom :: Random a => GeneratorState a getRandom = do generator < get let (value, newGenerator) = random generator put newGenerator return value
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. What is notable is that getRandom
can be used for any instance of Random
:
> evalState getRandom (mkStdGen 0) :: Bool True > evalState getRandom (mkStdGen 0) :: Char '\64685' > evalState getRandom (mkStdGen 0) :: Double 0.9872770354820595 > evalState getRandom (mkStdGen 0) :: Integer 2092838931
Indeed, it becomes quite easy to conjure all these at once:
allTypes :: GeneratorState (Int, Float, Char, Integer, Double, Bool, Int) allTypes = liftM (,,,,,,) getRandom `ap` getRandom `ap` getRandom `ap` getRandom `ap` getRandom `ap` getRandom `ap` getRandom
Here we are forced to used the ap
function, defined in Control.Monad
, since there exists no liftM7
. As you can see, its effect is to fit multiple computations into an application of the (lifted) 7elementtuple constructor, (,,,,,,)
. To understand what ap
does, look at its signature:
>:type ap ap :: (Monad m) => m (a > b) > m a > m b
remember then that type a
in Haskell can be a function as well as a value, and compare to:
>:type liftM (,,,,,,) getRandom liftM (,,,,,) getRandom :: (Random a1) => State StdGen (b > c > d > e > f > (a1, b, c, d, e, f))
The monad m
is obviously State StdGen
(which we "nicknamed" GeneratorState
), while ap
's first argument is function b > c > d > e > f > (a1, b, c, d, e, f)
. 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 7element tuple), not another function. To sum it up, ap
applies a functioninamonad to a monadic value (compare with liftM
, which applies a function not in a monad to a monadic value).
So much for understanding the implementation. Function allTypes
provides pseudorandom 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 Int
s will be different.
> evalState allTypes (mkStdGen 0) (2092838931,9.953678e4,'\825586',868192881,0.4188001483955421,False,316817438)
Exercises 


Notes[edit]
 ↑ The technical term for the type of
()
is unit.