>>12385Here's how you (could) define a state monad:
newtype State s a = State { runState :: s -> (a, s) }
"State s a" is a box containing a function of type "s -> (a, s)", which can be extracted with "runState". So here, the "state" is a represented as a single value: you supply an initial state, and you get back a result and a final state.
instance Functor (State s) where
fmap :: (a -> b) -> State s a -> State s b
fmap f sa = State $ \st -> let (a, st') = runState sa st in (f a, st')
The Functor instance lets you apply a function to the result value, possibly changing its type. It doesn't let you do anything to the state value though. This is because Functor has kind "* -> *", whereas "State" has kind "* -> * -> *", so the first type parameter needs to be fixed.
instance Applicative (State s) where
pure :: a -> State s a
pure a = State $ \st -> (a, st)
(<*>) :: State s (a -> b) -> State s a -> State s b
sf <*> sa = State $ \st -> let (f, st1) = runState sf st
(a, st2) = runState sa st1
in (f a, st2)
Applicative lets you put values into State, and to apply a stateful function to a stateful value: and thread through the state from left to right.
instance Monad (State s) where
(>>=) :: State s a -> (a -> State s b) -> State s b
sa >>= f = State $ \st -> let (a, st') = runState sa st
in runState (f a) st'
Monad lets you sequence stateful actions together.
We also want to be able to modify this internal state, in particular we want to be able to read the current state, and replace it with a new value:
get :: State s s
get = State $ \st -> (st, st)
put :: s -> State s ()
put s = State $ \_ -> ((), s)
Now a little example:
example :: State Int String
example = do
x <- get
put (x + 1)
y <- get
put (y + 1)
pure "hello world"
main :: IO ()
main = print $ runState example 0
This prints ("hello world",2).
