1. 6
  1. 3

    I sometimes wonder if the benefits of immutable data structures aren’t overshadowed by the added complexity needed to use them efficiently in practice.

    Unless I’m misunderstanding, a Zipper is basically an iterator that makes traversing and updating immutable trees more efficient? Does anybody have real life examples of how these are used? Or maybe an example comparing a language with mutable data structures and Clojure with Zippers?

    1. 5

      I think it might be better to think of a zipper as something that gives you suspendable/resumable iteration. One place I find them useful is when building UIs where you need to step through a list of data. At work I use a zipper on a page where I have a list of items that are related to the main entity a user is viewing. The UI lets a user step back and forward through these one at a time with next/previous buttons. A zipper gives me all of these operations in O(1) time, and also lets me query the state for “is there a previous page? is there a next page?”.

      This is doable if you maintain a list of items along with the length of the list and some 0 <= i < length xs, but now I think all the operations I want become harder to obviously see, and also harder to obviously verify I got things correct (e.g., did I remember to increment i? Did I bounds check?)

      1. 3

        Thank you! It’s interesting to hear a real life use case, and I hadn’t considered the suspendable/resumable aspect. I can see that being a real benefit when iterating over a complicated structure.

        Is the interface extendable for user defined types? One gripe I have with Common Lisp is that the built-in iteration with (loop) isn’t easily extended for user defined types. The popular package ‘iterate’ allows it, but it’s an extra dependency to pull in.

        I suppose one day I should just learn Clojure.

        1. 4

          Yes, the interface is extensible–zippers basically take a few functions which define the children of a node, a root, and how to create new nodes. This makes them really convenient when you want to do ad-hoc modification of data structures that weren’t necessarily intended for traversal–say, for example, an HTML document, an SVG, a b*tree, a web API, or ad-hoc tree representations: (node child1 (child2 subchild1 subchild2)) or {:node "foo" :children [{:node "bar"} ...]}–you can lift them into a zipper, traverse or transform them in some way, then spit back a new structure without anyone being the wiser. If your trees are code, this is a nice way to write compiler optimizations and complex macros–you could, for instance, statically apply DeMorgan’s laws to simplify deeply nested boolean expressions in a complex conditional.

          This is super helpful for complex transformations like the kind you might do with XSLT/XPATH on XML documents: I could use a zipper to find instances of (e.g.) an image followed by a paragraph (at any level of nesting) within a <div> with a particular class, then rewrite that HTML to, I dunno, add some special tags and wrap both photo and following paragraph in a single div. Really handy for transforming, say, the results of a Markdown processor if the output it gives you isn’t quite right for the context you want to display it in.

          Of course you can do all this mutably too, but zippers give you two big advantages. One is that they allow you to extend tree traversal and manipulation over arbitrary structures that weren’t necessarily intended for it. Second, because the zippers themselves are immutable, you get some nice atomic properties: if I have a node with two children a and b, I can compute a new a' and b' and replace them atomically based on both a and b without having to create temporary variables or (potentially) deep copies. You get arbitrary rollback, it plays nicely with compare-and-set, etc.

          Not always the right solution–of course their performance isn’t going to be as good as direct traversal–but they’re a surprisingly useful tool. :-)