# 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) }
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.

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.