Memoization of Fibonacci using generic Int => Int helper

Question

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.

Answer 1

For generic memoization I pretty much always use scalaz Memo but when I compute sequences, I personally prefer using the standard Scala Stream.

Stream naturally memoize every computed value. Your solution could be refactored as:

lazy val fib = {
  def f(a: Int, b: Int): Stream[Int] = a #:: f(b, a + b)
  f(0, 1)
}

scala> fib.take(10) foreach println
0
1
1
2
3
5
8
13
21
34

scala> fib(45)
res1: Int = 1134903170