关于"了解你的Haskell"的State Monad代码的困惑

Question

我正在尝试使用在线书籍了解Haskell以获得很好的Haskell.

据我所知,到目前为止,我已经能够理解Monads,直到我介绍State Monad这一章.

然而,代码呈现并声称是Monad实现的State类型(我无法在Hoogle中找到它)对我来说似乎太过分了.

• 首先,我不理解它背后的逻辑,即为什么它应该工作以及作者如何考虑这种技术.(可能会建议相关的文章或白皮书？)

• 在第4行,建议函数f取1个参数.
  然而,几行下来我们会看到pop,它没有参数!

• 为了扩展第1点,作者试图使用函数来表示状态.

非常感谢任何帮助理解正在发生的事情.

编辑

敬启者,

以下答案彻底涵盖了我的问题.
我想补充一点:

在阅读了下面提到的文章之后,我找到了上面第二点的答案:所有那段时间我都假设 pop函数会被用作:
stuff >>= pop因为在bind类型中第二个参数是函数,而正确的用法是这样的pop >>= stuff,我在再次阅读之后意识到,如何将符号转化为简单的绑定 - lambdas.

Answer 1

该State单子表示状态的计算即使用值从,或许修改,一些外部状态的计算.当您对有状态计算进行排序时,后面的计算可能会给出不同的结果,具体取决于先前计算如何修改状态.

由于Haskell中的函数必须是纯的(即没有副作用),我们通过要求每个函数采用表示世界当前状态的附加参数来模拟外部状态的影响,并返回表示修改状态的附加值.实际上,外部状态穿过了一系列计算,就像我刚刚在MSPaint中绘制的图的可憎一样:

注意每个框(表示计算)如何具有一个输入和两个输出.

如果您查看Monad实例,State您会看到定义(>>=)告诉您如何执行此线程.它表示要将有状态计算绑定c0到f获取有状态计算结果并返回另一个有状态计算的函数,我们执行以下操作:

1. c0使用初始状态运行s0以获得结果和新状态:(val, s1)
2. 饲料val的功能f得到一个新的状态计算,c1
3. c1使用修改后的状态运行新计算s1

这如何与已经采用n参数的函数一起工作？因为默认情况下Haskell中的每个函数都是curry,所以我们只是将一个额外的参数(对于状态)添加到结尾,而不是正常的返回值,函数现在返回一个第二个元素是新修改状态的对.而不是

f :: a -> b

我们现在有

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

您可以选择将其视为

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

在Haskell中是相同的(因为函数组合是右关联的),它读取" f是一个接受类型参数a并返回有状态计算的函数".这就是Statemonad的全部内容.

Answer 2

简短回答:

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

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

答案很长:

State Monad已经在不同的论文中进行了研究,并且也存在于Haskell框架中(我现在不记得很好的引用,我会尽快添加它们).

这是它的想法:考虑一个类型,data MyState = ...其值保持系统的当前状态.

如果你想通过一堆函数传递它,你应该以这样的方式编写每个函数,它至少将当前状态作为参数并返回一对其结果(取决于状态和其他输入)参数)和新的(可能修改的)状态.嗯,这正是州monad告诉你的类型:s -> (a, s).在我们的例子中,s是MyState和意味着传递系统的状态.

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

如果你看一下可能在monad中使用的函数的类型(实际上,在monad中它们通常被称为动作),你会看到它们的结果类型是在monad中的盒子:这是告诉你的点一旦你给他们所有参数,他们实际上不会返回结果,但(在这种情况下)一个函数s -> (a,s)将符合monad的组成定律.

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

最后,不带参数的函数的类型为喜欢State a在那里a为他们的返回类型:如果你看看价值构造函数State,你会再次看到,这实际上是一个函数s -> (a,s).

Answer 3

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

答案：

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

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

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

  pop不接受任何参数，因为它由State.
  类型为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 :: 状态堆栈 Int  
  stackManip = 做  
       推3  
       流行音乐  
       流行音乐  
  

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

  stackManip :: 状态堆栈 Int  
  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) where  
      返回 x = 状态 $ \s -> (x,s)  
      (State h) >>= f = State $ \s -> let (a, newState) = hs  
                                          (状态 g) = fa  
                                      在 g newState 
  

  考虑 Stack 示例中的类型，类型(State s)将是

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

  而类型(State h)将是

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

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

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

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

  通常，类型h是s ->(a, s)，状态计算的表示。以下任何一项都可能是hStack 示例中的。

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

  就是这样。

Answer 4

该State单子基本上是

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

从一个state(s)到一对所需result(a)和一个新状态的函数.该实现使状态的线程隐式并为您处理状态传递和更新,因此不存在意外将错误状态传递给下一个函数的风险.

因此k > 0,在State smonad 中接受参数(其中一个是状态并返回一对东西和一个新状态)的函数变成了一个接受k-1参数并返回一个monadic动作的函数(它基本上是一个带有一个参数的函数,状态,这里).

在非状态设置中,pop接受一个参数,即堆栈,即状态.所以在monadic环境中,pop成为一个State Stack Int没有明确论证的行动.

使用Statemonad而不是显式状态传递可以使代码更简洁,错误的机会更少,这就是Statemonad完成的工作.一切都可以在没有它的情况下完成,它会更加麻烦且容易出错.