What mechanisms does Scala provide for memoization?

Instruction: Discuss Scala's support for memoization and provide an example of how to implement it.

Context: This question challenges the candidate's ability to optimize Scala applications through memoization, including understanding the techniques and tools available for caching function results.

Updated

Memoization retains computed results so later requests for the same input can reuse them. A lazy val caches one successfully initialized expression; caching a function across many arguments needs a separate cache and a lifetime policy.

This bounded, single-threaded Fibonacci calculator caches a prefix and avoids recursive stack growth:

def fibonacciMemo(maxN: Int): Int => BigInt = {
  require(maxN >= 0 && maxN <= 10000, "maxN must be in 0..10000")
  val saved = scala.collection.mutable.ArrayBuffer[BigInt](0, 1)
  (n: Int) => {
    require(n >= 0 && n <= maxN, "n is outside the configured range")
    while (saved.length <= n) {
      saved += saved(saved.length - 1) + saved(saved.length - 2)
    }
    saved(n)
  }
}
@main def memoExample(): Unit = {
  val fib = fibonacciMemo(1000)
  assert(fib(0) == 0 && fib(1) == 1)
  assert(fib(10) == 55 && fib(100).toString == "354224848179261915075")
  assert(fib(10) == 55)
}

Bind the returned function once to reuse its cache. Calling the factory again creates a fresh cache. The example caps its input by policy, uses BigInt to avoid numeric overflow and rejects negative inputs. Arithmetic and retained integers still grow with the requested index; caching is a memory/time tradeoff, not free computation. Mutable buffer operations

General caches need stable keys, a size or eviction policy, and decisions about failures and invalidation. Memoizing a function that reads changing external state can return stale results. This mutable cache must remain confined to one thread unless an explicit concurrency design is added; a concurrent map alone does not necessarily make multi-step computation atomic.

Related Questions