Sharing a list tail
An immutable list can contain a first element and a reference to its tail. Given the tail (b c), prepending a can allocate one new pair while both logical lists retain the same tail nodes.
Racket’s cons constructs such a pair. Its append copies preceding list spines but uses the final argument as the tail, illustrating how superficially similar composition operations can copy different portions.
References: [1]
Copying a tree path
With path copying, a changed leaf receives a new path from the root, while unaffected side branches remain shared. The old root describes the earlier version and the new root the updated version.
Benefits depend on shape and workload. Deep paths, widespread changes or many retained versions can still require substantial memory; structural sharing does not make every operation constant-cost.
References: [2]
Sharing and mutable contents
Sharing and immutability are related but distinct. If a collection stores an independently mutable object, two logical collections may observe changes through that shared object even when their outer structures remain unchanged.
Clojure’s transients demonstrate controlled editing with shared structure: the persistent source remains protected, while transient intermediate states cannot be retained arbitrarily or manipulated concurrently.