什么是正确的单子或序列理解，以映射和进位状态？

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

但是，我不能想出任何像上面原始的“var”解决方案那样紧凑和清晰的解决方案，我愿意接受它，但我认为吃/喝/睡单子成语的人会说……用这个..。(希望如此！)

Answer 1

使用带累加器的map组合器(最简单的方法)

您需要的高阶函数是mapAccumL。它在Haskell的standard library中，但是对于Scala，你必须使用像Scalaz这样的东西。

首先是导入(注意，我在这里使用的是Scalaz7；对于以前的版本，您需要导入Scalaz._)：

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

然后是一行：

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

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

使用state monad (稍微不太容易的方法)

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

但它会变得更好！Scalaz7为您提供了一个专用于状态monad的traverse版本：

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版本那么好，但相当干净。

Answer 2

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

，它不是一个折叠，因为结果就像一张地图。这不是一张地图，因为它是国家道具。

它是，一种使用状态单体的一元映射。

状态单体的值是读取一些内部状态，可能修改它，并返回一些值的计算。它经常在Haskell中使用(参见here或here)。

对于Scala，ScalaZ库中有一个名为State的trait对其进行建模(另请参阅the source)。States中有用于创建State实例的实用程序方法。请注意，从一元值的角度来看，State只是一个一元值。乍一看，这似乎很混乱，因为它是由一个依赖于状态的函数来描述的。(一元函数的类型应该是A => State[B]。)

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

在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.map或State.flatMap (或者使用for理解可能更好)将它们组合成更复杂的函数，然后您可以通过mapM在一系列表达式上运行整个计算。

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

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

他还问道：

但是为什么，当有一个标准的组合子可以在这种情况下做你需要的事情呢？(我问这个问题的原因是，有人因为使用state monad而被打耳光，而mapAccumL也会这么做。)

这是因为原来的问题是：

，它不是一个折叠，因为结果就像一张地图。这不是一张地图，因为它是国家道具。

我认为正确的答案是，这是一个使用状态单体的一元映射。

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

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

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

总结:我并不是说使用state monad是最好的解决方案，当然它也不是最快的。我只是相信它对于函数式程序员来说是最有说服力的--它以一种干净、抽象的方式描述了问题。

Answer 3

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

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 (它只是平板地图/地图的糖)等都是递归的。

此方法是尾递归的，编译器会对其进行优化，使其不会构建堆栈，因此使用它是绝对安全的。您可以添加@annotation.tailrec注释，以强制编译器应用尾递归消除。如果你的方法不是tailrec，编译器就会报错。

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