什么是适当的monad或序列理解来映射和携带状态？

Question

我正在编写一个编程语言解释器.

我需要正确的代码习惯用法来评估表达式序列以获取其值的序列,并在评估发生时将状态从一个评估器传播到下一个评估器.我想要一个函数式编程习惯用法.

它不是折叠因为结果像地图一样出现.这不是地图,因为国家支持.

我所拥有的是这个代码,我用来试图解决这个问题.首先考虑几行试验台:

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

我目前的解决方案 使用在评估地图主体时更新的var:

  def testTheVarWay() {
    var state = initialState
    val r = d.map {
      s =>
        {
          val (result, newState) = computeResultAndNewState(s, state)
          state = newState
          result
        }
    }
    println(r)
    println(state)
  }

我有我认为不可接受的解决方案使用foldLeft,它做我称之为"折叠时包你好"的成语:

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)

}

我也有一些递归变量(很明显,但也不清楚或者很有动力),一个使用几乎可以容忍的流:

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

但是,我想不出任何东西作为紧凑型或明确为原来的"变种"上面的解决方案,我愿意住在一起,但我认为人谁吃/饮料/睡单子成语是怎么回事,只是说..用这个...(希望!)

Answer 1

使用map-with-accumulator组合器(简单方法)

你想要的高阶函数是mapAccumL.它位于Haskell的标准库中,但对于Scala,您必须使用类似Scalaz的东西.

首先是导入(注意我在这里使用Scalaz 7;对于你导入的先前版本Scalaz._):

import scalaz._, syntax.std.list._

然后它是一个单行:

scala> d.mapAccumLeft(initialState, computeResultAndNewState)
res1: (State, List[ResType]) = (State(3),List(1, 3, 5))

请注意,我必须颠倒评估者的参数和返回值元组的顺序以匹配期望的签名mapAccumLeft(在两种情况下都是状态优先).

随着州monad(稍微不那么简单的方式)

正如PetrPudlák在另一个答案中指出的那样,你也可以使用状态monad来解决这个问题.Scalaz实际上提供了许多设施,使得与州monad合作比他的答案中的版本更容易,并且它们不适合评论,所以我在这里添加它们.

首先,Scalaz确实提供了一个mapM刚刚调用的东西traverse(正如PetrPudlák在他的评论中指出的那样,这是一个更普遍的).所以假设我们有以下内容(我在这里再次使用Scalaz 7):

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,你可以像这样摆脱它:

type ContainerState[X] = State[Container, X]

d.traverse[ContainerState, ResType](compute).run(initial)

但它变得更好!Scalaz 7为您提供了一个traverse专门用于状态monad的版本:

scala> d.traverseS(compute).run(initial)
res2: (Container, List[ResType]) = (Container(3),List(1, 3, 5))

而且好像这还不够,甚至还有run内置的版本:

scala> d.runTraverseS(initial)(compute)
res3: (Container, List[ResType]) = (Container(3),List(1, 3, 5))

mapAccumLeft在我看来,仍然没有版本那么好,但很干净.