An immutable quadtree represents a square array of alive or dead cells without allowing its structure to change after creation. It becomes useful when a conventional Life implementation cannot meet performance goals: the unusual structure supports a larger algorithmic leap through memoization and HashLife rather than incremental tuning. section 4.0 section 4.3
Define an n-quad recursively. A 0-quad is one alive or dead cell. For n > 0, an n-quad contains four (n−1)-quads: northeast, northwest, southeast, and southwest. The result is a complete quaternary tree whose leaves are cells, whose nonleaf nodes always have four children, and whose side length is 2ⁿ. section 4.3
The definition fixes several useful invariants:
- Every path from an n-quad root to a leaf has exactly n edges. section 4.3
- Every internal node divides its square into four named quadrants, preserving spatial layout recursively. section 4.3
- The structure can describe arbitrarily large square cell arrays while retaining a uniform recursive shape. section 4.3
