Scala-Memo: Wie funktioniert dieses Scala-Memo?
Der folgende Code stammt vonPathikrits dynamische Programmierung Repository. Ich bin sowohl von seiner Schönheit als auch von seiner Eigentümlichkeit verblüfft.
def subsetSum(s: List[Int], t: Int) = {
type DP = Memo[(List[Int], Int), (Int, Int), Seq[Seq[Int]]]
implicit def encode(key: (List[Int], Int)) = (key._1.length, key._2)
lazy val f: DP = Memo {
case (Nil, 0) => Seq(Nil)
case (Nil, _) => Nil
case (a :: as, x) => (f(as, x - a) map {_ :+ a}) ++ f(as, x)
}
f(s, t)
}
Der TypMemo ist in einer anderen Datei implementiert:
case class Memo[I <% K, K, O](f: I => O) extends (I => O) {
import collection.mutable.{Map => Dict}
val cache = Dict.empty[K, O]
override def apply(x: I) = cache getOrElseUpdate (x, f(x))
}
Meine Fragen sind:
Warum isttype K deklariert als(Int, Int) in subsetSum?
Was macht dieint im(Int, Int) stehen für jeweils?
3. Wie geht das?(List[Int], Int) implizit konvertieren zu(Int, Int)?
ich sehe keinenimplicit def foo(x:(List[Int],Int)) = (x._1.toInt,x._2). (auch nicht in derImplicits.scala Datei importiert.
* Edit: Nun, ich vermisse das:
implicit def encode(key: (List[Int], Int)) = (key._1.length, key._2)
Ich mag Pathikrits Bibliothekscalgos sehr viel. Es gibt viele Scala-Perlen darin. Bitte helfen Sie mir dabei, damit ich Pathikrits Witz zu schätzen weiß. Danke. (: