What is a State Monad?

2020-07-18•haskell

What is a state monad?

Other imperative languages keep track of state by mutating global variables, i.e. reassignment
Haskell is a purely functional language so we cannot keep track of state without threading state to each function – which can become troublesome
The state Monad abstracts state management make passing state much easier

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:

A function to construct an instance of that type
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

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.

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.

What is a State Monad?