了解状态单子

Question

我正在“为哈萨克斯坦学到伟大的东西！”一书中学习有关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
                                       (Stage g) = f a
                                   in g newState

我在理解>>=函数定义时遇到麻烦。我不确定h状态计算（即采用状态并返回具有更新状态的结果的函数）还是状态。我猜想它必须是有状态的计算，因为它被应用于slambda函数中的类型状态以产生结果(a, newState)。

但是从状态sa的类型声明：

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

状态是类型s，结果是类型a。所以对于单子的实例是s在instance Monad (State s) where状态的类型或它实际上是有状态的计算？任何见解都表示赞赏。

Answer 1

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

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

我们可以将State更改对象和状态更改对象的“工厂” 绑定a -> State s b到新的State更改对象中。因此，我们构造了一个具有初始状态的函数。我们首先运行到了的对象，从而获取一个2元组。然后，我们可以用这个来构造一个对象，然后我们运行（改变的状态），通过该的对象。s0runStateState(a, s1)aState s bs1runStateState

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

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运算符如下：

  s 0
\ /
 | |
 | |
 ||||
  | \ _________
  | '
  | s 1
  v \ /
  一个-----> | |
             | |
             ||||
              | \ _______
              | '
              VS 2 
              b

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