A system needs undo, history, and safe updates. Copying the entire state for every change sounds simple—until the data grows. Structural sharing creates a new immutable version while reusing unchanged portions of the old structure. section 4.0 section 4.1
Updating Watchmen’s publication year
Suppose the library catalog stores Watchmen under a nested path. An immutable Lodash FP update returns a new catalog: _.set(libraryData, ["catalog", "booksByIsbn", "978-1779501127", "publicationYear"], 1986). Only the nodes along that path are recreated; unrelated catalog data remains shared. section 4.2
The technique separates safe data construction from state movement:
- Keep data immutable, but allow the state reference to move from one version to the next. section 4.1
- Calculate the next version with stateless immutable functions, then commit it through a common stateful phase. section 4.0 section 4.8
- Recreate only the path to changed data and reuse the unchanged branches instead of performing a deep copy. section 4.2 section 4.3
- Retain historical references when needed for time travel or undo; ordinary discarded versions can be removed by garbage collection. section 4.1 section 4.7
A short recursive implementation copies each map on the route to the changed value, replaces that route’s child, and returns the rebuilt root. The untouched branches remain shared. section 4.3 section 4.8
Naive structural sharing improves copying but does not itself prevent accidental mutation, and manually enforcing it becomes costly at scale. Persistent data structures address safety and performance by embedding sharing in their representation. section 9.1 section 9.2 section 9.5
A linked-list shortcut
For an immutable linked list with 100,000 elements, adding a new head does not require copying the list. The new head points to the existing list, preserving the previous version and making the operation independent of list size. section 9.2
Figure 4.4 Structural sharing provides an efficient way to create a new version of the data. Next Library is recursively made of nodes that use the parts of Library that are common between the two.
Visualizes how the next library recursively reuses nodes shared with the current library. section 4.2
