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