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屋!