理解状态单子

Question

我在 Miran Lipovaca 的 "Learn You a Haskell for Great Good!" 一书中学习了 State monad。对于以下 monad 实例：

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

我无法理解 >>= 函数的定义。我不确定 h 是有状态计算（即接受状态的函数和 returns 具有更新状态的结果）还是状态。我猜它一定是有状态计算，因为它应用于 lambda 函数中的状态（s 类型）以产生结果 (a, newState).

但是从State s a的类型声明来看：

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

状态为s类型，结果为a类型。那么对于 monad 实例，s in instance Monad (State s) 是状态的 type 还是实际上是有状态计算？任何见解表示赞赏。

Answer 1

State 对象不存储状态。它存储一个"change of state"。实际上它存储了一个函数runState :: s -> (a, s)。这里 s 是状态的类型，a 是 "output" 可以这么说的类型。

函数因此将状态作为输入，return是一个二元组(a, s)。这里第一项是"output"，第二项是"new state"。新状态可能与旧状态相同，但因此有机会更改状态（否则无论如何使用 State 都不是很有用）。

我们可以将 State-changing 对象和状态更改对象 (a -> State s b) 的 "factory" 绑定到一个新的 State-changing 对象中。因此，我们构造了一个函数，该函数采用初始状态 s0。我们先运行那个到State对象的runState，从而得到一个二元组(a, s1)。然后我们可以使用这个 a 构造一个 State s b 对象，然后我们运行（改变的状态）s1 通过那个 State 对象的 runState。

因此，更详细的实现是：

instance Monad (State s) where 
   return x = State $ \s -> (x,s)
   (State h) >>= f = State g
       where g s0 = (b, s2) -- result of second runState
                 where (a, s1) = h s0 -- run through first runState
                       -- create second state with the output of the first
                       State f' = f a
                       (b, s2) = f' s1 -- run through second runState

请注意，我们在这里实际上没有状态值。我们只构造了一个新函数，将处理该状态值。

我们可以看到绑定运算符的示意图如下：

  s₀
\    /
 |  |
 |  |
 ||||
  |\_________
  |          '
  |           s₁
  v         \    /
  a ----->   |  |
             |  |
             ||||
              |\_______
              |        '
              v        s₂
              b

所以这里第一个runState采用初始状态s0将return和a 和 s1。使用 a，我们构造一个新的 runState，然后可以进一步处理状态 s1，并将return a b 和新状态 s2.

理解状态单子

Understanding the State Monad

haskell

functional-programming

monads

state-monad

newtype