not<\/em> necessarily clearer to show code. The concept of
\na zipper is very simple and elegant – but when you see a zippered tree
\nwritten out as a sequence of type constructors, it’s confusing, rather
\nthan clarifying.<\/p>\n<\/p>\n
The basic idea of a zipper is to give you a way of efficiently working with data
\nstructures in a functional language. There are a lot of cases where in an imperative
\nlanguage, there’s some basic operation which is cheap and simple in the imperative
\nlanguage, because it’s performed by an in-place update. But in a functional language,
\nyou can’t update a field of a data structure: instead, you have to create a new copy of the structure with the altered
\nfield. <\/p>\n
For example, consider the list [a b c d e f g]<\/code>. Implemented
\nas a cons-list, it’s a list of 7 cons-cells. Suppose you wanted
\nto replace “e” with “q”. In an imperative language, that’s no problem: just
\ndo a set-car! of the 5th cell. In a functional language, you would
\nneed to create a new list with “q” instead of
\n“e”. You could re-use the common tail [f g]<\/code>, but you would need
\nto re-create the other 5 cells: you’d need to create a new cell to
\nattach “q” to [f g]<\/code>. Then you’d need to create a new
\ncell to connect “d” to [q f g]<\/code>. And so on.<\/p>\n That makes the functional program much slower than the imperative one.
\nIf you’ve got a data structure that conceptually changes over time, and you’re going to make lots of changes,
\nthe cost of doing it functionally can become very high, because of all of the copying
\nyou do instead of mutating a data structure.<\/p>\n
In general, it’s very hard to get around that. You can’t update in place
\nin a functional language (at least, not without some serious cleverness, either
\nin your code (like monads), you language (like linear types), or your compiler).
\nBut for many applications, there’s some notion
\nof a focus point<\/em> – that is, a particular key point where changes
\nhappen — and you can build structures where updates around the focus<\/em>
\ncan be performed efficiently.<\/p>\n For example, if you’re building a text editor, you’ve got the point
\nwhere the cursor is sitting – and the changes all happen around the cursor.
\nThe user might type some characters, or delete some characters – but it always
\nhappens around the cursor.<\/p>\n
What a zipper does is take a data structure, and unfold it around a focal
\npoint. Then you can make changes at the focal point very quickly – about as
\nquickly as an in-place update in an imperative language.<\/p>\n
The idea of it is a lot like a gap-buffer. Right now, I’m actually working
\non a text-editor. I’m writing it using a gap-buffer. Conceptually, an
\nedit-buffer is one continuous sequence of characters. But if you represent it
\nas a continuous sequence of characters, every insert is extremely expensive.
\nSo what you do is split it into two sub-sequences: one consisting of the
\ncharacters before<\/em> the cursor point, and one consisting of the
\ncharacters after<\/em> the cursor point. With that representation,
\ninserting a character at the cursor point is O(1). Moving by one character is
\nalso O(1). Moving by N characters is O(N). With various improvements, you can
\ndo much better than that – but the key bit is that split between before the
\nfocus point and after it.<\/p>\n A zipper is a tree or graph-based version of a similar idea. For this
\ndiscussion, I’ll describe it in terms of trees; the graph version is more complicated,
\nbut you should be able to get the idea from seeing how it works on trees. The
\nidea is that you take the tree structure, and you split it around a focus. You’re focused on some node in the
\ntree. You keep track of a set of nodes that come before<\/em> you, and a
\nset of nodes that come after<\/em> you – those are basically like the
\npre-gap and post-gap regions of a gap buffer. But because you’re working in a
\ntree, you need a bit more information: you need to know the path<\/em> from
\nthe root of the tree down to the current node. <\/p>\n It’s called a zipper because what you do to create this pre-focus, path,
\nand post-focus bits of the structure is unzip<\/em> the tree. For example,
\nlook at the tree below. It’s a representation of a string of text represented
\nby a tree. In this particular tree, all of the data is stored in the leaves.
\nThe internal nodes contain metadata, which I haven’t shown in the diagram.<\/p>\n![\"string-tree.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_413.png?resize=389%2C202\")
<\/div>\n
Now, suppose I want to put the focus on “mno”. To do that, I climb down
\nthe tree, unzipping<\/em> as I go. I start at the root, node N1. Then I go
\nright. So I put N1 and its left subtree into the left-context of my
\nzipper-tree, and add “Right at N1” to the path. That puts the focus at N3. To
\nget to “mno” from N3, I need to go left. So I put N3 and its right child into
\nthe right context, and add “Left at N3” to the path. Now the focus is at N4.
\nTo get to “mno”, I need to go right: so I put N4 and its left child into the
\nleft context, and add “Right at N4” to the path. Now I’ve got the focus set
\nwhere I want it at “mno”; and I’ve got right and left contexts.<\/p>\n![\"string-tree-zippered.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_414.png?resize=447%2C231\")
<\/div>\n
With the zipper, you can make all sorts of changes very easily at the
\nfocus. Suppose I want to change the focus node, by inserting some text. I can
\ndo that functionally, without actually changing anything, by creating a new
\nzipper tree which is identical to the old one, but which changes the value of
\nthe focus node – that is, if I were to add “123” right after “mno”, I could do
\nit by creating a new focus node “mno123”, with the same path, left, and right
\ncontexts. It takes minimal extra memory to create the copy, because I can
\nre-use the path and the contexts. <\/p>\n
I could also add new children nodes. Suppose that instead of adding
\n“123” to the focus, I want to keep each leaf containing three characters.
\ncould replace the focus with a new node, N5, which had children “mno”
\nand “123”. I could re-use the “mno” node, and the path, left, and right
\ncontexts.<\/p>\n
![\"string-tree-zippered-and-edited.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_415.png?resize=497%2C231\")
<\/div>\n
That’s the beauty of the zipper: most operations can be in terms of local
\nchanges, re-using most of the structure. If we were using a standard tree,
\nthen to add a new node in the position of “mno”, we would need to create
\ncopies of N4, N3, and N1; instead, we only need to create the one new
\nnode.<\/p>\n
Doing other things isn’t that difficult either. Suppose we wanted to move
\nthe focus to “pqr”. We’d need to shift the focus from “mno” to N3, then to N3,
\nand then to “pqr”. To get from “mno” to N4, we take the last step off of the
\npath – which says we went right at N4 – so we set the focus to N4, and
\nre-establish “mno” as its right child. So the focus would be N4, with “jkl” as
\nits left child, and “mno” as its right child. To get from N4 to N3, we unroll
\nanother step of the path: since we went left at N3, that means that N3 is the
\nnew focus, with N4 as its left child. Then we’d go down to the right from N3,
\nso we’d add “right at N3” to the path, and “pqr” would be the new focus.
\nMoving the focus like that is a tad more difficult than just traversing
\nnon-zipper tree, but it’s not significantly slower – and it makes the edits
\nmuch, much<\/em> faster.<\/p>\n 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<\/em> 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.<\/p>\n You’ve got two choices. One is to re-balance
\nthe tree immediately. You can definitely do that. For
\nexample, if you think of how you do a re-balance in
\na 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
\nlocal operation. Much of the time, you can do things
\nlocally, but sometimes you’ll be stuck re-zipping as you move the focus up the tree fixing the balance; in
\nthe worst case, you need to re-zip the entire tree, all the way to the root.<\/p>\n
The alternative is something called scarring<\/em>. You put marks in the tree called scars that identify places where you made changes that could trigger a rebalance. (Or more generally,
\nin 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
\nthe 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
\nthe 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. )<\/p>\n Either way, it gets a bit more complicated – and when you look at the code
\nfor a zipper, the re-balancing\/invariant fixing has a tendency to dominate the complexity
\nof the code. The zipper itself is so simple and so elegant that it just disappears under
\nthe weight of tree-balancing.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[83,89],"tags":[],"class_list":["post-839","post","type-post","status-publish","format-standard","hentry","category-data-structures","category-haskell"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-dx","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/839","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=839"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/839\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=839"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=839"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=839"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![](\"http:\/\/upload.wikimedia.org\/wikipedia\/commons\/f\/f0\/Zipper_animated.gif\")
<\/p>\n