Scala和State Monad

Question

我一直在努力了解State Monad.与其如何使用不同,尽管这并不总是很容易找到.但是我发现的State Monad的每一次讨论基本上都有相同的信息,总有一些我不理解的东西.

以这篇文章为例.其中作者有以下内容:

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得到的印象是,状态monad有点像run允许转换的状态机(但在这种情况下,状态机并不像大多数状态机那样具有固定的状态转换).如果是这种情况,那么在上面的代码(a, t)中将表示单个转换.应用程序f将表示该值的修改和State(生成新的State对象).这让我完全不知道第二个run是什么.这似乎是第二次"过渡".但这对我没有任何意义.

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

那么,这里到底发生了什么？在这里建模的概念是什么？

编辑:2015年12月22日

所以,看来我并没有很好地表达我的问题.让我试一试.

在同一篇博文中,我们看到以下代码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.如果我的模型是正确的,那将导致"跳过"状态变化.

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

显然,这不是正在发生的事情.所以我的整个模型是不正确的.推理这个的正确方法是什么？

第2编辑: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

要理解"第二次运行",让我们"向后"分析它.

签名def flatMap[B](f: A => State[S, B]): State[S, B]表明我们需要运行一个函数f并返回其结果.

要执行功能,f我们需要给它一个A.我们从哪里得到一个？
好吧,我们有run可以让我们A离开S,所以我们需要一个S.

因为我们这样做:s => val (a, t) = run(s) ....我们把它读作"给出S执行run产生我们的功能A和新功能S.这是我们的"第一次"运行.

现在我们有一个A,我们可以执行f.这就是我们想要的,并f(a)给了我们一个新的State[S, B].如果我们这样做,那么我们有一个获取S并返回的函数Stats[S, B]:

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

但功能S => State[S, B]不是我们想要的回报!我们想要回归State[S, B].

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

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

但它没有State用S => (B, S),因为需要,而不是S => State[B, S].所以我们需要(B, S)离开State[B, S].
我们通过调用它的run方法并为它提供我们刚刚在上一步生成的状态来实现它!这是我们的"第二次"运行.

因此,我们通过以下方式执行以下转换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构造函数包装它.

看着这些"两分"的另一种方式是:
第一 -我们把国家与自己"我们"的run功能,
第二个 -我们传递转换状态的功能f,让它做自己的转型.

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