Zippers with records in Clojure

Today at clojure-conj there were some questions about using zippers with records and since I’ve been sitting on a blog idea about this I thought now was a great time…. I’ll refer you first to Brian Marick’s excellent tutorial on zippers as background context so I can skip that part.

Now let’s imagine we have a tree where each node in the tree is a Clojure record where various fields of the record may contain child records. The zipper library has built-in implementations for trees made of seqs, vectors, and XML. We want to create a zipper that understands how to work on our records data structure instead.

To do this, we need to use the zipper function which takes three functions and the root of your own data structure (our record tree). The three functions are:

branch? – a function that takes a tree node and returns true if it is *possible* for that node to have children (even if it might not)
children – given a branch tree node, return a seq of its children
make-node – given a node and a seq of children, make a new node

Because protocols are fun, I’ll wrap these functions up in a protocol:

(defprotocol TreeNode
  (branch? [node] "Is it possible for node to have children?")
  (node-children [node] "Return children of this node.")
  (make-node [node children] "Makes new node from existing node and new children."))

and it’s useful to provide a default implementation of the protocol via Object:

(extend-type Object TreeNode
             (branch? [node] false)
             (make-node [node children] node))

It’s then trivial to use the zipper function to create an extensible zipper based on a protocol:

(defn tree-zip
  "Make a zipper out of a tree."
  [root]
  (z/zipper branch? node-children make-node root))

Note that none of this is record-specific yet – this is really a generic zipper based on a node protocol. I haven’t thought through all the ramifications yet but maybe that would be a good generic refactoring for clojure.zipper.

So let’s make some records of our own and implement the protocol:

(defrecord ScalarFunction [f exprs])

(defrecord Comparison [op left right])

(extend-protocol TreeNode
  ScalarFunction
  (branch? [node] true)
  (node-children [node]
                 (seq (:exprs node)))
  (make-node [node children]
             (ScalarFunction. (:f node) children))

  Comparison
  (branch? [node] true)
  (node-children [node]
                 (seq (remove nil? [(:left node) (:right node)])))
  (make-node [node children]
             (Comparison. (:op node) (first children) (second children))))

Here I’m defining some mathematical like AST node constructs: ScalarFunction is an arithmetic function with args and Comparison is a logical comparison like “x = y”. You could pack these into the same record but they’re different here to demonstrate things later on. I use extend-protocol to implement the TreeNode protocol for the types ScalarFunction and Comparison.

These demonstrate two common use cases for records as tree nodes: 1) a record has fields, several of which contain records (ie left and right fields) and 2) a record has a single field that contains a seq of records. It seems to me that the only hard thing standing in the way of a generic zipper record implementation is deciding how to handle these cases. Anyhow…back to our example.

We can now create a zipper based on our tree of records:

(def f1 (ScalarFunction. :+ [2 3]))
(def f2 (ScalarFunction. :- [6 1]))
(def c1 (Comparison. := f1 f2))

(def tree-z (tree-zip c1))

Here I’ve created a tree representing “(2 + 3) = (6 – 1)” and then wrapped a zipper around it. We can then use standard zipper functions to “move around” the tree:

(println "down-down-right = " (-> tree-z z/down z/down z/right z/node))

which will walk down into the the comparison, down into the left function, then right to the second argument and return “3”. Cool!

Pure Danger Tech

Zippers with records in Clojure