Every Edit Keeps the Old Tree Intact

When you wire a bonsai branch into a new position, the rest of the tree doesn’t move. When you prune, the trunk remains. The change is local; the unchanged structure persists.

Persistent data structures work the same way. You never mutate. Instead, you create a new version that shares everything that didn’t change. In a tree with a thousand nodes, updating one leaf allocates perhaps three or four new nodes — the rest are pointers to the original.

Clojure’s persistent vectors and maps rely on this. Here’s a tree where we “prune” a branch — creating a new tree that shares the unchanged portion:

(def trunk {:id :trunk
            :branches [{:id :left  :leaves [1 2 3]}
                       {:id :right :leaves [4 5 6]}]})

(defn prune-branch [tree branch-id]
  (update tree :branches
          (fn [bs] (remove #(= (:id %) branch-id) bs))))

(def pruned (prune-branch trunk :right))

;; trunk still has both branches
;; pruned has only :left — but :left's data is shared, not copied

The original trunk survives. The pruned version exists alongside it. If you kept every intermediate state of a bonsai over forty years, you’d have a time-lapse. Persistent structures give you that for free — every historical version remains accessible.

Ada approaches this differently. Without garbage collection, you manage the sharing explicitly:

type Node;
type Node_Ptr is access Node;
type Node is record
   Value : Integer;
   Left  : Node_Ptr := null;
   Right : Node_Ptr := null;
end record;

function Replace_Left (T : Node_Ptr; New_Left : Node_Ptr) return Node_Ptr is
begin
   return new Node'(Value => T.Value, Left => New_Left, Right => T.Right);
end Replace_Left;

The Right pointer in the new node points to the same subtree as before. We allocate one node, not the whole tree. Without a garbage collector, you’re responsible for knowing when the old root can be freed — but the structural sharing still works.

This is why functional languages love trees. Hash-array mapped tries (the structure under Clojure’s vectors) achieve O(log₃₂ n) updates with minimal allocation. You get immutability without copying everything.

I find the symmetry compelling. A bonsai artist trains a tree over decades, each wiring session leaving the previous form encoded in the wood’s growth rings. A persistent data structure keeps its history by the same principle — old shapes survive beside new ones, sharing what didn’t need to change.