A persistent list is immutable: adding or updating elements creates a new version while preserving every earlier version. Rather than copying the entire collection, implementations use structural sharing, allowing versions to reuse unchanged data safely. section 9.5
The split that changes the cost
Suppose a list contains 100,000 elements. Splitting it repeatedly until pieces contain at most two elements gives a tree about 17 levels deep, so accessing or updating an element takes roughly 17 operations. Increasing the branching factor from 2 to 32 reduces the depth to about 3.3 levels. The asymptotic cost remains logarithmic, but the practical access cost drops substantially. section 9.2
Structural-sharing diagrams make the relationship between list versions visible: unchanged portions can be reused while each version remains available. section 9.2
The practical design principles are:
- Keep data immutable so versions can share internal structure safely. section 9.5
- Prefer a higher branching factor when access and update depth matter; the implementation described uses 32. section 9.2 section 9.5
- Use an existing library when appropriate; Paguro collections implement read-only Java collection interfaces without allowing mutation through those methods. section 9.5
