3
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.