Using the Haskell State Monad

There are lots of tutorials on how to use the state monad in Haskell. A lot of them are out of date, or confusing, even worse the code that you type in does not work. You are then sent on an endless googling round to actually work out what is going on. For example, how exactly does the constructor work? Should I write state blah or State $ blah A good resource that I have been using recently is the Haskell Wiki book¹, another good resource to try is What I wish I knew when learning haskell. I assume that by the time somebody reads this post all of what I have written will be out of date, because they have found yet another way to factor the dependencies of the various type classes involved.

You have to make some choices. As far as I can work out in 2021, using the mtl library is the way to go. It seems to be easier to use. There are other choice, but I do not really understand what the different options give you.

The important thing about the state monad is that it should take code like this

import System.Random

threeCoins :: StdGen -> (Bool, Bool, Bool)  
threeCoins gen =   
    let (firstCoin, newGen) = random gen  
        (secondCoin, newGen') = random newGen  
        (thirdCoin, newGen'') = random newGen'  
    in  (firstCoin, secondCoin, thirdCoin)  

threeCoinsDemo =
  threeCoins (mkStdGen 21)

and turn it into code that looks like this

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

randomSt :: (RandomGen g, Random  a) => State g a
randomSt = state random 

threeCoinsState :: State StdGen (Bool, Bool , Bool)
threeCoinsState = do
  a <- randomSt 
  b <- randomSt
  c <- randomSt
  return (a,b,c)

Most monads do not do anything on their own, they are just sequences of actions. You need to do something to make those actions happen. The required magic for the state monad is runState. If you do runState threeCoinsState (mkStdGen 21) then you get:

((True,False,False),StdGen {unStdGen = SMGen 5638754522534429640 489215147674969543})

or if we do not want to see the state of the random number generator then we can do evalState threeCoinsState (mkStdGen 21) which equals

(True,False,False)

What if we want a list of random numbers? Well we can use the magic of the do notation. The type annotations inside the function are optional, and are just there to make the code more readable. It took me a long time to actually get this code working, mostly because I did not trust Haskell to get the types correct.

coinList :: Integer -> State StdGen [Bool]
coinList 0 = return []
coinList n =
  do
    a <- randomSt  :: State StdGen Bool
    rest <- coinList (n - 1)  :: State StdGen [Bool]
    return (a : rest)

So what is going on? When you have a type State StdGen Bool one way of thinking about the elements of the type is that they are functions:

StdGen -> (Bool, StdGen)

It takes a random number state, and produces a Boolean value and a new random number state. This is much like the random function in System.Random:

:t random
random :: (Random a, RandomGen g) => g -> (a, g)

The random function takes a random number state g and returns a pair that contains a value a and a new random state. If you want, for example, get a random Boolean value then you have to force the type:

random (mkStdGen 21) :: (Bool, StdGen)
(True,StdGen {unStdGen = SMGen 4660324227184490554 489215147674969543})

So what is going on with

randomSt :: (RandomGen g, Random  a) => State g a
randomSt = state random 

We are using the state function from mtl. This has the type (s -> (a, s)) -> m a. It takes a function, such as random and puts it into the Monad. If you are using a 2021 version of mtl then doing things like State $ random just won’t work.

To really understand how a monad works you need to understand how the bind operator (=<<) :: Monad m => (a -> m b) -> m a -> m b actually works. You will find plenty of tutorials on the web. The reason that you want to use the state monad is to avoid all the plumbing and write clean looking code using the do notation.

Let’s write two equivalent functions:

oneCoin :: State StdGen Bool
oneCoin =
  do
    v <- randomSt
    return value

oneCoinEquiv :: State StdGen Bool
oneCoinEquiv =  randomSt

Running these two gives you the same first runState oneCoin (mkStdGen 21)

(True,StdGen {unStdGen = SMGen 4660324227184490554 489215147674969543})

and then runState oneCoinEquiv (mkStdGen 21)

(True,StdGen {unStdGen = SMGen 4660324227184490554 489215147674969543})

The function randomSt takes the current state and produces state which is a pair containing the new random state and the actual value. It is all wrapped up in the state monad. Doing

v <- randomSt

Inside a do block binds the random value to v, but because of the way do blocks are transformed the state is transformed around. If you really want to understand what is going on, then you should go find some Haskell tutorial on desugaring the do notation. It is like lots of things in programming and mathematics. It is boring reading some explanation; you learn much more by working things out yourself.

Finally, the point of this (supposedly short) post. What is going on with

coinList :: Integer -> State StdGen [Bool]
coinList 0 = return []
coinList n =
  do
    a <- randomSt  
    rest <- coinList (n - 1)  
    return (a : rest)

The state type has two components, a state StdGen and the return type [Bool] which is a list of Boolean values. If you don’t trust the type system to work everything out then you end up writing some pretty convoluted code, which I won’t repeat here. The line a <- randomSt extracts a random Boolean value. We know that it is a Boolean value because of the expression return (a : rest) and the return type [Bool]. In the expression rest <- coinList (n - 1) we extract from expression coinList (n - 1) a value of type [Bool] because of the type of the whole function and the fact that rest also appears in return (a : rest). It was honestly a surprise to me that you could have a with the type Bool and rest with the type [Bool]. On reflection is it no more surprising that in

threeCoinsState :: State StdGen (Bool, Bool , Bool)
threeCoinsState = do
  a <- randomSt :: State StdGen Bool 
  b <- randomSt
  c <- randomSt
  return (a,b,c)

a, b and c are of type Bool while the whole return type is (Bool, Bool, Bool).

None of this is really magic, but often people first meet the do notation when they are doing IO. The problem with examples using IO is that everything stays in same type². The three coins example is easy to grasp, as long as you don’t think about it too much. The full type of =<< is Monad m => (a -> m b) -> m a -> m b where a and b can be different. You have to live inside the same monad m, but you can wrap different types inside the monad. So this means it is perfectly fine to have the types State StdGen Bool and State StdGen [Bool] in the same do block.