In the previous post, I went over how to use zippers along with a tree of records.

Next, I want to pull up a level of abstraction and think about things you might want to do over a tree. We’re working on code these days that does lots of work on trees of heterogeneous records. In particular, much of the work involves building a tree, then (symbolically) manipulating that tree.

It’s useful to thus wrap up the ability to a) match a pattern in the tree and b) mutate the tree when you find a match. Below is a function that takes a zipper and two functions to match and mutate:

(defn tree-edit "Take a zipper, a function that matches a pattern in the tree, and a function that edits the current location in the tree. Examine the tree nodes in depth-first order, determine whether the matcher matches, and if so apply the editor. On first match, return modified tree." [zipper matcher editor] (loop [loc zipper] (if (z/end? loc) (z/root loc) (if-let [matcher-result (matcher loc)] (let [new-loc (z/edit loc (partial editor matcher-result))] (if (not (= (z/node new-loc) (z/node loc))) (z/root new-loc) (recur (z/next loc)))) (recur (z/next loc))))))

Here “loc” is a zipper location wrapping a point in the tree. The loop/recur walks through the tree using z/next until z/end? is true, then returns z/root. If the matcher matches, the result of the matcher and the current node are given to the editor function used in z/edit. If the returned mutated node is different, then we bail out early.

With this function, we can then write a pair of match and edit functions and apply them:

;; define a rule as a matcher/editor pair (defn is-scalar? [loc] (instance? ScalarFunction (z/node loc))) ;; define a tree editor - gets the result of the matcher and the node (defn eval-scalar [_ {:keys (f exprs)}] (case f :+ (apply + exprs) :- (apply - exprs) (str "oh noes! -> " f)))

We can then apply this match/edit rule using tree-edit:

(def tree-2 (tree-edit tree-z is-scalar? eval-scalar)) (def tree-3 (tree-edit (tree-zip tree-2) is-scalar? eval-scalar))

Our starting tree was tree-z:

which we then applied the rule to get tree-2:

and then applied it again to get tree-3:

It should be pretty obvious that I can write additional rules and build more infrastructure to apply these rules to mutate the tree.

If you found this interesting, I’m also doing a lightning talk today at the Clojure Conj conference and here are the slides:

**Tree Editing with Zippers**