Functional Tree Editing

The zipper is a Functional Pearl which allows localized editing of a list-based data structure (most commonly trees).

The idea is very simple, for any list-based data structure you can create a data-structure (the zipper) which allows you to navigate (next, previous, up, down) but also do functional-editing (by which I mean localized editing without having to reconstruct the entire data structure). The original data is untouched.

In the example below (see [1] for docs), we create a zip structure from a vector zip/vector-zip. Navigating along we move along with zip/next, zip/remove and return to the root with zip/root

  user> (let [zip (clojure.zip/vector-zip [1 2 3 4 5])]
          (clojure.zip/root (clojure.zip/remove (clojure.zip/next zip))))
  [2 3 4 5]

This example looks a bit backward; we can make things clearer with ->. This is a macro that "threads" function calls, we can explain this a bit clearer with macroexpand as this shows what a macro actually becomes.

  user> (macroexpand '(-> [1 2 3] rest rest))
  (rest (clojure.core/-> [1 2 3] rest))

  user> (macroexpand '(-> [1 2 3] rest))
  (rest [1 2 3])

  ;; Put the two together and we get (rest (rest [1 2 3])) ==> 3

If we apply this code to the previous zip example, we get something much clearer (apart from the namespace gumph).

  user> (let [zip (clojure.zip/vector-zip [1 2 3 4 5])]
          (-> zip clojure.zip/next clojure.zip/remove clojure.zip/root))

The main point of zippers is that the original is untouched.

  user> (let [data [1 2 3 4 5] zip (clojure.zip/vector-zip data)]
          (prn "Changed is " (-> zip clojure.zip/next clojure.zip/remove clojure.zip/root))
          (prn "Original is " data))

  "Changed is " [2 3 4 5]
  "Original is " [1 2 3 4 5]

Clojure provides zippers for vectors, sequences and XML elements.