What is a State Monad?

2020-07-18haskell

What is a state monad?

Definition

newtype State s a = State { runState :: s -> (a,s) }
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

Derivation

It is often a slippery-slope trying to explain this monad instance in detail. I think we can convince ourselves of what a state monad is by checking each line of the equations to see if the types match up.

Preliminary Functions

Firstly, in the newtype definition we obtain two functions for free as a result of using record-syntax:

  1. A function to construct an instance of that type
  2. A function to access a field within the record
newtype State s a = State { runState :: s -> (a,s) }
-- State :: (s -> (a,s)) -> State s a
-- runState :: State s a -> (s -> (a,s))

We will be using these functions to derive our monad instance.

Create a Monad Instance

To construct these, we just need to write methods: return and bind.

class Monad m where 
    return :: a -> m a --return 
    (>>=) :: m a -> (a -> m b) -> m b  -- bind
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
-- List of type signatures:
-- (State h) :: State s a
-- h :: (s -> (a,s))
-- f :: a -> State s b
-- (State g) :: State s b 
-- g :: (s -> (b,s))
-- g newState :: (b,s)

Questions

  1. Why do we use State s and not State s a?

Remember all monads have to be of kind *->*. In other words, they have to have a single type parameter.

  1. What is h and g?

h and g are stateful computations, i.e. (s -> (a,s)). They compute a a value and new state from an old state. State g and State h become wrappers of stateful computation, i.e. the monad context containing the value.

Examples

References