13

刚刚从这个优秀的教程中学习了 State monad 。然而，当我试图向一个非程序员解释它时，他们有一个问题难倒了我。

如果 State 的目的是模拟可变内存，那么 state monad 存储的函数为什么是这样的类型：

s -> (a, s)

而不仅仅是：

s -> s

换句话说，对于“中间”值的需求是什么？例如，在我们需要它的情况下，我们不能通过简单地将状态定义为 的元组来模拟它(state, value)吗？

我确定我混淆了一些东西，任何帮助表示赞赏。

4

7 回答 7

17

为了与像 C 这样的命令式语言进行类比，s -> s对应于具有返回类型的函数，该函数void纯粹是为了副作用（例如改变内存）而调用的。它同构于State s ()。

实际上，可以编写仅通过全局变量进行通信的 C 函数。但是，就像在 C 中一样，从函数返回值通常很方便。这a就是为了。

当然，对于您的特定问题，它可能s -> s是一个更好的选择。虽然它不是 Monad，但它是 Monoid（当包裹在Endo中时）。<>因此，您可以使用and构造这样的函数mempty，它们对应于Monad 的>>=and return。

于 2012-07-20T16:57:36.623 回答
5

扩展尼克的答案：

s是状态。如果您的所有函数都是s -> s（状态到状态），您的函数将无法返回任何值。您可以将状态定义为(the actual state, value returned)，但这会将状态与有状态函数正在计算的值混为一谈。而且您希望函数实际计算和返回值也是常见的情况......

于 2012-07-20T16:44:53.580 回答
2

s' -> s'相当于(a, s) -> (a, s)。很明显State，a除了s.

另一方面，s -> (a, s)只需要种子s就可以开始事情，根本不需要a值。

因此，类型s -> (a, s)告诉你，State它比 if 它更简单(a, s) -> (a, s)。Haskell 中的类型传达了很多信息。

于 2012-07-20T17:51:06.327 回答
2

如果 的目的State是模拟可变内存，为什么 state monad 存储的函数是以下类型：

s -> (a, s)

而不仅仅是：

s -> s

monad的目的State不是模拟可变内存，而是对既产生值又产生副作用的计算进行建模。简单地说，给定 type 的一些初始状态s，您的计算将产生一些 type 的值a，以及更新的状态。

也许您的计算不会产生值...然后，很简单：值类型a是 simple ()。另一方面，也许您的计算没有副作用。同样，很简单：您可能会认为您的状态转换函数（ 的s -> s参数modify）只是id。但通常你同时处理这两个问题。

您实际上可以使用getandput作为相对简单的示例：

get :: State s s      -- s -> (s, s)
put :: s -> State ()  -- s -> (s -> ((), s))

  • get是一个计算，在给定当前状态（第一个s）的情况下，它将作为一个值（即计算的结果）和“新”（未修改）状态返回它。

  • put是一个计算，给定一个新状态（第一个s）和一个当前状态（第二个s），将简单地忽略当前状态。它将()作为计算值产生（因为，当然，它没有计算任何值！）并挂在提供的新状态上。

于 2012-07-23T17:17:03.607 回答
1

大概你想在do符号中使用你的有状态计算？

您应该问自己，Monad对于由

newtype State s = { runState :: s -> s }
于 2012-07-20T17:15:35.943 回答
0

a是返回的值，s是最终状态。

http://www.haskell.org/haskellwiki/State_Monad#Implementation

于 2012-07-20T16:39:30.683 回答
0

要解决的问题是你有一个输入和一系列函数，你想把这些函数按顺序应用到输入上。

如果函数是纯粹的状态改变函数，s -> s在 type 的输入上s，那么你不需要 State使用它们。Haskell 非常擅长将这些函数链接在一起，例如使用标准组合运算符.，或类似的东西foldr (.) id，或foldr id。

但是，如果这些函数都改变了一个状态并报告了这样做的一些结果，以便您可以给它们 type s -> (s,a)，那么将它们粘合在一起有点麻烦。您必须解压缩结果元组并将新状态值传递给下一个函数，在其他地方使用报告的值，然后解压缩该结果，依此类推。将错误状态传递给输入函数很容易，因为您必须显式命名每个结果并输入才能进行解包。你最终会得到这样的结果：

let
  (res1, s1) = fun1 s0
  (res2, s2) = fun2 s1
  (res3, s3) = fun3 res1 res2 s1
  ...
  in resN

在那里，我不小心通过了s1而不是s2，可能是因为我后来添加了第二行并且没有意识到第三行需要更改。在编写s -> s函数时，不可能出现这个问题，因为没有正确的名称：

let
  resN = fun1 . fun2 . fun3 . -- etc.

所以我们发明State了做同样的把戏。State本质上只是一种将函数粘合s -> (s,a)在一起的方式，这样正确的状态总是传递给正确的函数。

因此，人们并不是说“我们想使用State，让我们使用s -> (s,a)”，而是“我们正在编写类似的函数s -> (s,a)，让我们发明State来让它变得简单”。有了 functions s -> s，这已经很容易了，我们不必发明任何东西。

作为如何s -> (s,a)自然产生的示例，考虑解析：解析器将获得一些输入，消耗一些输入并返回一个值。在 Haskell 中，这很自然地被建模为获取一个输入列表，并返回一对值和剩余的输入 - 即[Input] -> ([Input], a)或State [Input]。

于 2012-07-31T15:55:01.707 回答