Saturday, 23 February 2013

clojure zippers

I bumped into Clojure's zipper data structure while trying to implement aMinimax algorithm for a game. There are some excellent resources on zippers, Brian's is a good introduction
Why should you use zippers? That's a good question, when you already have tree-seq in clojure/core.
Tree-seq is good for navigating a tree, printing out its nodes. Zipper provide the ability to edit a tree, which tree-seq does not.
A couple of things stumped me when I first encountered zippers. 
One of them is that a zipper declared with vector-zip doesn't have any content in a parent node. In other words, all the number elements of the following vector are leaf nodes.

Loading ....

Brian calls the head of the tree the "tomorrow tree". Actually, all the parent elements (or those that have branches), are vectors (or the tomorrow tree) and do not contain any "content".  And here's how you could visualize the tree

Tree editing

Since clojure is functional, each tree edit returns a new (copy of) tree. So the basic idea is, do some edits and call zip/root to get the root of the tree. Note that zip/root calls zip/node on the tree, so you need to create a zipper again if you want to traverse the edited tree.
Loading ....

No comments: