haskell - 对“Learn you a Haskell”的 State Monad 代码感到困惑

Question

我正在尝试使用在线书籍Learn you a Haskell for great Good来掌握 Haskell 。

据我所知，到目前为止，我已经能够理解 Monad，直到我读到介绍State Monad的章节。

然而，呈现并声称是 State 类型的 Monad 实现的代码（我无法在 Hoogle 中找到它）似乎对我来说太难处理了。

• 首先，我不明白它背后的逻辑，即为什么它应该起作用以及作者如何考虑这种技术。（也许可以建议相关文章或白皮书？）

• 在第 4 行，建议函数 f 采用 1 个参数。
  然而，接下来的几行我们看到了 pop，它不带参数！

• 为了扩展第 1 点，作者试图用一个函数来代表国家来完成什么。

非常感谢任何有助于理解正在发生的事情。

编辑

敬启者，

下面的答案彻底涵盖了我的问题。
不过我想补充一件事：

在阅读了下面建议的文章后，我找到了上面第二点的答案：一直以来，我都认为pop 函数会像这样使用：
stuff >>= pop因为在绑定类型中，第二个参数是函数，而正确的用法是 this pop >>= stuff，在再次阅读 do-notation 如何转换为普通的 bind-lambdas 后，我意识到这一点。

Answer 1

Statemonad 表示有状态的计算，即使用来自某些外部状态的值，并且可能修改某些外部状态的计算。当您将有状态的计算排序在一起时，后面的计算可能会给出不同的结果，具体取决于先前的计算如何修改状态。

由于 Haskell 中的函数必须是纯函数（即没有副作用），我们通过要求每个函数接受一个表示当前世界状态的附加参数并返回一个表示修改后状态的附加值来模拟外部状态的影响。实际上，外部状态是通过一系列计算线程化的，就像我刚刚在 MSPaint 中绘制的这张可憎的图表一样：

请注意每个框（表示计算）如何具有一个输入和两个输出。

如果您查看Monad实例，State您会发现 的定义(>>=)告诉您如何执行此线程。它说要将有状态计算绑定c0到一个函数，该函数f接受有状态计算的结果并返回另一个有状态计算，我们执行以下操作：

1. c0使用初始状态运行s0以获得结果和新状态：(val, s1)
2. 输入val函数f以获得新的有状态计算，c1
3. c1使用修改后的状态运行新计算s1

---

这如何与已经接受n参数的函数一起工作？因为 Haskell 中的每个函数默认都是柯里化的，所以我们只需在末尾添加一个额外的参数（用于状态），而不是正常的返回值，该函数现在返回一个对，其第二个元素是新修改的状态。所以而不是

f :: a -> b

我们现在有

f :: a -> s -> (b, s)

您可能会选择将其视为

f :: a -> ( s -> (b, s) )

这在 Haskell 中是一样的（因为函数组合是右关联的），它读取“f是一个接受类型参数a并返回有状态计算的函数”。这就是Statemonad的全部内容。

Answer 2

简短的回答：

1. State旨在利用 monad 的特性来模拟带有局部变量的命令式系统状态。基本思想是在 monad 中隐藏获取当前状态并在每一步返回新状态以及中间结果的活动（这里我们有s -> (a,s).
2. 不要将任意函数与包含在State. 前者可能有你想要的任何类型（前提是State a如果你想在 state monad 中使用它们，它们最终会产生一些）。后者拥有 type 的函数s -> (a,s)：这​​是由 monad 管理的状态传递层。
3. 正如我所说，包含在其中的函数State实际上是通过为实例定义的(>>=)并return通过它们生成的。Monad (State s)它的作用是通过代码调用传递状态。

第 3 点也是 state 参数从 state monad 中实际使用的函数中消失的原因。

长答案：

State Monad 已经在不同的论文中进行了研究，并且也存在于 Haskell 框架中（我现在不记得好的参考资料，我会尽快添加它们）。

这就是它遵循的想法：考虑一个data MyState = ...其值保持系统当前状态的类型。

如果你想通过一堆函数传递它，你应该以这样的方式编写每个函数，它至少将当前状态作为参数并返回一对及其结果（取决于状态和其他输入参数）和新的（可能修改的）状态。嗯，这正是 state monad 的类型告诉你的s -> (a, s)：在我们的示例中，sisMyState并且旨在传递系统的状态。

包裹在 中的函数State不接受参数，除了来自当前状态，这是生成新状态和中间结果所必需的。您在示例中看到的具有更多参数的函数不是问题，因为当您do在 monad 中的 -notation 中使用它们时，您会将它们应用于所有“额外”需要的参数，这意味着它们中的每一个都会产生在一个部分应用的函数中，其唯一的剩余参数是状态；monad 实例State将完成其余的工作。

如果您查看可能在 monad 中使用的函数的类型（实际上，在 monad 中它们通常称为操作），您会看到它们的结果类型被装箱在 monad 中：这就是告诉您的点一旦你给了它们所有的参数，它们实际上不会返回结果，而是（在这种情况下）一个s -> (a,s)符合 monad 组合法则的函数。

计算将通过将系统的第一/初始状态传递给整个块/组合来执行。

最后，不带参数的函数将具有类似State awherea的返回类型的类型：如果您查看 的值构造函数State，您会再次看到这实际上是一个函数s -> (a,s)。

Answer 3

我完全是 Haskell 的新手，我也不能很好地理解那本书中的 State Monad 代码。但是让我在这里添加我的答案以帮助将来的人。

答案：

• 他们想用 State Monad 完成什么？

  组合处理有状态计算的函数。
  例如push 3 >>= \_ -> push 5 >>= \_ -> pop
  
  

• 为什么pop不带参数，而建议函数f带 1 个参数？

  pop不接受任何参数，因为它被State.
  类型为 unwapped 的函数s -> (a, s)接受一个参数。也是如此push。
  你可以用runState.

  runState pop :: Stack -> (Int, Stack)
  runState (push 3) :: Stack -> ((), Stack)
  

  >>=如果您指的是“函数f”的右侧，f则将类似于\a -> popor \a -> push 3，而不仅仅是pop.

长解释：

这三件事帮助我更多地理解了 State Monad 和 Stack 的例子。

• 考虑绑定运算符（>>=）的参数类型

  Monad 类型类中绑定运算符的定义是这样的

  (>>=) :: (Monad m) => ma -> (a -> mb) -> mb
  

  在堆栈示例中，m是State Stack.
  如果我们在心理上用 替换m，State Stack定义可以是这样的。

  (>>=) :: 状态栈 a -> (a -> 状态栈 b) -> 状态栈 b

  因此，绑定运算符左侧参数的类型将是State Stack a.
  而右边的将是a -> State Stack b。
  
  

• 将 do 表示法转换为绑定运算符

  这是书中使用 do 表示法的示例代码。

  stackManip :: 状态堆栈整数  
  stackManip = 做  
       推 3  
       流行音乐  
       流行音乐  
  

  可以使用绑定运算符将其翻译为以下代码。

  stackManip :: 状态堆栈整数  
  stackManip = push 3 >>= \_ -> pop >>= \_ -> pop
  

  现在我们可以看到绑定运算符的右侧是什么。
  它们的类型是a -> State Stack b.

  (\_ -> pop) :: a -> State Stack Int
  (\_ -> push 3) :: a -> 状态栈 ()
  

  
  

• 识别实例声明之间(State s)和中的区别(State h)

  这是书中State的实例声明。

  实例 Monad (State s) 其中  
      返回 x = 状态 $ \s -> (x,s)  
      (状态 h) >>= f = 状态 $ \s -> 让 (a, newState) = hs  
                                          (状态 g) = fa  
                                      在新状态
  

  考虑堆栈示例的类型，类型(State s)将是

  (State s) :: 状态栈
  s :: 堆栈
  

  的类型(State h)将是

  (状态 h):: 状态堆栈 a
  h :: 堆栈 -> (a, 堆栈)
  

  (State h)是绑定运算符的左侧参数，其类型State Stack a如上所述。
  

  那为什么h变成Stack -> (a, Stack)?
  它是与 newtype 包装器中定义的 State 值构造函数进行模式匹配的结果。对于(State g).

  新类型状态 sa = 状态 { runState :: s -> (a,s) }
  

  一般来说，type ofh是s ->(a, s)有状态计算的表示。以下任何一项都可能是h堆栈示例中的。

  runState pop :: Stack -> (Int, Stack)
  runState (push 3) :: Stack -> ((), Stack)
  runState stackManip :: Stack -> (Int, Stack)
  

  就是这样。

Answer 4

Statemonad本质上是

type State s a = s -> (a,s)

从一个状态 ( s) 到一对期望结果 ( a) 和一个新状态的函数。该实现使状态的线程化并为您处理状态传递和更新，因此不会有意外将错误状态传递给下一个函数的风险。

因此，一个接受k > 0参数的函数，其中一个是状态并返回一对东西和一个新状态，在State smonad 中变成了一个接受k-1参数并返回一个单子动作的函数（它基本上是一个接受一个参数的函数，状态，这里）。

在非状态设置中，pop接受一个参数，堆栈，即状态。所以在单子设置中，pop变成了一个State Stack Int没有明确参数的动作。

使用Statemonad 而不是显式的状态传递可以使代码更简洁，出错的机会更少，这就是Statemonad 所完成的。没有它一切都可以完成，它只会更麻烦且容易出错。