How do I write a 100% memoize function?
For example, let's 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)
}
}
Then I can implement the 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 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, the function memoize
uses mutable state internally. I can override memoize
as a monad, so every time we call fib
it returns a tuple [value, fib] where it fib
now has something in the cache, leaving the original fib
unmodified.
The downside to the monad approach is that it is not idiomatic JavaScript and is difficult to use without a static type system.
Is there any other way to implement a function memoize
that avoids mutation without resorting to monads?
source to share
First, even in Haskell, which is "clean" by all reasonable standards, thunks are internally overwritten with their result after being evaluated - read the graph abbreviation . This is a trade-off 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. Think about what you would do in a purely imperative setup: dynamic programming. Have you thought about how you can build a function as a table lookup and then build that table from the bottom up. Now, what a lot of people use this is that it is just constructing a memoized recursive function.
You can include the principle, and in functional language use bottom-up to get an imaginary recursive function by simply creating a lookup table in its purest form:
fib n = fibs !! n where fibs = 0:1:zipWith (+) fibs (tail fibs)
Translated to 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 like this 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
similar to reduce
but retains intermediate accumulations, #::
is a minus for threads, and the value lazy val
is essentially a memoizing thunk.)
For further thinking about implementing fib
in the presence of graph shortening, see How is this memoacci function memoized? ...
source to share