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!