# Is there a generic way to memoize in Scala?

I found a better way to memoize using Scala:

``````def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() {
override def apply(key: I) = getOrElseUpdate(key, f(key))
}
``````

Now you can write fibonacci as follows:

``````lazy val fib: Int => BigInt = memoize {
case 0 => 0
case 1 => 1
case n => fib(n-1) + fib(n-2)
}
``````

Here’s one with multiple arguments (the choose function):

``````lazy val c: ((Int, Int)) => BigInt = memoize {
case (_, 0) => 1
case (n, r) if r > n/2 => c(n, n - r)
case (n, r) => c(n - 1, r - 1) + c(n - 1, r)
}
``````

And here’s the subset sum problem:

``````// is there a subset of s which has sum = t
def isSubsetSumAchievable(s: Vector[Int], t: Int) = {
// f is (i, j) => Boolean i.e. can the first i elements of s add up to j
lazy val f: ((Int, Int)) => Boolean = memoize {
case (_, 0) => true        // 0 can always be achieved using empty list
case (0, _) => false       // we can never achieve non-zero if we have empty list
case (i, j) =>
val k = i - 1            // try the kth element
f(k, j - s(k)) || f(k, j)
}
f(s.length, t)
}
``````

EDIT: As discussed below, here is a thread-safe version

``````def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() {self =>
override def apply(key: I) = self.synchronized(getOrElseUpdate(key, f(key)))
}
``````