Function Memoization

One of my favorite pastimes is playing games.  No not XBox 360, PS3, or Wii games nor other computer games, but board games, card games, and other such games.  It's probably because I'm from a large family - I have 8 siblings - and we would often spend time together playing games.  It is a good way to accommodate a wide variety of interests, skills, and aptitudes.  Some of my favorite games are Settlers of Catan, Carcassonne, Spades, Rook, Mafia, Take Two, Stratego, Ticket to Ride, and of course Axis and Allies.

For my birthday this past year, I received an interesting board game titled RoboRally.  The premise of the game is there are a number of robots in a factory and they are bored, so they begin to indulge themselves by competing in races around the factory floor.  Each player takes command of a robot and seeks to win these competitions by controlling the robot.  The players are dealt a number of instruction cards whereupon each player elects five cards to load into his program registers.  After all the players have programmed their robots, their programs are executed somewhat simultaneously.  The robots can interact with each other by shooting, pushing, or otherwise hampering each other's progress.  But the real catch is that the board also interacts with the robots by way of conveyer belts, lasers, pushers, gears, pits, etc.  The uncertainty caused by the sheer number of interactions coupled with the deterministic behavior of programmed robots creates pandemonium.

One day I was just itching to write some code so I thought why not implement a computer version of RoboRally.  I thought that it would be particularly fun because of the number of interacting objects and the amount of state that is involved.  So I began to code away on a board editor.  This took a little bit of time mostly because I'm not very skilled at graphic art.  Here is a screenshot from an early version of the board editor.

The code for the editor consists of three assemblies: the windows application, a game engine, and a functional programming library.  This was one of the first non-trivial apps that I wrote using C# 3.0 and it was very fun to use the new language features.  In fact, it was incredible because I found that many design patterns that I commonly used changed drastically or were no longer needed.  Furthermore, I found that entirely new designs were possible.  Today, I will touch on just one of these design patterns and the underlying principle used in it.

The game engine has an class called Board and these boards are composed of many Tiles which are each associated with a Location.  Tiles can be simple or rather complex.  For instance, there are blank tiles and there are move left express conveyer belt tiles.  But there are also gear tiles with a normal wall on the top side and a laser wall on the left side which also have a flag on the tile.  I made a design decision early on to have basic tiles and decorator tiles.  So complex tiles are formed from the composition of a basic tile and any number of decorator tiles.  I wrote a factory which creates either some basic tile or some decorator tile.  For a first cut, I didn't worry that I created an overabundance of blank tiles even if they are all identical.  Nor did I worry about the fact that all move right conveyer tiles are the same.  However, later as I was refining the design I came back to the factory and wanted to improve it by reducing the number of tiles that were created to the bare minimum.  A typical solution to this problem for the blank tiles would look like this:

IBlankTile blankTile;
public IBlankTile CreateBlankTile()
if (blankTile == null)
blankTile = new BlankTile();
return blankTile;

But how do we do this for conveyer tiles?

Dictionary<Direction, IConveyerTile> conveyerTiles = new Dictionary<Direction, IConveyerTile>();
public IConveyerTile CreateConveyerTile(Direction direction)
IConveyerTile result;
if (!conveyerTiles.TryGetValue(direction, out result))
result = new ConveyerTile(direction);
conveyerTiles.Add(direction, result);
return result;

Ick!  It only gets even more complicated for tiles that are parameterized on more items.  Furthermore, it seems that there is a lot of repetition going on.  Specifically, all of the machinery to track instance existence and creation is being duplicated for each tile type.  To some extent the Singleton and Multiton patterns also suffer from the same problem.  There must be a better way.

In fact, there is a better way.  What we really want here is a function that returns the same value each time it is applied to the same parameter values.  Functional programmers will instantly recognize this as function memoization.

Memoization can be implemented as a function which takes a function as a parameter and returns a new function which when invoked the first time on some set of parameters will compute the result and when invoked with the same values will not recompute the result but will instead return the previously computed result.

Now let's see how our code would have looked if we had a static method called Memoize is a functional library called Fun (why not? functional programming is fun isn't it?).

public readonly Func<IBlankTile> CreateBlankTile = Fun.Memoize(() => new BlankTile());
public readonly Func<Direction,IConveyerTile> CreateConveyerTile = Fun.Memoize(dir => new ConveyerTile(dir));

The new code is beautiful and doesn't have all of the redundancy and complexity of the old code.  This is a very practical example of the modularity of functional style code that I referred to previously.

"But wait", you say, "how exactly does the magic happen?"  Well, let's take a look.  First, let's examine a memoize function which takes a function of no arguments and returns a memoized version of that function.

public static Func<R> Memoize<R>(this Func<R> f)
R value = default(R);
bool hasValue = false;
return () =>
if (!hasValue)
hasValue = true;
value = f();
return value;

Memoize takes a function which has no arguments and a return type of R and returns a function with the same signature.  When Memoize is called it creates two local variables value and hasValue. Memoize then returns a new function that returns value if hasValue is true otherwise it computes value by evaluating the parameter f, sets hasValue to true, and then returns value.  Notice that the function that is returned from Memoize accesses hasValue, value, and f.  These three variables are local to Memoize.  The three variables together with a reference to the function that is created by Memoize form a closure.

So what happens when we invoke the function returned from Memoize for the first time?  The variable hasValue will be set to false, so we will set hasValue to true and then apply f saving the result to value.  Finally, we will return the value which is the result of f.  So the memoized function will return the same thing that f would have returned on its first invocation.

But what about on subsequent invocations?  When we call memoized function again, hasValue will be true so we will simply return value without recomputing it.  So the memoized function will always return the same value as it did on the first invocation without recomputing the result through f.

This has subtle implications such as if f has side effects then those side effects will only occur when we apply the memoized function the first time.  So we need to be careful about using it.  But consider how CreateBlankTile used Memoize.  When CreateBlankTile is run the first time, it will create a blank tile and then return the result, but on subsequent invocations it will continue to return the same blank tile.  This is exactly the behavior that we want.

Can we do the same thing for functions that have arguments?  Absolutely, let's take a look at how to Memoize functions of one argument.

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
var map = new Dictionary<A, R>();
return a =>
R value;
if (map.TryGetValue(a, out value))
return value;
value = f(a);
map.Add(a, value);
return value;

This time instead of storing the computed values in a local variable directly, we store them in a dictionary and instead of marking that we have computed the value we just check for existence in the dictionary.  This can be generalized to functions of n arguments by creating composite keys of n fields that are used in the dictionary.

Consider how this Memoize function works with CreateConveyerTile.  When we invoke it with some direction for the first time then it will not find that direction in the dictionary and so it will create a new conveyer tile parameterized on that direction and then store it in the dictionary.  Subsequent calls with the same direction will not create new tiles but instead grab out the existing one from the dictionary.  Again this is the behavior that we want.  Furthermore, all of the mechanics of storing and fetching tiles are located in Memoize instead of CreateBlankTile or CreateConveyerTile.

Memoize is also useful for the improving performance of recursive functions.  Eric Lippert has a great post about how not to teach recursion where he specifically mentions not to use fibonacci numbers.  However, I'm going to use fibonacci numbers not to teach recursion but to show how to improve the performance of recursive functions.  Recall, that the definition of the nth fibonacci number where n >= 0 is:

fib(0) = 0

fib(1) = 1

fib(n) = fib(n - 1) + fib(n - 2) if n > 1

We can easily write a little function to do this:

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

The problem is this function is very inefficient.  Consider calculating the 5th fibonacci number.


  = fib(4) + fib(3)

  = fib(3) + fib(2) + fib(2) + fib(1)

  = fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + 1

  = fib(1) + fib(0) + 1 + 1 + 0 + 1 + 0 + 1

  = 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1

  = 5

Notice how the computation branches out forming a tree of expansions.  In fact, the number of leaves in a tree for the computation of the nth fibonacci number is fib(n + 1) where the number of ones is fib(n) and the number of zeros is fib(n - 1).

So calculating fib(5) will cause fib to evaluated twelve times (the sum of the fibonacci numbers from 0 to 5) but only six distinct calls will be made (fib(0), fib(1), ..., fib(5)).  The problem only gets worse because the fibonacci numbers grow very quickly.  Here are the first 20 fibonacci numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181

So our straightforward recursive function for computing fibonacci numbers will be exponential in n.  Ouch!  But wait, we can Memoize fib so that if it calls fib again with the same argument then it will not recalculate but instead use the previous result.  This will move our exponential function to a linear one at the cost of linear space to store the previous results (we could possibly use a weak reference hash map instead to solve problems with space if they existed).  In fact, subsequent calls to fib with previously computed values will be evaluated in constant time.

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
fib = fib.Memoize();

If you want, you can add a Console.WriteLine to show when the evaluations happen to both versions and compare.  It is very enlightening.

Memoize is turning into quite the useful function.  We have used it to solve parameterized identity creation problems and performance issues.  Later, we will see other ways we can use Memoize to solve design problems.