Monday, 19 January 2009

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.