Haskell 笔记：State Monad

一个依赖于外部状态 s 的伪函数 f' :: a -> b，我们可以将其改写为 f :: a -> s -> (b, s) 使其良定。即，在输入输出中显式传递状态 s。现在，我们需要利用 Monad 将状态传递过程隐藏起来。

注意到，输出值 (b, s) 中的末状态 s 不仅依赖于输入状态，更依赖于之前更改过状态的一系列函数及其逻辑。因此我们不能简单地将 Monad 定义为 (a, s) 类似的形式，否则两个函数用 >=> 结合的结果将与函数逻辑无关，这与我们的期望不符。

考虑如下定义：

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

由于 -> 的右结合性，f :: a -> s -> (b, s) 和 f :: a -> State s b 等价。固定 s，则 State s 可以成为一个 Monad。一个类型为 State s a 的值通常也被称为一个 state processor。

现在尝试定义 (>>=) :: State s a -> (a -> State s b) -> State s b。若 p >>= f，则 p 蕴含了在此之前所有的状态处理逻辑，我们希望将 p 和 f 的逻辑融合在一起，成为一个新的 state processor，并作为返回值。

p >>= f = 
    (
        State $ \s -> (b, s'')
        where
            (a, s') = (runState p) s
            p2 = f a -- :: State s b
            (b, s'') = (runState p2) s'
    )

return 是平凡的：

return a = State $ (\s -> (a, s))

fmap 可以作如下定义：

fmap :: (a -> b) -> (State s a) -> (State s b)
fmap f = 
    (
        \pIn -> (
            \s -> (b, s')
            where
                (a, s') = (runState pIn) s
                b = f a
        )

如此一来，我们可以将一系列的依赖外部状态的函数串成一个依赖外部状态的函数，传以初始状态，便可得到结果。