Memoization in F#

Sometimes functions are asked recompute the same value over and over again. Why do all that extra work?

Memoization is here to help!

What is memoization?

Memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

wikipedia

It stores function results that we’ve already computed. And will return the previous results instead of having to recompute.

So it works just like a cache does, instead of caching db or api calls, it’s caching function calls.

Fibonacci Algorithm

Fibonacci is a pretty simple recursive function.

let rec fib(n: int):int = 
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n - 2)

Running this will work, but it slows down very quickly. Every call to fib triggers two more calls to fib, which means it’s exponential.

Not good! 😥

Lets memoize it!

Memoization

As mentioned earlier, memoization stores previously computed values for reuse.

Here’s what that looks like in F#.

let memoize f =
    let dict = Dictionary<_, _>();
    fun c ->
        let exist, value = dict.TryGetValue c
        match exist with
        | true -> value
        | _ -> 
            let value = f c
            dict.Add(c, value)
            value

• It takes a function f as input.
• Internally it creates a dictionary.
• Everytime f is called, it first checks to see if value exists:
  • If it exists, it returns the value. Potentially saving tons of work.
  • If it doesn’t exist, it computes the value, stores it for later reuse, then returns it.

Notice that our Dictionary is generic <_, _>, so this is a general purpose memoize function.

Fibonacci + Memoization

To leverage that, we’ll compose (+1 functional languages) both our methods:

let memoFib = memoize fib

let run = memoFib 2 |> printfn "%i"

Now our fibonacci function has been memoized! Any call to memoFib is now efficient because there’s no recomputation of the same value.

Memoize It All

Now that you know about memoization, make sure every function you create is memoized.

Jk, don’t do that. That’d be weird.