10

Scala でメモ化を行う方法を調べていると、理解できないコードがいくつか見つかりました。私はこの特定の「もの」を調べようとしましたが、それを何と呼ぶべきかわかりません。つまり、それを参照する用語です。さらに、記号を使用して検索するのは簡単ではありません。

ここで、Scala でメモ化を行う次のコードを見ました。 

case class Memo[A,B](f: A => B) extends (A => B) {
  private val cache = mutable.Map.empty[A, B]
  def apply(x: A) = cache getOrElseUpdate (x, f(x))
}

そして、私を混乱させているのはケースクラスが拡張しているものですextends (A => B)。まず、何が起こっているのですか？第二に、なぜそれが必要なのですか？最後に、この種の継承を何と呼びますか。つまり、それを参照するために使用できる特定の名前または用語はありますか?

次に、ここでフィバノッチ数を計算するためにこのように使用されるメモを見ています。 

  val fibonacci: Memo[Int, BigInt] = Memo {
    case 0 => 0
    case 1 => 1
    case n => fibonacci(n-1) + fibonacci(n-2)
  }

適用されている「単純化」のすべてを見ていないのはおそらく私です。しかし、私はval行の終わりを把握することができません= Memo {. したがって、これをより詳細に入力すると、Memo がどのように構築されているかについての「飛躍」が理解できるでしょう。

これに関するご支援をいただければ幸いです。ありがとうございました。

4

5 に答える 5

7

0_ の回答を完成させるために、fibonacciは のコンパニオン オブジェクトの apply メソッドを通じてインスタンス化されます。これは、 がケース クラスであるMemoため、コンパイラによって自動的に生成されます。Memo

これは、次のコードが生成されることを意味します。

object Memo {
  def apply[A, B](f: A => B): Memo[A, B] = new Memo(f)
}

Scala には、applyメソッドに対する特別な処理があります。呼び出し時に名前を入力する必要はありません。次の 2 つの呼び出しは厳密に同等です。

Memo((a: Int) => a * 2)

Memo.apply((a: Int) => a * 2)

ブロックは、caseパターン マッチングとして知られています。内部的には、部分関数、つまり、入力パラメーターの一部に対して定義されている関数を生成しますが、必ずしもすべてではありません。部分関数の詳細については、的外れなので省略します (これは、そのトピックについて私が自分自身に書いたメモです)。PartialFunctioncaseのインスタンス。

そのリンクをたどると、 Function1PartialFunctionが拡張されていることがわかります- これは の予想される引数です。Memo.apply

したがって、そのコードのビットが実際に意味することは、一度脱糖すると (それが単語の場合)、次のとおりです。

lazy val fibonacci: Memo[Int, BigInt] = Memo.apply(new PartialFunction[Int, BigInt] {
  override def apply(v: Int): Int =
    if(v == 0)      0
    else if(v == 1) 1
    else            fibonacci(v - 1) + fibonacci(v - 2)

  override isDefinedAt(v: Int) = true
})

unapplyパターン マッチングの処理方法を大幅に簡略化したことに注意してくださいunapplySeq。

于 2013-10-23T17:48:58.527 に答える
4

この回答は、0__ と Nicolas Rinaudo の両方によって提供された部分的な回答をまとめたものです。

概要：

Scala コンパイラーによって作成される、便利な (しかし非常に絡み合った) 仮定が多数あります。

  1. Scala は( ScalaDoc for Function1[+T1, -R] )extends (A => B)と同義として扱います。extends Function1[A, B]
  2. Function1 の継承された抽象メソッドの具体的な実装をapply(x: A): B提供する必要があります。def apply(x: A): B = cache.getOrElseUpdate(x, f(x))
  3. Scala は、matchで始まるコード ブロックに暗黙の を想定します。= Memo {
  4. Scala は{}項目 3 で開始されたコンテンツをパラメーターとして Memo ケース クラス コンストラクターに渡します。
  5. Scala は、{}項目 3 で開始された asの間の暗黙の型を想定しPartialFunction[Int, BigInt]、コンパイラは "match" コード ブロックを PartialFunction メソッドのオーバーライドとして使用apply()し、PartialFunction の method に追加のオーバーライドを提供しますisDefinedAt()。

詳細：

ケース クラス Memo を定義する最初のコード ブロックは、次のようにより詳細に記述できます。 

case class Memo[A,B](f: A => B) extends Function1[A, B] {    //replaced (A => B) with what it's translated to mean by the Scala compiler
  private val cache = mutable.Map.empty[A, B]
  def apply(x: A): B = cache.getOrElseUpdate(x, f(x))  //concrete implementation of unimplemented method defined in parent class, Function1
}

val fibanocci を定義する 2 番目のコード ブロックは、次のようにより詳細に記述できます。

lazy val fibonacci: Memo[Int, BigInt] = {
  Memo.apply(
    new PartialFunction[Int, BigInt] {
      override def apply(x: Int): BigInt = {
        x match {
          case 0 => 0
          case 1 => 1
          case n => fibonacci(n-1) + fibonacci(n-2)
        }
      }
      override def isDefinedAt(x: Int): Boolean = true
    }
  )
}

lazy行の自己参照の問題に対処するために、2 番目のコード ブロックの val に追加する必要がありましたcase n => fibonacci(n-1) + fibonacci(n-2)。

最後に、フィボナッチの使用例は次のとおりです。

val x:BigInt = fibonacci(20) //returns 6765 (almost instantly)
于 2013-10-23T19:56:06.593 に答える
2

これについてもう 1 つextends (A => B): extendshere は必須ではありませんが、 のインスタンスをMemo高次の関数や状況で同様に使用する場合は必要です。

this がなくても、インスタンスをメソッド呼び出しだけでextends (A => B)使用してもまったく問題ありません。Memofibonacci

case class Memo[A,B](f: A => B) {
    private val cache = scala.collection.mutable.Map.empty[A, B]
    def apply(x: A):B = cache getOrElseUpdate (x, f(x))
}
val fibonacci: Memo[Int, BigInt] = Memo {
    case 0 => 0
    case 1 => 1
    case n => fibonacci(n-1) + fibonacci(n-2)
}

例えば：

Scala> fibonacci(30)
res1: BigInt = 832040

ただし、高階関数で使用する場合は、型の不一致エラーが発生します。

Scala> Range(1, 10).map(fibonacci)
<console>:11: error: type mismatch;
 found   : Memo[Int,BigInt]
 required: Int => ?
              Range(1, 10).map(fibonacci)
                               ^

したがって、ここでは、メソッドを持っているため、いくつかのジョブを実行できるインスタンスを他の人extendsに識別するのに役立つだけです。fibonacciapply

于 2013-12-07T05:19:47.450 に答える