• previous -- Making types: newtype
• table of contents
• next -- Random numbers

Haskell for Hobos -- the "State" monad

This ends up being somewhat out of order, because I have not yet talked about monads, but I'll try to make this a preview of coming attractions in that regard.

What I am going to do is to try to follow along with the book LYAH in chapter 14 (For a Few Monads More) on page 316.
He shows the following definition:

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

A brief comment on the above line of code. Here we see a State type being defined that simply wraps a function called "runState". The reason for that is that Monad is a typeclass, and we can only get this function set up as a Monad if it is a type. Once it is a type we can indicate that it participates in the Monad typeclass (and we will write some "instance" code to implement the Monad "bind (>==)" operator. Actually we won't write that code, someone else did, we just want to find out how to play the Monad game with our State type.

We have companionship and plenty of help

• State monad from first principles
• State: a tutorial for the confused
• Reddit: get into State Monad
• Demystifying the Haskell State monad
• Control.Monad.State.Lazy

A case study -- LYAH, chapter 14

Consider a function with the following type signature:

s -> (a, s)

Next consider that the function takes "s" as an input and yields the new state wrapped in a tuple. Chaining functions of this sort is exactly what Monads were created to take care of.

On pages 314-315, as a sort of warmup, the book introduces a stack as an example of stateful computation. A stack is implemented as a list of Int values.

I put his code together and got it to run as follows:

type Stack = [Int]

pop :: Stack -> (Int, Stack)
pop (x:xs) = (x, xs)
pop [] = (0, [])

push :: Int -> Stack -> ((), Stack)
push a xs = ((), a:xs)

stackManip :: Stack -> (Int, Stack)
stackManip stack = let
    ((), new1) = push 3 stack
    (a, new2) = pop new1
    in pop new2

(xx, st0) = push 99 []
result = stackManip st0

main = putStrLn $ show result

Now let's try it using the code in LYAH on page 317 --

import Control.Monad.State

pop :: State Stack Int
pop = state $ \(x:xs) -> (x,xs)

push :: Int -> State Stack ()
push a = state $ \xs -> ((), a:xs)

manip :: State Stack Int
manip = do
    push 3
    a <- pop
    pop

result = runState manip [5,8,2,1]

main = putStrLn $ show result

There is plenty here that is still mysterious to me, but having complete code that runs makes me feel good.

My searching ran across this comment about things in modern Haskell:

In modern Haskell (Control.Monad.State), State s a is actually a type alias for a StateT transformer stack. It does not have a matching State data constructor (named "State") Instead, you must use the state function (lowercase "s") to wrap a state-passing function:

Here is what LYAH shows for the Monad instance for "State s". Given the comment above, it is unlikely that this is the code currently in use, but we can still learn from it (or try to).

instance Monad (State s) where
	return x = State $ \s -> (x, s)
	(State h) >>= f = State $ \s -> let (a, newState) = h s
	                                    (State g) = f a
	                                in g newState

The first thing to bear in mind is that the Monad "State s" is a function! And the "s" is part of that function. That is the beauty of it -- "s" is embedded in the Monad and taken care of for us. We therefore shouldn't talk about "State" as the monad but "State s".

Look at the implementation of return. It yields the type name "State" along with a function with a type signature s -> (x, s).

Go all the way back to this and compare it to the return above.

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

Now look at the implementation of bind (>>=) in the Monad instance. The game with any monad it to take functions with a type of "x -> m x" and link them together using (>>=). XXX Notice here that "State s" takes a function for s, hence the lambdas in the body of the instance. The Monad type is (State s) including the "s".

The Reader, Writer, State trio

To me, it looks like Reader and Writer are just specialized versions of State. The same mechanism is used.

People call the Reader, Writer, and "State a" monads a trio.
Perhaps a close look at Reader/Writer would be helpful.
Perhaps these essays will be helpful:

• State Monad from first principles
• Reader Monad from first principles
• Writer Monad from first principles

• Monday Morning Haskell (MMH)
• Monads (MMH)
• Reader and Writer monads (MMH)
• State monad (MMH)
• Monad Transformers (MMH)

Reader, Writer, and State all have one thing in common. They have a newtype declaration that wraps a function. And the function is named runState, runReader, or runWriter -- as appropriate.

the Reader monad

Maybe this deserves its own page? This can also be called the Environment monad. The basic idea is to pass a read only collection of stuff (the environment) through a chain of functions. We could add "env" as an extra argument to each function, but this is more elegant.

It is a lot like State, but now the state is read-only. %nav

---

Have any comments? Questions? Drop me a line!

Tom's software pages / tom@mmto.org