Zippers
A tree or list held by a cursor: the focused subtree plus the path back to the root, turned inside out so edits at the cursor are cheap and purely functional.
How they work
Updating one spot deep in a tree normally means copying its whole path from the root. That is fine once, but too slow when a program keeps editing the same area, like the buffer of a text editor. Gérard Huet’s zipper (1997) holds the tree by its current position instead of its root. A location is the focused subtree plus a path: the siblings to its left, the siblings to its right, and the parent’s path, with pointers from the root to the cursor reversed, “like a returned glove”.
Moving left, right or down and replacing, inserting or deleting at the cursor take constant time; moving up costs time proportional to the number of siblings to the left, because it rebuilds the parent node. Huet coined it for the structure editor of a proof assistant and wrote that the idea had probably been invented many times but never published. It works for any tree shape and in any language, functional or not, lazy or not.
Use a zipper for editors, tree walks that change nodes as they go, and anything with a cursor. Clojure ships one in the standard library as clojure.zip.