14

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

我需要正确的代码习惯来评估一系列表达式以获取它们的一系列值，并在评估发生时将状态从一个评估器传播到下一个评估器。我想要一个函数式编程习语。

这不是折叠，因为结果像地图一样出来。这不是地图，因为横穿了国家道具。

我所拥有的是我用来试图解决这个问题的代码。先忍受几行测试台：

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

但是，我想不出像上面的原始“var”解决方案那样紧凑或清晰的东西，我愿意接受，但我认为吃/喝/睡觉单子成语的人只会说.. . 使用这个... （希望如此！）

4

3 回答 3

19

使用带有累加器的 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（在两种情况下都首先声明）预期的签名。

使用状态单子（稍微不那么简单的方法）

正如 Petr Pudlák 在另一个答案中指出的那样，您也可以使用 state monad 来解决这个问题。Scalaz 实际上提供了许多工具，使使用 state monad 比他的答案中建议的版本更容易，而且它们不适合评论，所以我在这里添加它们。

首先，Scalaz 确实提供了一个mapM——它只是被称为traverse（这有点更笼统，正如 Petr Pudlá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专门用于 state 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版本好，但很干净。

于 2012-09-04T14:44:02.973 回答
4

您所描述的是状态单子中的计算。我相信你的问题的答案

这不是折叠，因为结果像地图一样出来。这不是地图，因为横穿了国家道具。

是它是使用状态 monad 的 monadic 地图。

状态单子的值是读取一些内部状态、可能修改它并返回一些值的计算。它经常在 Haskell 中使用（参见此处或此处）。

对于 Scala，traitScalaZ 库中有一个名为State的模型对其进行建模（另请参见源代码）。有一些实用方法States用于创建State. 注意从一元的角度来看State只是一个一元的值。起初这可能看起来令人困惑，因为它是由一个取决于状态的函数描述的。（一元函数将是某种类型A => State[B]。）

接下来你需要一个单子映射函数，它计算你的表达式的值，通过计算线程化状态。在 Haskell中，当专门用于 state monad 时，有一个库方法mapM可以做到这一点。

在 Scala 中，没有这样的库函数（如果有，请纠正我）。但是可以创建一个。举一个完整的例子：

import scalaz._;

object StateExample
  extends App
  with States /* utility methods */
{
  // The context that is threaded through the state.
  // In our case, it just maps variables to integer values.
  class Context(val map: Map[String,Int]);

  // An example that returns the requested variable's value
  // and increases it's value in the context.
  def eval(expression: String): State[Context,Int] =
    state((ctx: Context) => {
      val v = ctx.map.get(expression).getOrElse(0);
      (new Context(ctx.map + ((expression, v + 1)) ), v);
    });

  // Specialization of Haskell's mapM to our State monad.
  def mapState[S,A,B](f: A => State[S,B])(xs: Seq[A]): State[S,Seq[B]] =
    state((initState: S) => {
      var s = initState;
      // process the sequence, threading the state
      // through the computation
      val ys = for(x <- xs) yield { val r = f(x)(s); s = r._1; r._2 };
      // return the final state and the output result
      (s, ys);
    });


  // Example: Try to evaluate some variables, starting from an empty context.
  val expressions = Seq("x", "y", "y", "x", "z", "x");

  print( mapState(eval)(expressions) ! new Context(Map[String,Int]()) );
}

通过这种方式，您可以创建简单的函数，这些函数接受一些参数并返回State，然后使用State.mapor State.flatMap（或者更好地使用for推导式）将它们组合成更复杂的函数，然后您可以在表达式列表上运行整个计算mapM。

另见http://blog.tmorris.net/posts/the-state-monad-for-scala-users/

编辑：请参阅Travis Brown的回答，他描述了如何更好地在 Scala 中使用 state monad。

他还问：

但是，当有一个标准组合器可以完全满足您在这种情况下的需要时，为什么？（我问这个问题是因为当 mapAccumL 会使用 state monad 而被打脸的人。）

这是因为最初的问题是：

这不是折叠，因为结果像地图一样出来。这不是地图，因为横穿了国家道具。

我相信正确的答案是它是使用状态单子的单子地图。

使用mapAccumL肯定更快，内存和 CPU 开销都更少。但是状态单子抓住了正在发生的事情的概念，即问题的本质。我相信在许多（如果不是大多数）情况下，这更重要。一旦我们意识到问题的本质，我们可以使用高级概念来很好地描述解决方案（可能会牺牲一点速度/内存）或优化它以使其更快（或者甚至设法做到两者）。

另一方面，mapAccumL解决了这个特定的问题，但没有给我们更广泛的答案。如果我们需要稍微修改它，它可能会发生它不再工作了。或者，如果库开始变得复杂，代码可能会开始变得凌乱，我们不知道如何改进它，如何让最初的想法再次清晰。

例如，在评估有状态表达式的情况下，库可能变得复杂而复杂。但是如果我们使用 state monad，我们可以围绕小函数构建库，每个函数接受一些参数并返回类似State[Context,Result]. 这些原子计算可以使用flatMap方法或for理解组合成更复杂的计算，最后我们将构建所​​需的任务。整个库的原则将保持不变，最终任务也将是返回的东西State[Context,Result]。

总结一下：我并不是说使用 state monad 是最好的解决方案，当然它也不是最快的解决方案。我只是相信它对函数式程序员来说是最具教育意义的——它以一种干净、抽象的方式描述了问题。

于 2012-09-04T21:16:09.677 回答
0

您可以递归地执行此操作：

def testTheRecWay(xs: Seq[String]) = {
  def innerTestTheRecWay(xs: Seq[String], priorState: State = initialState, result: Vector[ResType] = Vector()): Seq[ResType] = {
    xs match {
      case Nil => result
      case x :: tail =>
        val (res, newState) = computeResultAndNewState(x, priorState)
        innerTestTheRecWay(tail, newState, result :+ res)
    }
  }
  innerTestTheRecWay(xs)
}

递归是函数式编程中的一种常见做法，并且在大多数情况下比循环更容易阅读、编写和理解。事实上 scala 除了 . 之外没有任何循环while。fold, map, flatMap, for（这只是 flatMap/map 的糖）等都是递归的。

这种方法是尾递归的，会被编译器优化为不建栈，所以使用起来绝对安全。您可以添加 @annotation.tailrec 注释，以强制编译器应用尾递归消除。如果您的方法不是 tailrec，编译器会抱怨。

编辑：重命名内部方法以避免歧义

于 2012-09-04T10:41:15.313 回答