Notes on state monad

haskell_state_monad.md

https://hackage.haskell.org/package/containers-0.6.6/docs/src/Utils.Containers.Internal.State.html

newtype State s a = State {runState :: s -> (s, a)}

instance Functor (State s) where
    fmap = liftA

instance Monad (State s) where
    {-# INLINE return #-}
    {-# INLINE (>>=) #-}
    return = pure
    m >>= k = State $ \ s -> case runState m s of
        (s', x) -> runState (k x) s'

Let's remove the State / runState wrapper to see whats really going on.

m :: s -> (s, a)
k :: a -> (s -> (s, a))
# using noulith syntax
m >>= k := \s -> (s', x := m(s); m':= k(x); m'(s'))

s here is the initial state. s' is the state after applying the previous computation m. A new computation m' is produced from k depending on x (the result of the previous computation). That computation is then evaluated to give the final result.

so x <- (do notation) is pulling out the result of the previous computation to produce the next computation.

instance Applicative (State s) where
    {-# INLINE pure #-}
    pure x = State $ \ s -> (s, x)
    (<*>) = ap
    m *> n = State $ \s -> case runState m s of
      (s', _) -> runState n s'
#if MIN_VERSION_base(4,10,0)
    liftA2 = liftM2
#endif

execState :: State s a -> s -> a
execState m x = snd (runState m x)

so pure just discards and replaces the result of the previous computation