映射和携带状态的正确单子或序列理解是什么? [英] what is proper monad or sequence comprehension to both map and carry state across?
问题描述
我正在写一个编程语言解释器.
I'm writing a programming language interpreter.
我需要正确的代码习惯来评估一系列表达式以获取其值的序列，并在评估发生时将状态从一个评估器传播到下一个评估器.我想要一个函数式编程习惯.
I have need of the right code idiom to both evaluate a sequence of expressions to get a sequence of their values, and propagate state from one evaluator to the next to the next as the evaluations take place. I'd like a functional programming idiom for this.
这不是折痕，因为结果像地图一样出现.这不是一张地图，因为有州的支持.
It's not a fold because the results come out like a map. It's not a map because of the state prop across.
我所拥有的是这段代码，我正在使用它试图找出答案.首先忍受几行测试台:
What I have is this code which I'm using to try to figure this out. Bear with a few lines of test rig first:
// test rig
class MonadLearning extends JUnit3Suite {
val d = List("1", "2", "3") // some expressions to evaluate.
type ResType = Int
case class State(i : ResType) // trivial state for experiment purposes
val initialState = State(0)
// my stub/dummy "eval" function...obviously the real one will be...real.
def computeResultAndNewState(s : String, st : State) : (ResType, State) = {
val State(i) = st
val res = s.toInt + i
val newStateInt = i + 1
(res, State(newStateInt))
}
我当前的解决方案.使用一个变量，该变量在评估地图主体时会更新:
My current solution. Uses a var which is updated as the body of the map is evaluated:
def testTheVarWay() {
var state = initialState
val r = d.map {
s =>
{
val (result, newState) = computeResultAndNewState(s, state)
state = newState
result
}
}
println(r)
println(state)
}
使用foldLeft，我有我认为不可接受的解决方案，它做我所谓的折叠时装袋"成语:
I have what I consider unacceptable solutions using foldLeft which does what I call "bag it as you fold" idiom:
def testTheFoldWay() {
// This startFold thing, requires explicit type. That alone makes it muddy.
val startFold : (List[ResType], State) = (Nil, initialState)
val (r, state) = d.foldLeft(startFold) {
case ((tail, st), s) => {
val (r, ns) = computeResultAndNewState(s, st)
(tail :+ r, ns) // we want a constant-time append here, not O(N). Or could Cons on front and reverse later
}
}
println(r)
println(state)
}
我也有几个递归变体(很明显，但也不是很清楚或动机不强)，其中一个使用的流几乎是可以容忍的:
I also have a couple of recursive variations (which are obvious, but also not clear or well motivated), one using streams which is almost tolerable:
def testTheStreamsWay() {
lazy val states = initialState #:: resultStates // there are states
lazy val args = d.toStream // there are arguments
lazy val argPairs = args zip states // put them together
lazy val resPairs : Stream[(ResType, State)] = argPairs.map{ case (d1, s1) => computeResultAndNewState(d1, s1) } // map across them
lazy val (results , resultStates) = myUnzip(resPairs)// Note .unzip causes infinite loop. Had to write my own.
lazy val r = results.toList
lazy val finalState = resultStates.last
println(r)
println(finalState)
}
但是，我无法找到像上面的原始"var"解决方案一样紧凑或清晰的东西，我愿意与之配合使用，但是我认为吃/喝/睡觉monad惯用语的人只会说...使用这个...(希望如此！)
But, I can't figure out anything as compact or clear as the original 'var' solution above, which I'm willing to live with, but I think somebody who eats/drinks/sleeps monad idioms is going to just say ... use this... (Hopefully!)
推荐答案
使用带有累加器的映射组合器(简单方法)
所需的高阶函数是mapAccumL.它位于Haskell的标准库中，但是对于Scala，您将必须使用 Scalaz 之类的东西.
With the map-with-accumulator combinator (the easy way)
The higher-order function you want is mapAccumL. It's in Haskell's standard library, but for Scala you'll have to use something like Scalaz.
首先导入(请注意，我在这里使用Scalaz 7；对于以前的版本，您将导入Scalaz._):
First the imports (note that I'm using Scalaz 7 here; for previous versions you'd import Scalaz._):
import scalaz._, syntax.std.list._
然后它是单线的:
scala> d.mapAccumLeft(initialState, computeResultAndNewState)
res1: (State, List[ResType]) = (State(3),List(1, 3, 5))
请注意，我必须颠倒评估程序参数和返回值元组的顺序，以匹配mapAccumLeft期望的签名(在两种情况下均先声明).
Note that I've had to reverse the order of your evaluator's arguments and the return value tuple to match the signatures expected by mapAccumLeft (state first in both cases).
正如PetrPudlák在另一个答案中指出的那样，您还可以使用状态monad来解决此问题. Scalaz实际上提供了许多功能，使使用状态monad的工作比他的回答中所建议的版本容易得多，并且它们不适合发表评论，因此我在此处添加它们.
As Petr Pudlák points out in another answer, you can also use the state monad to solve this problem. Scalaz actually provides a number of facilities that make working with the state monad much easier than the version in his answer suggests, and they won't fit in a comment, so I'm adding them here.
首先，Scalaz确实提供了mapM，它只是被称为traverse(正如PetrPudlák在其评论中所指出的那样，它更为通用).因此，假设我们具有以下条件(我在这里再次使用Scalaz 7):
First of all, Scalaz does provide a mapM—it's just called traverse (which is a little more general, as Petr Pudlák notes in his comment). So assuming we've got the following (I'm using Scalaz 7 again here):
import scalaz._, Scalaz._
type ResType = Int
case class Container(i: ResType)
val initial = Container(0)
val d = List("1", "2", "3")
def compute(s: String): State[Container, ResType] = State {
case Container(i) => (Container(i + 1), s.toInt + i)
}
我们可以这样写:
d.traverse[({type L[X] = State[Container, X]})#L, ResType](compute).run(initial)
如果您不喜欢丑陋的lambda，可以这样消除它:
If you don't like the ugly type lambda, you can get rid of it like this:
type ContainerState[X] = State[Container, X]
d.traverse[ContainerState, ResType](compute).run(initial)
但是它变得更好了！ Scalaz 7为您提供了专门针对状态monad的traverse版本:
But it gets even better! Scalaz 7 gives you a version of traverse that's specialized for the state monad:
scala> d.traverseS(compute).run(initial)
res2: (Container, List[ResType]) = (Container(3),List(1, 3, 5))
似乎还不够，甚至有内置run的版本:
And as if that wasn't enough, there's even a version with the run built in:
scala> d.runTraverseS(initial)(compute)
res3: (Container, List[ResType]) = (Container(3),List(1, 3, 5))
在我看来，它仍然不如mapAccumLeft版本好，但是很干净.
Still not as nice as the mapAccumLeft version, in my opinion, but pretty clean.
这篇关于映射和携带状态的正确单子或序列理解是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
