state.hs

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

instance Monad (State s) where
    (State x) >>= f = State $ \s ->
        let (a, s') = x s
            (State x') = f a
        in x' s'

instance Applicative (State s) where
    pure x = State $ \s -> (x, s)
    (<*>) = ap

instance Functor (State s) where
    fmap = liftM