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.
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 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!
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
- Internally it creates a dictionary.
fis 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.