I wanted to memoize this:
def fib(n: Int) = if(n <= 1) 1 else fib(n-1) + fib(n-2)
println(fib(100)) // times out
So I wrote this and this surprisingly compiles and works (I am surprised because fib
references itself in its declaration):
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
But when I try to declare fib inside of a def
, I get a compiler error:
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 fails to compile error: forward reference extends over definition of value fib
case n => fib(n-1) + fib(n-2)
Why does declaring the val fib
inside a def fails but outside in the class/object scope works?
To clarify, why I might want to declare the recursive memoized function in the def scope - here is my solution to the subset sum 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)
}
Scalaz has a solution for that, why not reuse it?
You can read more about memoization in Scalaz.
Mutable HashMap isn't thread safe. Also defining case statements separately for base conditions seems unnecessary special handling, rather Map can be loaded with initial values and passed to Memoizer. Following would be the signature of Memoizer where it accepts a memo(immutable Map) and formula and returns a recursive function.
Memoizer would look like
Now given a following Fibonacci formula,
fibonacci with Memoizer can be defined as
where context agnostic general purpose Memoizer is defined as
Similarly, for factorial, a formula is
and factorial with Memoizer is
Inspiration: Memoization, Chapter 4 of Javascript good parts by Douglas Crockford
I found a better way to memoize using Scala:
Now you can write fibonacci as follows:
Here's one with multiple arguments (the choose function):
And here's the subset sum problem:
EDIT: As discussed below, here is a thread-safe version
Class/trait level
val
compiles to a combination of a method and a private variable. Hence a recursive definition is allowed.Local
val
s on the other hand are just regular variables, and thus recursive definition is not allowed.By the way, even if the
def
you defined worked, it wouldn't do what you expect. On every invocation offoo
a new function objectfib
will be created and it will have its own backing map. What you should be doing instead is this (if you really want adef
to be your public interface):