Clojure Zippers for Maps

There is a wonderful library in Clojure for traversing and manipulating hierarchical data structures using zippers.  The internet even has several good references on how understand the mind-warping nature of zippers and use them effectively.

My goal was to navigate a nested structure of maps, like this:

{:a0 {:b0 {:c0 1 :c1 {}} :b1 {:d0 2}} :a1 {:z {}}}

After a couple of iterations I settled on this for my zipper:

(defn map-zip
  [m]
  (let [root (clojure.lang.MapEntry. ::root m)]
    (z/zipper (comp map? val)
              (comp seq val)
              (fn [[k children] children'] (clojure.lang.MapEntry. k (into (empty children) children')))
              root)))

This zipper works perfectly for iteratively traversing and editing my data structure. For example, one task was to prune the empty sub-maps (like the entry at (get-in m [:a1 :z]). Here's a function that performs that task:

(defn prune
  "Recursively prune the empty submap leaves from the nested map structure `m`"
  [m]
  (let [z (map-zip m)]
    (val (loop [z z]
           (if (z/end? z)
             (z/root z)
             (recur (if (and (z/branch? z) (not (seq (z/children z))))
                      (z/remove z)
                      (z/next z))))))))

But despite the effectiveness, in several cases I found the implementation counter-intuitive -specifically when navigating.   The fundamental problem is that navigating using relative motion (left, right, leftmost, rightmost) work well for sequences (a common use case for zippers) but is inefficient when I already have an index associating keys to children for my maps.

I decided to create a new library inspired by the Clojure zipper implementation but leveraging the efficient and idiomatic navigation by sequences of keys (à la get-in , update-in, assoc-in).    Projected completion date: not now.