In this tutorial, I’ll use sequences as trees. You can create your own kind of trees if you want, but I won’t cover that.
Here’s what we’ll be working with:
user=> (def original [1 '(a b c) 2]) #'user/original
It’s a tree whose root is a vector with three children: 1, the subtree
(a,b,c) and 2. We need to convert it into some sort of data structure that allows free movement. That’s done like this:
user=> (require '[clojure.zip :as zip]) nil user=> (def root-loc (zip/seq-zip (seq original))) #'user/root-loc
Notice that I used the alias
zip. If you
use clojure.zip, you’ll find yourself overwriting useful functions like
Notice also that I explicitly wrapped the tree in a seq. If you use seq-zip on an unwrapped vector, you’ll get confusing results.
At this point, I’d describe
root-loc as “the location (or loc) of the root of the tomorrow tree.” I say “tomorrow tree” because it’s not a tree itself, but something that can later be converted into a tree. In reality,
root-loc names both the loc and the tomorrow tree, bundled up together, but I think it most straightforward to leave the tomorrow tree implicit.
(The actual data structure is called a “zipper”, which is a decent analogy for the actual implementation but didn’t help me understand how to use the library.)
Moving around inside a tomorrow tree
With the loc, we can move around:
user=> original [1 (a b c) 2] user=> (zip/node (zip/down root-loc)) 1
zip/down moves to the leftmost child of the current loc and returns that child’s loc.
zip/node gives you the subtree of the original tree corresponding to its loc argument. It’s one of the main ways you get parts of a tree—regular lists, vectors, and the like—”out of” a tomorrow tree.
-> macro makes movement in the tomorrow tree much easier to understand:
user=> (-> root-loc zip/down zip/right zip/node) (a b c) user=> (-> root-loc zip/down zip/right zip/down zip/right zip/node) b
Nevertheless, I always wrap anything but the simplest traversals in their own functions.
Here are some other movement functions for you to try:
leftmost. Beware of (arguable) inconsistencies in the handling of edge cases. For example,
rightmost behave differently when moving “off the end” of a list of siblings:
user=> original [1 (a b c) 2] user=> (def last-one (-> root-loc zip/down zip/right zip/right)) #'user/last-one user=> (zip/node last-one) 2 user=> (-> last-one zip/right) nil ; off into nothingness user=> (-> last-one zip/rightmost zip/node) 2 ; stays put
Parts of a tree
In addition to
zip/node, there are other functions for recovering parts of the original tree. All work relative to the current loc.
user=> (def b (-> root-loc zip/down zip/right zip/down zip/right)) #'user/b user=> (zip/node b) b user=> (zip/lefts b) (a) user=> (zip/rights b) (c)
An interesting one shows all subtrees from the root of the tree down to just above the current loc:
user=> (zip/path b) [ (1 (a b c) 2) (a b c) ]
Changing the tree
A number of functions take a current loc (and associated tomorrow tree) and produce a new loc inside a different tomorrow tree. For example, let’s delete the ‘(a b c) subtree:
user=> (def loc-in-new-tree (zip/remove (zip/up b))) #'user/loc-in-new-tree
How does the tree represented by this new tomorrow tree differ from the
original tree? We can see that with the
root function, which applies
zip/node to the root of the tomorrow tree:
user=> (zip/root loc-in-new-tree) (1 2) user=> original [1 (a b c) 2]
Where, exactly, is the new location?
user=> (zip/node loc-in-new-tree) 1
The new loc has “backed up” from its previous version. (That’s not an exact enough description, but it’ll do for a few more paragraphs.) The other editing functions return an “unchanged” loc (except in the sense that it’s pointing into a new tomorrow tree with a changed structure):
append-child. Try them out.
In which I reveal I’m slow
At first, I easily forgot that these functions create a new tomorrow tree and don’t really “replace” or “insert” or “edit” parts of the old one. That is:
user=> (zip/root loc-in-new-tree) (1 2) ; I see that I've edited the tree. user=> (zip/root b) (1 (a b c) 2) ; Wait - I thought I changed the tree?!
“Well, duh”, you might say, “it’s a functional language with immutable state, so of course it doesn’t change the old tree.” You’re absolutely right, but it was surprisingly easy for old habits to sneak up on me. So, two rules:
If you ever fail to use the return value of one of these functions, you’re doing it wrong.
If you ever write code like this:
(let [stashed-location (zip/whatever ...)] ... make "changes" ... ... use stashed location ...)
you might be doing it wrong. Make sure that you’re not unthinkingly assuming that later changes to “the” tree are reflected in your
Here’s an example of printing out a whole tree, one node at a time:
(defn print-tree [original] (loop [loc (zip/seq-zip (seq original))] (if (zip/end? loc) (zip/root loc) (recur (zip/next (do (println (zip/node loc)) loc))))))
This is an ordinary recursive loop. It visits each location in the tomorrow tree, stopping when
zip/end? is true.
zip/next returns a new current loc that is the next one in the tomorrow tree, where “next” means “in preorder depth-first order”. To see that, here’s what one run of the function prints:
user=> (print-tree [1 '(a (i ii iii) c) 2]) (1 (a (i ii iii) c) 2) 1 (a (i ii iii) c) a (i ii iii) i ii iii c 2
To make changes to the tree, add a
cond. The default case should hand the current loc to
zip/next. The other cases should yield a loc pointing into a changed copy of the tomorrow tree:
(loop [loc (zip/seq-zip original-tree)] (if (zip/end?> loc) (zip/root loc) (recur (zip/next (cond (subtree-to-change? loc) (modify-subtree loc) … :else loc)))))
The tricky bit is making sure that
modify-subtree returns a loc just before the next loc of interest (in a depth-first traversal). (It has to be before so that
zip/next takes you to the interesting loc.) To get to that loc, you can use any of the movement functions (
zip/rightmost, and so on). There’s also a
zip/prev that returns the loc just before the current one.
To keep from confusing myself, I write little helper functions, each named by what it does and what loc it returns. So, for example, I have one function that glories in this name:
(defn wrap-with-expect__at-rightmost-wrapped-location [loc] (assert (start-of-arrow-sequence? loc)) (let [right-hand (-> loc zip/right zip/right) edited-loc (zip/edit loc (fn [loc] `(expect ~loc => ~(zip/node right-hand))))] (-> edited-loc zip/right zip/right zip/remove zip/remove)))
It takes a form like
... (f 1) => (+ 2 3) :next, with the current loc being
(f 1), and turns it into this:
... (expect (f 1) => (+ 2 3)) :next
… with the current loc being at the 3 so that the
zip/next returns a loc at
:next. This positioning works because I use
zip/remove, which returns a loc that’s “backed up” to the previous loc in a depth-first traversal. (That’s the fix to my earlier imprecision about what
zip/remove returns. It’s not the previous loc at the same level, which—for the sake of a simpler explanation—I earlier allowed you to assume.)