Clojure Zippers - Part One

I started working on a replacement for the existing clojure.zip library with a couple of enhancements to support navigation by index or key. I went down a rabbit hole, finding things I didn't like about the existing implementation. Of course the more I learned the more I came to appreciate that it reflected good compromises. Still, Clojure has evolved since Rich Hickey wrote the original implementation and at the end of the day, I still wanted to make some changes.

This is the first of a three-part series.

Part One: Zipper Primer
Part Two: Clojure Implementation
Part Three: Extensions

Zipper Primer

Like Hickey, my starting point was the Functional Pearl paper published by Gérard Huet in 1997. I pored over Huet's paper until my eyes hurt -I have a barely detectable ability to read OCaml which probably handicapped me more than I would have liked to admit. But after much experimenting at the REPL I think I finally understand the Zipper. To help others in their quest to understand the Zipper, I've generated some diagrams focusing on some critical concepts.

This diagram shows a simple tree along with a path from the Root to a terminal leaf "element" (I avoid the term "node" because, as we'll see below, it has a different meaning in the context of Huet's zipper).

An element can be both contained within its parent and contain other elements. The green in the diagram below is the same value: at the third level it is contained within its parent alongside its siblings. At the fourth level we see that it is also a collection containing sub-elements in its own right.

This next diagram gets to the crux of the zipper. It shows the hierarchy of Node structures corresponding to the path shown above. Each Node is a three-tuple comprised of a list of left (Huet calls them "elder") siblings, a pointer to its parent Node and a list of right ("younger") siblings. There are five Nodes in this diagram (the purple Node at the top has a nil value in place of a pointer to its parent). It's essential to understand that the Node does not track the value between the left siblings and the right siblings. There is essentially a gap between the left and right.

If you squint just right, the above image evokes a zipper. Imagine recursively pulling each arrow up to the gap between its parent's left and right siblings. If you had the missing "gap" element from the bottom-most (blue) node, you could reconstitute the corresponding element. You could in turn pull the reconstituted blue element up to the red node above it and thus reconstitute a red element, and with that element you could... and so on up to the root to reconstitute the entire tree.

The Zipper uses the Loc data structure to explicitly track this bottom-most missing gap element. A Loc is a tuple of the path to the root (a linked list of Nodes as depicted above) plus the single element missing from the bottom Node. Below in green are the two components of a Loc for the eighth sibling of the third descendant of the example tree. The dark green is the gap element itself (frequently named t for "tree" in Huet's paper) while the light green is the recursive Node (frequently named p for "path" in Huet's paper). Keep in mind that p is the entire path to the root -I've only shaded the first Node, but the arrow pointing up should remind you that the entire path to the root is available recursively through ancestor Nodes.

Why Zippers?

What advantages do Zippers represent compared to alternative data structures?

An obvious advantage, compared to the raw tree, is that the Zipper represents the entire (possibly updated) tree and a current position (or focus). Said another way, Zippers are a purely functional way of navigating, modifying and pointing within an arbitrary tree.

Another notable advantage is the efficient editing of immutable data structures^[1]. For immutable data, the Zipper's recursive Node structure tracks the minimal set of elements that need to be re-written to effect any change. With no loss in expressivness, the necessary re-writing is deferred until "zipping" up the data structure; multiple changes are thus effected all at once, potentially minimizing expensive write operations.