I'm trying to understand memoization using Scala. I took the Fibonacci sequence as an example because of the high cost of recursively computing numbers in the sequence without memoization.
class memoize private (val f: Int => Int) {
import scala.collection.mutable
val cache = new mutable.HashMap[Int, Int]()
def memoized_f(x : Int) : Int =
cache.getOrElseUpdate(x, f(x))
}
object memoize {
def apply(f: Int => Int) : Int => Int = new memoize(f).memoized_f
}
val fib : Int=>Int = memoize((n:Int) => {
if (n <= 1) n else fib(n-1) + fib(n-2)
})
With memoization the function fib
is called 10 times compared to 276 without it. I discovered that val fib
is required: def fib
results in the memo object being created on each call to fib
!
I realize that this could eventually be generalized by parameterising memoize
with a type T
(or key K
and value V
) to replace Int
. But I wanted to start somewhere simple to understand how the technique works. Given that I'm looking at memoizing only Int => Int
functions, could what I've done be improved in terms of function or style?
I've also discovered a couple of related items on the web: Is there a generic way to memoize in Scala? and Memo in ScalaZ (see also this tutorial), but I'm not entirely sure how what I've done relates to them.