理解状态单子模式

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是有状态计算（即接收状态并返回带有更新状态的结果的函数）还是一个状态。我猜测它必须是一个有状态的计算，因为它应用于状态（类型为s）的lambda函数中，以产生结果(a, newState)。

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

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

状态的类型为s，结果的类型为a。所以对于monad实例，instance Monad (State s)中的s是状态的类型，还是实际的有状态计算？任何见解都将不胜感激。

- ceno980

---

使用 newtype {- StatePassingComputations -} State s a = MkState { runState :: s -> (a,s) } 可能会在面向新手的书籍中更加清晰易懂。 - Will Ness

Answer 1

一个 State 对象并不存储一个状态。它存储的是“状态变化”。实际上，它存储了一个函数 runState :: s -> (a, s)。这里，s 是状态的类型，而 a 可以说是“输出”的类型。

因此，该函数以状态作为输入，并返回一个 2-元组 (a, s)。这里，第一个元素是“输出”，第二个元素是“新状态”。新状态可能与旧状态相同，但这样就有机会对状态进行更改（否则使用 State 就没有什么用处）。

我们可以将一个改变 State 的对象和一个生成改变状态对象的“工厂”(a -> State s b)绑定在一起，构建一个新的改变 State 的对象。因此，我们构建一个函数，它需要一个初始状态 s0。首先将其运行到 State 对象的 runState 中，从而检索到一个 2-元组 (a, s1)。然后，我们可以使用这个 a 来构造一个 State s b 对象，然后我们通过那个 State 对象的 runState 运行（更改后的状态）s1。

因此，一种更冗长的实现方式是：

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

请注意，我们这里实际上从未有过状态值。我们只是构建一个新函数，它将运作在该状态值上。

从示意上看，我们可以将绑定操作符视为以下形式：

  s0
\    /
 |  |
 |  |
 ||||
  |\_________
  |          '
  |           s1
  v         \    /
  a ----->   |  |
             |  |
             ||||
              |\_______
              |        '
              v        s2
              b

因此，第一个 runState 接收初始状态 s0 并返回一个 a 和 s1。使用 a，我们构建一个新的 runState，它可以进一步处理状态 s1，并将返回一个 b 和新状态 s2。

- Willem Van Onsem