The Zipper

An immutable tree can be walked downward for free: a child is a value already held by its parent. Walking back up has no answer, because a node stores no reference to whoever points at it. Adding a parent field would fix that and break immutability at the same time — the field must be filled in after the parent exists, and a subtree carrying a parent pointer belongs to exactly one tree and can no longer be shared between two.

A zipper is the alternative Huet published in 1997. It represents a position in a tree as a pair: the subtree currently in focus, and a context describing the entire rest of the tree as seen from that position. The tree is not modified and no node gains a field. The pair is a different value that carries the same information, arranged so that every local move is a constant-time rearrangement of it.

The context is the path from the focus back to the root, stored in reverse and turned inside out. For a binary tree it has three forms: Top, meaning the focus is the root; Left(c, r), meaning the focus is the left child of a node whose right child is r and whose own context is c; and Right(l, c), the mirror image. For an n-ary tree each frame holds the left siblings in reverse order, the right siblings in order, and the parent's context.

Each frame records what was set aside to descend one level and which side the descent took. The complete state is (focus, context), called a location. The original root is not stored anywhere in it: the root is recoverable from the context, and while the cursor is elsewhere it does not need to exist as a value.

Take the seven-node tree with root a, children b and c, and b's own children d and e, and walk a cursor from the root down to e. At the start the focus is the whole tree and the context is Top, meaning nothing has been set aside yet: the focus is the root.

The first step goes left. The value b is already sitting inside a, so making it the focus costs nothing — but the rest of the tree has to go somewhere, or the way back would be lost. It goes into a frame that records two things: that the step went left, and that the sibling subtree c was passed on the way. Nothing about b is written into that frame, which is exactly why the focus can later be swapped without disturbing it.

The second step goes right, from b down to e, pushing a second frame that records the direction and the sibling d. The cursor now stands on e with a two-frame context, and those two frames plus the focus contain the whole tree between them, reorganised so that the current position is at the front instead of buried at depth two. No node was copied, no node gained a parent field, and each step read two fields and allocated one frame — O(1), whatever the depth.

To move to the left child, take the focus apart. Its left subtree becomes the new focus, and a new frame Left(c, r) is pushed onto the context, holding the right subtree that was just set aside and the previous context c. Moving right is symmetric. The step allocates one frame and reads two fields.

The cost is O(1) and does not depend on the size of the tree or the depth reached. The subtree set aside is stored by reference, so descending past a subtree of any size costs the same as descending past a leaf. A descent of d levels builds a context of d frames, which is the only storage the traversal uses beyond the tree itself.

Moving up pops one frame and reverses the descent. From Left(c, r), rebuild the parent node from the current focus and the saved sibling r, make that node the focus, and restore c as the context. The parent is reconstructed rather than looked up, which is why no parent pointer was needed. This is also O(1): one node is allocated and one frame is discarded.

Moving to a sibling is up followed by down, or in the n-ary form a single step that transfers one subtree between the left-siblings list and the right-siblings list of the current frame. Every navigation primitive — down, up, left, right — is constant time, so the cost of a traversal is proportional to the number of moves made rather than to the size of the tree or the depth of the target. A traversal that visits every node does O(n) total work.

Continue from the cursor standing on e. Replacing the focus is a single assignment: put a different subtree where e was and leave the context alone. This works because the frames describe what sits beside the focus, never what sits at it — no frame has to be rewritten, and no ancestor is touched, so the edit itself is O(1) no matter how deep the cursor is or how large the tree is.

Climbing back out is where the new tree gets built. Moving up pops the innermost frame, which says the step down went right past the sibling d; that is enough to construct a new b whose children are d and the edited focus. Moving up again pops the outer frame, which says left past c, producing a new a from c and the new b. The context is Top once more, so the focus is now the root of the edited tree.

Three nodes were allocated — the edited focus and one node per level climbed — and everything else was carried over by reference: c and d in this small tree, and in a real one, every subtree hanging off the path. Meanwhile the original root is still a perfectly good value describing the tree before the edit, which is what makes undo, snapshots, and sharing across threads fall out of the structure rather than being bolted on.

Replacing the focused subtree is one field assignment on the location: keep the context, substitute a different tree. It costs O(1) and does not touch the ancestors, because the ancestors are not represented as nodes pointing at the focus — they are frames that will be reassembled around whatever the focus happens to be when the walk comes back up.

Insertion and deletion at the focus follow the same pattern in the n-ary form, where the frame holds sibling lists: inserting a sibling conses onto one of the two lists, and deleting the focus promotes a sibling out of one of them. A sequence of edits under a single subtree therefore costs one constant-time operation each, with the path to the root paid for once, on the way in and the way out.

The whole tree is recovered by moving up until the context is Top. Each step allocates one node, so the cost is O(d) in the current depth and the result is a complete tree reflecting every edit made along the way. Huet's paper gives this as the top operation, and it is the only place the full structure is materialised.

The nodes allocated are exactly those on the path from the focus to the root; every subtree hanging off that path is carried over by reference. An edit deep in a large tree therefore produces a new tree that shares all but d nodes with the old one, and both remain valid. This is the same path-copying accounting that a rope performs on a split, applied to an arbitrary tree shape rather than a sequence.

A list is a tree with one child per node, and its zipper is the simplest case: a pair of lists, the elements before the focus stored in reverse order and the elements after it stored forward, with the focused element between them. Moving one step transfers a single element from one list to the other, which is O(1), and inserting or deleting at the focus is a cons or an uncons.

The reversal is the mechanism. Because the elements before the focus are kept nearest-first, the neighbour on either side is always at the head of a list, so neither direction requires a scan. A doubly linked list provides the same moves by mutation; the list zipper provides them without mutation, so an old position remains a valid value after the cursor has moved on. The deque supports the same two-ended access for a different purpose: the deque exposes both ends of a sequence, while the zipper exposes both sides of an interior point.

The shape of the context is determined by the shape of the data, and the correspondence is exact. McBride showed in 2001 that the type of one-hole contexts for a container type is its formal derivative in the sense of calculus. A list of x has generating function 1/(1 − x), and its derivative 1/(1 − x)² is a pair of lists — the two lists of the list zipper. A binary tree satisfies T = 1 + x·T², and differentiating yields a list of frames, each of which is a node with one child position removed.

The practical content is that the context type is not invented per structure; it is read off the definition. Removing one position from a product leaves the other components, which is why a frame holds the siblings, and a sum contributes one alternative per constructor, which is why the binary-tree context has a Left case and a Right case. The derivation generalises to record types, fixed-arity nodes, and mutually recursive syntax trees.

Nothing in a zipper is mutated, so a location is a value that can be copied, stored, or handed to another thread with no synchronisation. Saving the location before an edit gives an undo entry that costs one word; the two versions of the document differ only in the nodes on one root-to-focus path and share the rest.

The bound on that sharing is depth. An edit under a balanced tree of n nodes copies O(log n) nodes, the same figure that makes persistent AVL trees and red-black trees practical. Under a degenerate tree it is O(n), so a zipper over an unbalanced structure inherits that structure's shape problem: the navigation stays constant time per move, but the number of moves needed to reach a node, and the cost of rebuilding the root afterwards, both follow the depth.

The mutable answer to the same problem is a parent pointer in every node, or a cursor object holding an explicit stack of ancestors. Parent pointers make upward movement a single dereference with no allocation, which is faster than reconstructing the node, and they cost one word per node whether or not any traversal is running. They also fix each node to one parent, so no subtree can be shared between two trees or between two versions of one tree, and every structural edit must repair the pointers of the moved nodes.

A cursor holding an ancestor stack is closer to a zipper: it stores the path outside the nodes, so the nodes stay shareable. The difference is that a cursor's stack references ancestors that already exist and become stale if the tree is edited underneath it, whereas a zipper's frames hold the siblings rather than the parents, so an edit at the focus leaves the frames valid and the parent is built fresh on the way up. Tree-sitter's TSTreeCursor takes the ancestor-stack form, keeping the path outside the nodes so that syntax trees remain shareable across parses.

A zipper gives constant-time movement in all four directions and constant-time edit at the focus, over an immutable tree, with no field added to any node and no restriction on sharing subtrees. Localised work is cheap: descending once and then editing repeatedly within a subtree pays the depth only at entry and exit. The context type is derived from the data type, so the implementation is short and total.

The costs are concentrated in access patterns that are not local. Reaching an arbitrary node requires navigating to it — there is no indexed jump — so random access costs the path length rather than a lookup, and a location is only meaningful for the tree it was derived from. Every upward move allocates, which is cheap under a generational collector and awkward without one. In a mutable single-owner setting, parent pointers do the same job with fewer allocations and less machinery, and are the better choice when sharing and persistence are not required.

The xmonad window manager encodes focus directly in its state type rather than tracking it separately. Its StackSet holds workspaces as a list punctured at the current one, and each workspace holds its windows as a Stack: a focused window, the windows above it in reverse order, and the windows below it. Both are zippers, so "focus the next window" and "move the focused window" are constant-time rearrangements, and the type makes an unfocused non-empty workspace unrepresentable. The design is attributed in the project's own writing to Huet's zipper by way of a suggestion from Wouter Swierstra.

Source-rewriting tools are the other established use. Clojure ships clojure.zip in its standard distribution, and rewrite-clj builds on it a zipper over parsed Clojure source in which whitespace and comments are ordinary nodes, so a tool can navigate to one form, replace it, and emit the file with the surrounding formatting intact. The formatter zprint, the linter splint, and rewrite-edn for configuration files all operate through that zipper.

Beyond these, the sources reviewed for this chapter do not identify a broad set of production systems that document using a zipper by name. The construction is standard in functional-language codebases and in the literature on structure editors — Huet developed it while working on one — but outside that setting the equivalent job is usually done with a mutable cursor holding an ancestor stack.

A zipper represents a position in an immutable tree as the focused subtree paired with a context: the path to the root, reversed, with the siblings set aside at each level. Down pushes a frame, up pops one and rebuilds the parent, sideways moves a subtree between sibling lists, and replacing the focus is an assignment. All four are O(1) and none of them mutates a node.

Reconstructing the whole tree costs O(d) and allocates only the nodes on that path, so an edit yields a new tree sharing everything else with the old one. What is given up is indexed access: a node is reachable only by navigating to it, and the position is tied to the tree it came from. The context type itself is not a design choice but the derivative of the data type, which is why one derivation covers lists, binary trees, and arbitrary syntax trees.