Zippers: Making Functional "Updates" Efficient

In the Haskell stuff, I was planning on moving on to some monad-related
stuff. But I had a reader write in, and ask me to write another
post on data structures, focusing on a structured called a
zipper.

A zipper is a remarkably clever idea. It's not really a single data
structure, but rather a way of building data structures in functional
languages. The first mention of the structure seems to be a paper
by Gerard Huet in 1997, but as he says in the paper, it's likely that this was
used before his paper in functional code --- but no one thought to formalize it
and write it up. (In the original version of this post, I said the name of the guy who first wrote about zippers was "Carl Huet". I have absolutely no idea where that came from - I literally had his paper on my lap as I wrote this post, and I still managed to screwed up his name. My apologies!)

It also happens that zippers are one of the rare cases of data structures
where I think it's not necessarily clearer to show code. The concept of
a zipper is very simple and elegant - but when you see a zippered tree
written out as a sequence of type constructors, it's confusing, rather
than clarifying.

The basic idea of a zipper is to give you a way of efficiently working with data
structures in a functional language. There are a lot of cases where in an imperative
language, there's some basic operation which is cheap and simple in the imperative
language, because it's performed by an in-place update. But in a functional language,
you can't update a field of a data structure: instead, you have to create a new copy of the structure with the altered
field.

For example, consider the list [a b c d e f g]. Implemented
as a cons-list, it's a list of 7 cons-cells. Suppose you wanted
to replace "e" with "q". In an imperative language, that's no problem: just
do a set-car! of the 5th cell. In a functional language, you would
need to create a new list with "q" instead of
"e". You could re-use the common tail [f g], but you would need
to re-create the other 5 cells: you'd need to create a new cell to
attach "q" to [f g]. Then you'd need to create a new
cell to connect "d" to [q f g]. And so on.

That makes the functional program much slower than the imperative one.
If you've got a data structure that conceptually changes over time, and you're going to make lots of changes,
the cost of doing it functionally can become very high, because of all of the copying
you do instead of mutating a data structure.

In general, it's very hard to get around that. You can't update in place
in a functional language (at least, not without some serious cleverness, either
in your code (like monads), you language (like linear types), or your compiler).
But for many applications, there's some notion
of a focus point - that is, a particular key point where changes
happen --- and you can build structures where updates around the focus
can be performed efficiently.

For example, if you're building a text editor, you've got the point
where the cursor is sitting - and the changes all happen around the cursor.
The user might type some characters, or delete some characters - but it always
happens around the cursor.

What a zipper does is take a data structure, and unfold it around a focal
point. Then you can make changes at the focal point very quickly - about as
quickly as an in-place update in an imperative language.

The idea of it is a lot like a gap-buffer. Right now, I'm actually working
on a text-editor. I'm writing it using a gap-buffer. Conceptually, an
edit-buffer is one continuous sequence of characters. But if you represent it
as a continuous sequence of characters, every insert is extremely expensive.
So what you do is split it into two sub-sequences: one consisting of the
characters before the cursor point, and one consisting of the
characters after the cursor point. With that representation,
inserting a character at the cursor point is O(1). Moving by one character is
also O(1). Moving by N characters is O(N). With various improvements, you can
do much better than that - but the key bit is that split between before the
focus point and after it.

A zipper is a tree or graph-based version of a similar idea. For this
discussion, I'll describe it in terms of trees; the graph version is more complicated,
but you should be able to get the idea from seeing how it works on trees. The
idea is that you take the tree structure, and you split it around a focus. You're focused on some node in the
tree. You keep track of a set of nodes that come before you, and a
set of nodes that come after you - those are basically like the
pre-gap and post-gap regions of a gap buffer. But because you're working in a
tree, you need a bit more information: you need to know the path from
the root of the tree down to the current node.

It's called a zipper because what you do to create this pre-focus, path,
and post-focus bits of the structure is unzip the tree. For example,
look at the tree below. It's a representation of a string of text represented
by a tree. In this particular tree, all of the data is stored in the leaves.
The internal nodes contain metadata, which I haven't shown in the diagram.

Now, suppose I want to put the focus on "mno". To do that, I climb down
the tree, unzipping as I go. I start at the root, node N1. Then I go
right. So I put N1 and its left subtree into the left-context of my
zipper-tree, and add "Right at N1" to the path. That puts the focus at N3. To
get to "mno" from N3, I need to go left. So I put N3 and its right child into
the right context, and add "Left at N3" to the path. Now the focus is at N4.
To get to "mno", I need to go right: so I put N4 and its left child into the
left context, and add "Right at N4" to the path. Now I've got the focus set
where I want it at "mno"; and I've got right and left contexts.

With the zipper, you can make all sorts of changes very easily at the
focus. Suppose I want to change the focus node, by inserting some text. I can
do that functionally, without actually changing anything, by creating a new
zipper tree which is identical to the old one, but which changes the value of
the focus node - that is, if I were to add "123" right after "mno", I could do
it by creating a new focus node "mno123", with the same path, left, and right
contexts. It takes minimal extra memory to create the copy, because I can
re-use the path and the contexts.

I could also add new children nodes. Suppose that instead of adding
"123" to the focus, I want to keep each leaf containing three characters.
could replace the focus with a new node, N5, which had children "mno"
and "123". I could re-use the "mno" node, and the path, left, and right
contexts.

That's the beauty of the zipper: most operations can be in terms of local
changes, re-using most of the structure. If we were using a standard tree,
then to add a new node in the position of "mno", we would need to create
copies of N4, N3, and N1; instead, we only need to create the one new
node.

Doing other things isn't that difficult either. Suppose we wanted to move
the focus to "pqr". We'd need to shift the focus from "mno" to N3, then to N3,
and then to "pqr". To get from "mno" to N4, we take the last step off of the
path - which says we went right at N4 - so we set the focus to N4, and
re-establish "mno" as its right child. So the focus would be N4, with "jkl" as
its left child, and "mno" as its right child. To get from N4 to N3, we unroll
another step of the path: since we went left at N3, that means that N3 is the
new focus, with N4 as its left child. Then we'd go down to the right from N3,
so we'd add "right at N3" to the path, and "pqr" would be the new focus.
Moving the focus like that is a tad more difficult than just traversing
non-zipper tree, but it's not significantly slower - and it makes the edits
much, much faster.

So why is it harder to code? Because when we're dealing with trees, we're pretty much always dealing with balance. And balance isn't a local property. No matter which kind of tree you use - red/black, 2/3, AVL - you might need to climb up the tree to do the balance maintenance. That mangles the simple zipper.

You've got two choices. One is to re-balance
the tree immediately. You can definitely do that. For
example, if you think of how you do a re-balance in
a red-black tree, you climb up the tree doing fixes until you've got things rebalanced. You can definitely do that - by using the zipper to move around the tree. But a big part of the point of the zipper is to keep operations local, and the re-balancing is not a
local operation. Much of the time, you can do things
locally, but sometimes you'll be stuck re-zipping as you move the focus up the tree fixing the balance; in
the worst case, you need to re-zip the entire tree, all the way to the root.

The alternative is something called scarring. You put marks in the tree called scars that identify places where you made changes that could trigger a rebalance. (Or more generally,
in places where you made an edit that could have violated some invariant of the data structure.) You don't do the fix immediately - you just mark it with
the scar, and then at some point, whenever it makes sense for your application, you go back to the scars, and fix the tree. (Scaring can also have a more general meaning, which involves memorizing certain paths through
the tree, so that you can make changes at the leave, then a few steps up, then back at the leaf. It's a similar concept; in both forms of scarring, you're optimizing to reduce the cost of zipping up and down the tree. )

Either way, it gets a bit more complicated - and when you look at the code
for a zipper, the re-balancing/invariant fixing has a tendency to dominate the complexity
of the code. The zipper itself is so simple and so elegant that it just disappears under
the weight of tree-balancing.