Deduplication replaces repeated data with references to one shared representation. Its value depends on what counts as identical: repeated grid regions, common word prefixes, and equivalent graph nodes call for different tests. Sharing immutable data is especially useful because a shared object cannot later change for one user but not another. section 4.4.1 section 5.2 section 5.4.2
A large grid with familiar patches
An immutable quadtree can reuse one node wherever the same square of cells appears. Memoizing its construction makes grid storage depend on the amount of variation rather than the number of cells. HashLife also memoizes a region’s future state: once a common large region has been advanced, another occurrence can reuse that result. This is not a promise of constant-time simulation from the start. Chaotic early evolution performs poorly, and the memoization caches can consume substantial memory; settled, recurring regions are where the gains appear. section 4.4.6 section 4.4.1
A trie tackles a different kind of repetition. More than 750 words in ENABLE start with anti, so storing each word as a separate string repeats that prefix many times. In a trie, those words traverse the same prefix path. Further compression can merge nodes that are functionally indistinguishable as states of a finite-state automaton. Building an entire trie before minimizing it may be impractical if the trie itself will not fit in memory. section 5.2 section 5.3
For a directed acyclic word graph, keep a hash set of canonical, fully optimized nodes. A candidate matches a canonical node when their end-of-word status and outgoing edges agree, with corresponding edges leading to the same canonical child objects. Order edge labels consistently when computing hashes. Do not mutate a node after inserting it into the set: changing its hash would make membership checks unreliable. section 5.4.2
Listing 5.7 Finishing the Node equality comparer
public int GetHashCode(Node n)
{
var h = new HashCode();
h.Add(n.IsEnd);
foreach(var e in n.EdgeLabels.OrderBy(c=>c))
{
h.Add(e);
h.Add(n.FollowEdge(e)); #1
}
return h.ToHashCode();
}
}
The equality comparer hashes end-of-word status, sorted edge labels, and child references, making the canonical-node lookup concrete. section 5.4.2
The same sharing idea can prevent a surprising blow-up in binary-term unification. Substitution can produce an exponentially large expanded term; memoized factories for immutable terms can instead share equal subterms, yielding a linear-size graph in the illustrated case. A smaller, related use of deduplication appears in the occurs check: a hash set ensures that a hole appearing repeatedly is enumerated only once. That removes repeated checks rather than merging term representations. section 10.2 section 10.1.2
