# 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!