# Pure Danger Tech home

# Pattern matching and tree mutation

23 Oct 2010

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: