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.
