A pure function produces an output determined only by its input values. It neither reads nor changes global state, making the same input reliably produce the same result. section 4.3.4
That predictability enables memoization: cache the first result for each input and return the cached result on later calls. Immutable arguments are required so cached results remain valid. section 4.3.4 section 10.2
Purity has practical consequences:
- Memoization trades additional memory for less computation when repeated inputs occur. section 4.4.4
- A cache needs lifecycle controls because low-value entries can consume substantial memory; clearing or replacing the dictionary limits that cost. section 4.3.4
- Real measurements matter: a small number of frequently reused entries may provide most of the benefit while many entries remain cold. section 4.4.4
Memoizing a pure function
A one-argument memoizer stores each newly computed result in a dictionary, then returns that result for subsequent calls with the same input. The pattern applies to pure operations such as constructing or stepping immutable quadtrees. section 4.3.4 section 4.4.4
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;
}
Inspect the complete C# Memoizer implementation, including dictionary lookup, cache insertion, clearing, and entry counting. section 4.3.4
