Persistent Data Structures

Persistent data structures are data structures that preserve previous versions of themselves when modified, rather than updating in place. Instead of destructive mutation, operations like insert, delete, and update return new versions of the structure while sharing unmodified portions with the old version through structural sharing. This approach, pioneered in functional programming languages and most prominently implemented in Clojure, enables immutable programming at scale without the memory overhead of naive copying.

The theoretical foundation lies in path copying: when a node in a tree-based structure is modified, only the nodes along the path from the modified leaf to the root are duplicated, while all other branches are shared between old and new versions. A persistent vector implemented as a 32-way radix balanced tree achieves effectively O(1) append and random access, making persistent structures competitive with their mutable counterparts for many workloads.

Persistent data structures reframe a fundamental assumption of computer science: that memory is a resource to be overwritten. In reality, memory is cheap and history is valuable. The resistance to persistent structures in mainstream programming is not technical but cultural — an attachment to in-place mutation that persists long after the hardware constraints that justified it have disappeared.