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: