14

私はプログラミング言語のインタプリタを書いています。

一連の式を評価して一連の値を取得し、評価が行われるときに 1 つの評価器から次の評価器に状態を伝達するための正しいコード イディオムが必要です。これには関数型プログラミングのイディオムが必要です。

結果は地図のように出てくるので折り目ではないです。state prop across のため、これはマップではありません。

私が持っているのは、これを理解しようとするために使用しているこのコードです。最初に数行のテスト リグで我慢します。

// 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 を使用していることに注意してください。以前のバージョンでは import を使用していました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 が別の回答で指摘しているように、状態モナドを使用してこの問題を解決することもできます。Scalaz は実際には、状態モナドの操作を彼の回答のバージョンよりもはるかに簡単にする多くの機能を提供していますが、それらはコメントに収まらないため、ここに追加します。

まず第一に、 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)

醜いタイプのラムダが気に入らない場合は、次のように削除できます。

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

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

しかし、それはさらに良くなります!Scalaz 7traverseでは、状態モナドに特化した のバージョンが提供されます。

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

あなたが説明しているのは、状態モナド内の計算です。あなたの質問に対する答えだと思います

結果は地図のように出てくるので折り目ではないです。state prop across のため、これはマップではありません。

状態モナドを使用したモナドマップです。

状態モナドの値は、何らかの内部状態を読み取り、場合によってはそれを変更し、何らかの値を返す計算です。Haskell でよく使用されます (こちらまたはこちらを参照)。

Scala の場合、それをモデル化するStatetraitと呼ばれる ScalaZ ライブラリにがあります (ソースも参照してください)。のインスタンスを作成するためのユーティリティ メソッドがあります。モナドの観点からは、は単なるモナドのであることに注意してください。これは、状態に応じた関数で記述されるため、最初は混乱するかもしれません。(モナド関数は 型のものになります。)StatesStateStateA => State[B]

次に必要なのは、式の値を計算し、計算を通じて状態をスレッド化するモナド マップ関数です。Haskell には、ステート モナドに特化した場合に、まさにそれを行うライブラリ メソッド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]()) );
}

このようにして、いくつかの引数を受け取って戻り、それらを or を使用して (またはおそらく内包表記を使用して)Stateより複雑な関数に結合する単純な関数を作成し、式のリストに対して を使用して計算全体を実行できます。State.mapState.flatMapformapM


http://blog.tmorris.net/posts/the-state-monad-for-scala-users/も参照してください。


編集: Travis Brownの回答を参照してください。彼は、Scala で状態モナドをよりうまく使用する方法を説明しました。

彼はまた尋ねます:

しかし、この場合に必要なことを正確に実行する標準コンビネーターがあるのに、なぜでしょうか? (これは、mapAccumL が使用するときに状態モナドを使用するために平手打ちされた誰かとして尋ねます。)

元の質問が尋ねたからです:

結果は地図のように出てくるので折り目ではないです。state prop across のため、これはマップではありません。

適切な答えは、状態モナドを使用したモナドマップであると思います。

を使用するmapAccumLと、メモリと CPU のオーバーヘッドが少なくなり、確実に高速になります。しかし、状態モナドは何が起こっているかという概念、つまり問題の本質を捉えています。多くの場合(ほとんどではないにしても)、これはより重要であると私は信じています。問題の本質を認識したら、高レベルの概念を使用して解決策を適切に説明する (おそらく速度/メモリを少し犠牲にする) か、高速になるように最適化します (または、両方を実行することさえできます)。

一方、mapAccumLこの特定の問題は解決しますが、より広い答えは得られません。少し手を加えると動かなくなってしまうかもしれません。または、ライブラリが複雑になり始めた場合、コードがごちゃごちゃし始め、それを改善する方法や、元のアイデアを再び明確にする方法がわかりません。

たとえば、ステートフルな式を評価する場合、ライブラリはますます複雑になる可能性があります。しかし、状態モナドを使えば、小さな関数を中心にライブラリを構築でき、それぞれがいくつかの引数を取り、 のようなものを返しますState[Context,Result]flatMapこれらのアトミックな計算は、メソッドまたは内包表記を使用してより複雑な計算に組み合わせることができfor、最終的に目的のタスクを構築します。原則はライブラリ全体で同じままであり、最終的なタスクも を返すものになりますState[Context,Result]

結論として、状態モナドを使用することが最善の解決策であると言っているわけではありません。私はそれが関数型プログラマーにとって最も教訓的であると信じています-それは問題をきれいで抽象的な方法で説明しています.

于 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 には 以外のループはありませんwhilefoldmapflatMapfor(flatMap/map の砂糖) などはすべて再帰的です。

このメソッドは末尾再帰的であり、スタックを構築しないようにコンパイラによって最適化されるため、絶対に安全に使用できます。@annotation.tailrec 注釈を追加して、コンパイラに末尾再帰の削除を適用させることができます。メソッドが tailrec でない場合、コンパイラは文句を言います。

編集: あいまいさを避けるために内部メソッドの名前を変更しました

于 2012-09-04T10:41:15.313 に答える