scala - tiempo - música para estudiar y memorizar

¿Hay una manera genérica de memorizar en Scala?

Question

Quería memorizar esto:

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

Así que escribí esto y esto sorprendentemente compila y funciona (estoy sorprendido porque fib referencia en su declaración):

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

Pero cuando trato de declarar fib dentro de una def , obtengo un error de compilación:

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

Arriba no se puede compilar el error: forward reference extends over definition of value fib case n => fib(n-1) + fib(n-2)

¿Por qué falla la declaración de val fib dentro de una definición, pero falla en el alcance de clase / objeto?

Para aclarar, ¿por qué podría querer declarar la función memorizada recursiva en el ámbito def? Aquí está mi solución al problema de suma de subconjuntos:

/**
* 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

Class / rasgo nivel val compila a una combinación de un método y una variable privada. Por lo tanto, se permite una definición recursiva.

Los val locales, por otro lado, son solo variables regulares, por lo que no se permite la definición recursiva.

Por cierto, incluso si la def que definió funcionó, no haría lo que esperaba. En cada invocación de foo se creará un nuevo objeto de función fib y tendrá su propio mapa de respaldo. Lo que debería hacer en su lugar es esto (si realmente quiere que una def su interfaz pública):

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 2

Encontré una mejor manera de memorizar usando Scala:

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

Ahora puede escribir fibonacci de la siguiente manera:

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

Aquí hay uno con múltiples argumentos (la función de elegir):

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

Y aquí está el problema de la suma de subconjuntos:

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

EDITAR: Como se explica a continuación, aquí hay una versión segura para subprocesos

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 3

Mutable HashMap no es seguro para subprocesos. También la definición de las declaraciones de casos por separado para las condiciones base parece un manejo especial innecesario, en lugar de eso, Map puede cargarse con los valores iniciales y pasarse a Memoizer. Lo siguiente sería la firma de Memoizer donde acepta una nota (Mapa inmutable) y fórmula y devuelve una función recursiva.

Memoizer se vería como

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

Ahora con la siguiente fórmula de Fibonacci,

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

fibonacci con Memoizer se puede definir como

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

donde el memorándum de propósito general agnóstico de contexto se define como

 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
}

Del mismo modo, para factorial, una fórmula es

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

y factorial con Memoizer es

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

Inspiration: Memoization, Capítulo 4 de las partes buenas de Javascript por Douglas Crockford

Answer 4

Scalaz tiene una solución para eso, ¿por qué no reutilizarla?

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

Puede leer más sobre la memorización en Scalaz .