Scala 和 State Monad [英] Scala and State Monad

问题描述

我一直在尝试了解 State Monad.与其说它是如何使用的，但也并不总是很容易找到.但是我发现的关于 State Monad 的每一次讨论都有基本相同的信息，而且总有一些我不明白的地方.

以这篇帖子为例.作者在其中有以下内容:

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

我可以看到类型排列正确.但是，我根本不理解第二个 run.

也许我错误地看待这个 monad 的整个目的.我从 HaskellWiki 中得到的印象是 State monad 有点像一个状态机，带有 run 允许转换(不过，在这种情况下，状态机并没有真正的固定状态像大多数状态机一样进行转换).如果是这种情况，那么在上面的代码中 (a, t) 将代表单个转换.f 的应用将代表对该值和 State 的修改(生成一个新的 State 对象).这让我完全困惑于第二个 run 是什么.这似乎是第二次过渡".但这对我来说没有任何意义.

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

那么，这里到底发生了什么?这里建模的概念是什么?

12/22/2015

所以，看来我没有很好地表达我的问题.让我试试这个.

在同一篇博文中，我们看到了以下 map 的代码:

def map[B](f: A => B): State[S, B] =状态(s => {val (a, t) = 运行 (s)(胖的)})

显然，这里只有一次对 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)).

显然这不是正在发生的事情.所以我的整个模型是不正确的.对此进行推理的正确方法是什么?

第二次12/22/2015

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

scala>val v = State(head[Int]).flatMap { a =>状态(头[Int])}v: State[List[Int],Int] = State(标度>v.run(List(1,2,3,4,5))res2: (Int, List[Int]) = (2,List(3, 4, 5))

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

解决方案

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

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

要执行函数f，我们需要给它一个A.我们从哪里得到一个?
好吧，我们有 run 可以从 S 中给我们 A，所以我们需要一个 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) = 运行 (s)f(a)//状态[S, B]

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

我们如何做到这一点?我们可以把这个函数包装成State:

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

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

因此，我们通过 flatMap 执行了以下转换:

s =>//当一个状态被提供时val (a, t) = run(s)//产生一个 `A` 和一个新的状态值val resState = f(a)//产生一个新的`State[S, B]`resState.run(t)//返回 `(S, B)`

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

另一种看待这两次运行"的方式是:
first - 我们自己用我们的"run 函数转换状态
second - 我们将转换后的状态传递给函数 f 并让它进行自己的转换.

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

I have been trying to understand the State Monad. Not so much how it is used, though that is not always easy to find, either. But every discussion I find of the State Monad has basically the same information and there is always something I don't understand.

Take this post, for example. In it the author has the following:

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
    })
...
}

I can see that the types line up correctly. However, I don't understand the second run at all.

Perhaps I am looking at the whole purpose of this monad incorrectly. I got the impression from the HaskellWiki that the State monad was kind of like a state-machine with the run allowing for transitions (though, in this case, the state-machine doesn't really have fixed state transitions like most state machines). If that is the case then in the above code (a, t) would represent a single transition. The application of f would represent a modification of that value and State (generating a new State object). That leaves me completely confused as to what the second run is all about. It would appear to be a second 'transition'. But that doesn't make any sense to me.

I can see that calling run on the resulting State object produces a new (A, S) pair which, of course, is required for the types to line up. But I don't really see what this is supposed to be doing.

So, what is really going on here? What is the concept being modeled here?

Edit: 12/22/2015

So, it appears I am not expressing my issue very well. Let me try this.

In the same blog post we see the following code for map:

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

Obviously there is only a single call to run here.

The model I have been trying to reconcile is that a call to run moves the state we are keeping forward by a single state-change. This seems to be the case in map. However, in flatMap we have two calls to run. If my model was correct that would result in 'skipping over' a state change.

To make use of the example @Filppo provided below, the first call to run would result in returning (1, List(2,3,4,5)) and the second would result in (2, List(3,4,5)), effectively skipping over the first one. Since, in his example, this was followed immediately by a call to map, this would have resulted in (Map(a->2, b->3), List(4,5)).

Apparently that is not what is happening. So my whole model is incorrect. What is the correct way to reason about this?

2nd Edit: 12/22/2015

I just tried doing what I said in the REPL. And my instincts were correct which leaves me even more confused.

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))

So, this implementation of flatMap does skip over a state. Yet when I run @Filippo's example I get the same answer he does. What is really happening here?

解决方案

To understand the "second run" let's analyse it "backwards".

The signature def flatMap[B](f: A => State[S, B]): State[S, B] suggests that we need to run a function f and return its result.

To execute function f we need to give it an A. Where do we get one?
Well, we have run that can give us A out of S, so we need an S.

Because of that we do: s => val (a, t) = run(s) .... We read it as "given an S execute the run function which produces us A and a new S. And this is our "first" run.

Now we have an A and we can execute f. That's what we wanted and f(a) gives us a new State[S, B]. If we do that then we have a function which takes S and returns Stats[S, B]:

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

But function S => State[S, B] isn't what we want to return! We want to return just State[S, B].

How do we do that? We can wrap this function into State:

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

But it doesn't work because State takes S => (B, S), not S => State[B, S]. So we need to get (B, S) out of State[B, S].
We do it by just calling its run method and providing it with the state we just produced on the previous step! And it is our "second" run.

So as a result we have the following transformation performed by a 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)`

This gives us S => (S, B) and we just wrap it with the State constructor.

Another way of looking at these "two runs" is:
first - we transform the state ourselves with "our" run function
second - we pass that transformed state to the function f and let it do its own transformation.

So we kind of "chaining" state transformations one after another. And that's exactly what monads do: they provide us with the ability to schedule computation sequentially.

这篇关于Scala 和 State Monad的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！