How do I write a 100% pure memoize function?

Question

For example, say this is my function:

let fib = n => {
  switch (n) {
    case 0: return 0
    case 1: return 1
    default: return fib(n - 1) + fib(n - 2)
  }
}

I can then implement a basic memoize function...

let memoize = fn => {
  let cache = new Map   // mutates!
  return _ => {
    if (!cache.has(_)) {
      cache.set(_, fn(_))
    }
    return cache.get(_)
  }
}

... And use it to implement a memoized fib:

let fib2 = memoize(n => {
  switch (n) {
    case 0: return 0
    case 1: return 1
    default: return fib2(n - 1) + fib2(n - 2)
  }
})

However, that memoize function uses mutable state internally. I can reimplement memoize as a monad, so every time we call fib it returns a tuple of [value, fib] where fib now has something in cache, leaving the original fib unmodified.

The downside of the monad approach is it is not idiomatic JavaScript, and is hard to use without a static type system.

Is there some other way to implement a memoize function that avoids mutation, without resorting to monads?

Answer 1

First, even in Haskell, which is "pure" by all reasonable standards, thunks are internally overwritten by their result after evaluation -- read about graph reduction. This is a tradeoff between purity and efficiency, which however hides the impurity from the user, and thus makes it an implementation detail.

But the answer to your question is yes. Consider what you'd do in a purely imperative setting: dynamic programming. You'd think about how you can construct the function as a table lookup, and then build that table from bottom up. Now, what many people applying this is that this just is building a memoized recursive function.

You can turn the principle around, and in a functional language use the "bottom-up table trick" to get a memoized recursive function, just by building the lookup table in a pure manner:

fib n = fibs !! n
  where fibs = 0:1:zipWith (+) fibs (tail fibs)

Translated to a lazy pseudo-JS:

let fibs = [0, 1, Array.zipWith((a, b) => a + b, fibs, fibs.tail)...]
let fib = (n) => fibs[n]

In Haskell this works by default, since it is lazy. In JavaScript, you can probably do something similar by using lazy streams. Compare the following Scala variant:

def fibonacci(n: Int): Stream[Int] = {
   lazy val fib: Stream[Int] = 0 #:: fib.scan(1)(_+_)
   fib.take(n)
}

(scan is like reduce, but keeps intermediate accumulations; #:: is cons for streams; and a lazy val value is essentially a memoizing thunk.)

For further pondering about the implementation of fib in the presence of graph reduction, see How is this fibonacci-function memoized?.