Gibt es eine generelle Möglichkeit, in Scala zu memoisieren?

Question

Ich wollte das memoize:

def fib(n: Int) = if(n <= 1) 1 else fib(n-1) + fib(n-2) 
println(fib(100)) // times out 

Also schrieb ich das und das kompiliert raschend und arbeitet (ich bin überrascht, weil fib Referenzen selbst in seiner Erklärung):

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

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

println(fib(100))  // prints 100th fibonacci number instantly 

Aber wenn ich versuche, erklären fib innerhalb eines def, ich habe einen Compiler-Fehler:

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

Above nicht kompilieren error: forward reference extends over definition of value fib case n => fib(n-1) + fib(n-2)

Warum funktioniert die Deklaration der val fib in einem Def-Fehler aber außerhalb in der Klasse/Objekt-Bereich funktioniert?

Um zu klären, warum ich die rekursive memoized Funktion im def Umfang erklären möchte - hier ist meine Lösung für die Teilmenge Summe Problem:

/** 
    * Subset sum algorithm - can we achieve sum t using elements from s? 
    * 
    * @param s set of integers 
    * @param t target 
    * @return true iff there exists a subset of s that sums to t 
    */ 
    def subsetSum(s: Seq[Int], t: Int): Boolean = { 
    val max = s.scanLeft(0)((sum, i) => (sum + i) max sum) //max(i) = largest sum achievable from first i elements 
    val min = s.scanLeft(0)((sum, i) => (sum + i) min sum) //min(i) = smallest sum achievable from first i elements 

    val dp: Memo[(Int, Int), Boolean] = Memo {   // dp(i,x) = can we achieve x using the first i elements? 
     case (_, 0) => true  // 0 can always be achieved using empty set 
     case (0, _) => false  // if empty set, non-zero cannot be achieved 
     case (i, x) if min(i) <= x && x <= max(i) => dp(i-1, x - s(i-1)) || dp(i-1, x) // try with/without s(i-1) 
     case _ => false   // outside range otherwise 
    } 

    dp(s.length, t) 
    } 

Answer 1

Ich fand einen besseren Weg, mit Scala memoize:

def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() { 
    override def apply(key: I) = getOrElseUpdate(key, f(key)) 
} 

Jetzt können Sie schreiben Fibonacci wie folgt:

lazy val fib: Int => BigInt = memoize { 
    case 0 => 0 
    case 1 => 1 
    case n => fib(n-1) + fib(n-2) 
} 

Hier ist ein mit mehreren Argumenten (die Auswahl-Funktion):

lazy val c: ((Int, Int)) => BigInt = memoize { 
    case (_, 0) => 1 
    case (n, r) if r > n/2 => c(n, n - r) 
    case (n, r) => c(n - 1, r - 1) + c(n - 1, r) 
} 

Und hier ist die Teilmenge Summe Problem:

// is there a subset of s which has sum = t 
def isSubsetSumAchievable(s: Vector[Int], t: Int) = { 
    // f is (i, j) => Boolean i.e. can the first i elements of s add up to j 
    lazy val f: ((Int, Int)) => Boolean = memoize { 
    case (_, 0) => true  // 0 can always be achieved using empty list 
    case (0, _) => false  // we can never achieve non-zero if we have empty list 
    case (i, j) => 
     val k = i - 1   // try the kth element 
     f(k, j - s(k)) || f(k, j) 
    } 
    f(s.length, t) 
} 

EDIT: Wie unten diskutiert wird, ist hier eine Thread-sichere Version

def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() {self => 
    override def apply(key: I) = self.synchronized(getOrElseUpdate(key, f(key))) 
} 

Answer 2

Klasse/Merkmal Ebene val zu einer Kombination aus a kompiliert Methode und eine private Variable. Daher ist eine rekursive Definition erlaubt.

Lokale val s sind dagegen nur reguläre Variablen und somit ist eine rekursive Definition nicht erlaubt.

Übrigens, selbst wenn die von Ihnen definierte def funktioniert, würde es nicht tun, was Sie erwarten. Bei jedem Aufruf von foo wird ein neues Funktionsobjekt fib erstellt und es wird eine eigene Backing Map haben. Was man stattdessen tun sollten ist dies (wenn Sie wirklich ein def möchten, dass Ihre öffentliche Schnittstelle sein):

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

def foo(n: Int) = { 
    fib(n) 
} 

Answer 3

Scalaz eine Lösung für das hat, warum es nicht wiederverwenden ?

import scalaz.Memo 
lazy val fib: Int => BigInt = Memo.mutableHashMapMemo { 
    case 0 => 0 
    case 1 => 1 
    case n => fib(n-2) + fib(n-1) 
} 

Sie können mehr über memoization in Scalaz lesen.

Answer 4

Mutable HashMap ist nicht threadsicher. Auch das separate Definieren von Case-Anweisungen für Basisbedingungen scheint eine unnötige spezielle Behandlung zu sein, vielmehr kann Map mit Initialwerten geladen und an Memoizer übergeben werden.Das folgende wäre die Unterschrift von Memoizer, wo es eine Notiz (unveränderliche Karte) und eine Formel akzeptiert und eine rekursive Funktion zurückgibt.

Memoizer wie

def memoize[I,O](memo: Map[I, O], formula: (I => O, I) => O): I => O 

Jetzt können als

val fibonacci = memoize(Map(0 -> 0, 1 -> 1), fib) 

definiert werden

wo Kontext

def fib(f: Int => Int, n: Int) = f(n-1) + f(n-2) 

Fibonacci mit Memoizer aussehen würde Agnostiker Allzweck Memoizer ist gegeben eine folgende Fibonacci-Formel, definiert als

def memoize[I, O](map: Map[I, O], formula: (I => O, I) => O): I => O = { 
     var memo = map 
     def recur(n: I): O = { 
      if(memo contains n) { 
      memo(n) 
      } else { 
      val result = formula(recur, n) 
      memo += (n -> result) 
      result 
      } 
     } 
     recur 
     } 

Auch für faktorielle, eine Formel

def fac(f: Int => Int, n: Int): Int = n * f(n-1) 

und factorial mit Memoizer ist

val factorial = memoize(Map(0 -> 1, 1 -> 1), fac) 

Inspiration: memoization, Kapitel 4 von Javascript guten Teile von Douglas Crockford