haskell - 了解 State 立单子(monad)

我正在“为哈萨克斯坦学到伟大的东西!”这本书中了解州立单子。由Miran Lipovaca撰写。
对于以下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是状态计算(即采用状态并返回具有更新状态的结果的函数)还是状态。我猜想它必须是有状态的计算，因为它被应用于lambda函数中的状态(s类型)以产生结果(a, newState)。

但是从State s a的类型声明:

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

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

最佳答案

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

因此，该函数将状态作为输入，并返回2元组(a, s)。这里的第一项是“输出”，第二项是“新状态”。新状态可能与旧状态相同，但是新状态因此有机会对状态进行更改(否则无论如何使用State并不是很有用)。

我们可以将State更改对象和状态更改对象的“工厂”(a -> State s b)绑定到新的State更改对象中。因此，我们构造了一个带有初始状态s的函数。我们首先将其运行到runState对象的State，然后检索一个2元组(a, s)。然后，我们可以使用此a构造一个State s b对象，然后通过该s对象的runState运行(更改状态)State。

因此，一个更详细的实现是:

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

请注意，我们这里实际上从未拥有状态值。我们仅构造一个将对该状态值起作用的新函数。

在示意图上，我们可以看到bind运算符如下:

s0
\ /
| |
| |
||||
| \ _________
| '
| s1
v \ /
一个-----> | |
| |
||||
| \ _______
| '
v 2
b

因此，这里第一个runState采用初始状态s将返回a和s。使用a，我们可以构造一个新的runState，然后可以进一步处理s状态，并将返回b和新的状态s。