What is a State Monad?
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 notState s a
?
Remember all monads have to be of kind *->*
. In other words, they have to have a single type parameter.
- What is
h
andg
?
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.