Suppose an immutable quadtree keeps producing the same pattern of cells. Rebuilding that pattern—or recomputing its future—does the same work again. Memoization trades memory for time: it stores a function’s arguments and result, then returns the stored result when those arguments recur. The function must be pure, so its result depends only on its inputs; immutable arguments keep a cached answer valid. section 2.1.5 section 4.3.4 section 10.2
Listing 4.3 A general-purpose one-argument memoizer
sealed class Memoizer<A, R> where A : notnull
{
private Dictionary<A, R> dict;
private readonly Func<A, R> f;
public Memoizer(Func<A, R> f)
{
this.dict = new Dictionary<A, R>();
this.f = f;
}
public R MemoizedFunc(A a)
{
if (!dict.TryGetValue(a, out R? r))
{
r = f(a);
dict.Add(a, r);
}
return r;
}
public void Clear(Dictionary<A, R>? newDict = null)
{
dict = newDict ?? new Dictionary<A, R>();
}
public int Count => dict.Count;
}
The C# memoizer wraps a one-argument function. On a dictionary miss, it calls the original function and stores the result; on a hit, it returns that result without recomputing. Count exposes the cache size, and Clear replaces the dictionary. section 4.3.4
One argument is enough for a quadtree factory: a tuple holds its four children. Memoizing that factory makes equivalent quads reuse one object instead of occupying separate space. An emptiness test can then compare a quad with the cached empty quad by reference. At the extreme, an empty level-60 quad represents a square with 2^60 cells on each side using only 61 objects. section 4.3.3 section 4.3.5
Caching the future
HashLife also applies memoization to a pure Step method. Repeated quads can then reuse computed future states rather than repeat a large recursive calculation. This is a different payoff from memoizing the factory: Step spends cache space to save computation, while the factory deduplicates the data structure itself. section 4.4 section 4.4.4
A cache is not automatically a win. In a 5,000-tick test of small Life configurations, the memoized implementation performed roughly like a naïve array implementation while its Step and Make caches accumulated millions of entries. Just 20 entries accounted for 40% of calls, yet half the entries were never hit again. Measure reuse, watch cache size, and provide a way to clear it: retaining rarely reused results can turn a performance aid into a memory problem. section 4.4.4 section 4.3.4
The same test—will identical inputs recur, and is the saved work worth the memory?—applies beyond Life:
- Memoizing queue reversal could soften repeated expensive operations during undo and redo. section 2.6.3
- Memoized term factories could make equality checks use reference equality; memoizing anti-unification itself could replace a repeated-results search. section 10.5
