Memoization

Don Syme blogged this quite some years ago but it just came up in a design review on my team this afternoon and it bears repeating.

let memoize f =
    let cache = new Dictionary<_,_>()
    (fun x ->
        match cache.TryGetValue x with
        | true, res -> res
| _ -> let res = f x in cache.Add(x, res); res)

This generic function takes a function and returns a new caching version of it. So simple!

You can then take some expensive function such as the standard example Fibonacci:

let rec fib = function
    | 1 | 2 -> 1
    | n -> fib (n - 1) + fib (n - 2)

Which is quite expensive when written this naïvely because of the exponential number of recursive calls; most with the same arguments.

> fib 42;;
Real: 00:00:01.663, CPU: 00:00:01.669, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 267914296

It takes 1.663 seconds for fib 42!

Okay, let’s make a memoized version:

let rec fastFib = memoize (function
    | 1 | 2 -> 1
    | n -> fastFib (n - 1) + fastFib (n - 2))

It really can’t be any easier than that! Note that because it's a recursive function simply saying let fastFib = memoize fib doesn't work.

> fastFib 42;;
Real: 00:00:00.000, CPU: 00:00:00.001, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 267914296

Viola!