Scala 和 State Monad

Question

我一直在努力理解State Monad。与其说它是如何使用的，倒不如说它并不总是很容易找到，要么。但是我找到的关于 State Monad 的每一次讨论都有基本相同的信息，而且总有一些我不明白的地方。

以thispost为例。其中作者有以下内容：

case class State[S, A](run: S => (A, S)) {
...
  def flatMap[B](f: A => State[S, B]): State[S, B] =
    State(s => {
      val (a, t) = run(s)
      f(a) run t
    })
...
}

我可以看到类型正确排列。但是，我完全不明白第二个run。

也许我错误地看待了这个 monad 的全部目的。我从 HaskellWiki 中得到的印象是 State monad 有点像带有 run 允许转换的状态机（尽管在这种情况下，状态机并不像大多数状态机那样真正具有固定的状态转换状态机）。如果是这种情况，那么在上面的代码中 (a, t) 将代表一个单一的转换。 f 的应用表示对该值和 State 的修改（生成一个新的 State 对象）。这让我完全不知道第二个 run 是什么意思。它似乎是第二个 'transition'。但这对我来说没有任何意义。

我可以看到，对生成的 State 对象调用 run 会生成一个新的 (A, S) 对，当然，这对类型排列是必需的。但是我真的不明白这应该做什么。

那么，这里究竟发生了什么？这里建模的概念是什么？

编辑：2015 年 12 月 22 日

看来我没有很好地表达我的问题。让我试试这个。

在同一个博客 post 中，我们看到 map 的以下代码：

def map[B](f: A => B): State[S, B] =
  State(s => {
    val (a, t) = run(s)
    (f(a), t)
  })

显然这里只有一个 run 调用。

我一直试图调和的模型是，调用 run 可以通过单个状态更改移动我们保持向前的状态。在map中似乎就是这种情况。但是，在 flatMap 中，我们有两次调用 run。如果我的模型是正确的，那将导致 'skipping over' 状态改变。

要使用下面提供的示例@Filppo，第一次调用 run 将返回 (1, List(2,3,4,5))，第二次调用将返回 (2, List(3,4,5))，有效地跳过第一。因为在他的示例中，紧接着调用 map，这将导致 (Map(a->2, b->3), List(4,5)).

显然事实并非如此。所以我的整个模型是不正确的。正确的推理方法是什么？

第二次编辑：2015 年 12 月 22 日

我只是尝试按照我在 REPL 中所说的去做。我的直觉是正确的，这让我更加困惑。

scala> val v = State(head[Int]).flatMap { a => State(head[Int]) }
v: State[List[Int],Int] = State(<function1>

scala> v.run(List(1,2,3,4,5))
res2: (Int, List[Int]) = (2,List(3, 4, 5))

因此，flatMap 的这种实现 会跳过一个状态。然而，当我运行 @Filippo 的例子时，我得到了与他相同的答案。这里到底发生了什么？

Answer 1

state monad归结为这个函数从一个state到另一个state（加上A）：

type StatefulComputation[S, +A] = S => (A, S)

Tony 在该博客 post "capture" 中提到的实现 case class 的 run:

case class State[S, A](run: S => (A, S))

flatmap 对 bind 一个 state 对另一个 state 的实现正在调用 2 个不同的 runs:

    // the `run` on the actual `state`
    val (a: A, nextState: S) = run(s)

    // the `run` on the bound `state`
    f(a).run(nextState)

编辑 2 State

之间的 flatmap 示例

考虑一个简单地调用 .head 到 List 以获得 A 和 .tail 下一个状态的函数 S

// stateful computation: `S => (A, S)` where `S` is `List[A]`
def head[A](xs: List[A]): (A, List[A]) = (xs.head, xs.tail)

2的简单绑定State(head[Int]):

// flatmap example
val result = for {
  a <- State(head[Int])
  b <- State(head[Int])
} yield Map('a' -> a,
            'b' -> b)

for-comprehension 的预期行为是 "extract" 将列表的第一个元素放入 a，将第二个元素放入 b。结果状态 S 将是运行列表的剩余尾部：

scala> result.run(List(1, 2, 3, 4, 5))
(Map(a -> 1, b -> 2),List(3, 4, 5))

怎么样？在某些状态 s:

调用 run 中的 "stateful computation" head[Int]

s => run(s)

这给出了列表的head（A）和tail（B）。现在我们需要将 tail 传递给下一个 State(head[Int])

f(a).run(t)

其中 f 在 flatmap 签名中：

def flatMap[B](f: A => State[S, B]): State[S, B]

也许为了更好地理解此示例中的 f，我们应该将 for-comprehension 脱糖为：

val result = State(head[Int]).flatMap {
  a => State(head[Int]).map {
    b => Map('a' -> a, 'b' -> b)
  }
}

使用 f(a) 我们将 a 传递给函数，使用 run(t) 我们传递修改后的状态。

Answer 2

为了理解"second run"我们来分析一下"backwards".

签名def flatMap[B](f: A => State[S, B]): State[S, B]表明我们需要运行一个函数f和return它的结果。

要执行函数f，我们需要给它一个A。我们从哪里得到一个？
好吧，我们有 run 可以从 S 中得到 A，所以我们需要一个 S.

因此我们这样做：s => val (a, t) = run(s) ...。我们把它读成 "given an S execute the run function which produces us A and a new S. And this is our "first" 运行.

现在我们有一个A，我们可以执行f。这就是我们想要的，f(a) 给了我们一个新的 State[S, B]。如果我们这样做，那么我们有一个函数需要 S 和 returns Stats[S, B]:

(s: S) => 
   val (a, t) = run(s)
   f(a) //State[S, B]

但是函数 S => State[S, B] 并不是我们想要的 return！我们想要 return 只是 State[S, B].

我们该怎么做？我们可以把这个函数包装成 State:

State(s => ... f(a))

但它不起作用，因为 State 需要 S => (B, S)，而不是 S => State[B, S]。所以我们需要从 State[B, S].
中得到 (B, S) 我们只需调用其 run 方法并为其提供我们在上一步中刚刚生成的状态即可！又是我们的"second"运行.

因此，flatMap 执行了以下转换：

s =>                   // when a state is provided
  val (a, t) = run(s)  // produce an `A` and a new state value
  val resState = f(a)  // produce a new `State[S, B]`
  resState.run(t)      // return `(S, B)`

这给了我们 S => (S, B) 我们只是用 State 构造函数包装它。

查看这些 "two runs" 的另一种方式是：
首先 - 我们用"our" run 函数
自己转换状态 second - 我们将转换后的状态传递给函数 f 并让它进行自己的转换。

所以我们 "chaining" 状态转换一个接一个。而这正是 monad 所做的：它们为我们提供了按顺序安排计算的能力。

Answer 3

我接受了@AlexyRaga 对我的问题的回答。我认为@Filippo 的回答也非常好，事实上，它给了我一些额外的思考。谢谢你们。

我认为我在概念上遇到的困难实际上主要与“run 方法 'mean' 的作用有关”。即它的目的和结果是什么。我将其视为 'transition' 函数（从一种状态到另一种状态）。而且，在时尚之后，这就是它的作用。但是，它不会从给定的 (this) 状态转换到下一个状态。相反，它采用初始 State 和 returns (this) 状态的值和新的 'current' 状态（而不是 next状态转换序列中的状态）。

这就是 flatMap 方法按原样实现的原因。当您生成一个新的 State 时，您需要根据传入的初始状态从中获取当前的 value/state 对，然后可以将其作为函数包装在一个新的 State 对象中。你并没有真正过渡到一个新的状态。只需将生成的状态重新包装在一个新的 State 对象中。

我太沉迷于传统的状态机，看不到这里发生了什么。

再次感谢大家

Scala 和 State Monad

Scala and State Monad

scala

state-monad