Implementations of Memoization in F#

Today let’s talk about memoization.

This is the definition of memoization in Wikipedia:

“memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs.”

To put it simple, memoization is a technique by remembering the previous result of the function results. This implies that memoization is best to use as recursive functions, because it needs to call itself again!

The need to store values means that it needs mechanism to store result value.

To implement this mechanism, of course we need another helper variable to store the result.

Don Syme, the original creator of F# has this simple sample of memoization on his blog.

Here’s his starting sample:

There’s no further explanation about how the code above works. We’ll try to dive it together.

In his first sample, type checking on x (as x in the “fun x –>”) will always be performed.

He used System.Collections.Generic.Dictionary of <_,_> to map x as the key and fill the value with the result of computation of f x.

This is the power of type inference in action, so we can expressively map Dictionary<_,_> to have two kinds of generic type without naming it.

F# then will infer the first “_” as the key, and the second “_” as the type of the value.

The signature of “memoize f” is “('a -> 'b) -> ('a -> 'b)”.

The Dictionary used then will be used as a cache to store result value.

He further update the memoization sample.

This is the update using unchecked type:

And now using single mutable reference of Map:

The code above is more functional because it uses immutable F# Map instead of mutable System.Collections.Generic.Dictionary and also easier to understand, though using Unchecked is cleaner in some sense of C# perspective.