While we are quite happy with the result in the preceding implementation, it feels a little unsatisfactory because we have to write the same code every time we need to memoize a new function. Wouldn't it be nice if the cache is automatically maintained? Realistically, we just need one cache for each function that we want to memoize.

So, let's do it a little differently. The thought is that we should be able to build a higher-order function that takes an existing function and return a memoized version of it. Before we get there, let's first redefine our fib function as an anonymous function, as follows:

fib = n -> begin
    println("called")
    return n < 3 ? 1 : fib(n-1) + fib(n-2)
end

For now, we have added a println statement just so that we can validate the correctness of our implementation. If it works properly, fib should not be called millions of times. Moving on, we can define a memoize function as follows:

function memoize(f)
    memo = Dict()
    x -> begin
        if haskey(memo, x)
            return memo[x]
        else
            value = f(x)
            memo[x] = value
            return value
        end
    end
end

The memoize function first creates a local variable called memo for storing previous return values. Then, it returns an anonymous function that captures the memo variable, performs cache lookup, and calls f functions when it is needed. This coding style of capturing a variable in an anonymous function is called a closure. Now, we can use the memoize function to build a cache-aware fib function:

fib = memoize(fib)

Let's also prove that it does not call the original fib function too many times. For example, running fib(6) should be no more than 6 calls:

That looks satisfactory. If we run the function again with any input less than or equal to 6, then the original logic should not be called at all, and all results should be returned straight from the cache. However, if the input is larger than 6, then it calculates the ones above 6. Let's try that now:

We cannot conclude what we did is good enough until we benchmark the new code. Let's do it now.

The original function took 433 ms to compute fib(400). This memoized version only takes 50 ns. This is a huge difference.