Clojure Zipper of nested Maps repressing a TRIE

Question

How can I create a Clojure zipper for a TRIE, represented by nested maps, were the keys are the letters.?

Something like this:

{\b {\a {\n {\a {\n {\a {'$ '$}}}}}} \a {\n {\a {'$ '$}}}}

Represents a trie with 2 words 'banana' and 'ana'. (If necessary , its possible to make some changes here in maps..)

I've tried to pass map? vals assoc as the 3 functions to the zipper,respectively. But it doesnt seem to work..

What 3 functions should I use?

And how the insert-into-trie would look like based on the zipper ?

Remanent

Answer 1

map? vals #(zipmap (keys %1) %2) would do but doesn't support insertion/removal of children (since children are only values, you don't know which key to remove/add).

The map-zipper below does support insertion/removal because nodes are [k v] pairs (except the root which is a map).

(defn map-zipper [m]
  (z/zipper 
    (fn [x] (or (map? x) (map? (nth x 1))))
    (fn [x] (seq (if (map? x) x (nth x 1))))
    (fn [x children] 
      (if (map? x) 
        (into {} children) 
        (assoc x 1 (into {} children))))
    m))

Felting

I have added this to ClojureDocs and provided a link to this answer. I hope it's OK. clojuredocs.org/clojure.zip/… – Tunnel

This is a nice solution but as the size increases and a map changes from PersistentArrayMap to PersistentHashMap the order is no longer preserved. Thus navigating to the a new node after "append-child" with "z/down z/rightmost" will now be guaranteed to work. – Lulululuabourg

Answer 2

The solution proposed by @cgrant is great, but implicitly describes a tree where all branches and leaf nodes have an associated value (the key in the dictionary) except for the root node that is just a branch without a value. So, the tree {"/" nil}, is not a tree with a single leaf node, but a tree with an anonymous root branch and a single leaf node with value /. In practice, this means that every traversal of the tree has to first execute a (zip/down t) in order to descend the root node.

An alternative solution is to explicitly model the root inside the map, that is, only create zippers from maps with a single key at the root. For example: {"/" {"etc/" {"hosts" nil}}}

The zipper can then be implemented with:

(defn map-zipper [map-or-pair]
  "Define a zipper data-structure to navigate trees represented as nested dictionaries."
  (if (or (and (map? map-or-pair) (= 1 (count map-or-pair))) (and (= 2 (count map-or-pair))))
    (let [pair (if (map? map-or-pair) (first (seq map-or-pair)) map-or-pair)]
      (zip/zipper
        (fn [x] (map? (nth x 1)))
        (fn [x] (seq (nth x 1)))
        (fn [x children] (assoc x 1 (into {} children)))
        pair))
    (throw (Exception. "Input must be a map with a single root node or a pair."))))

Shockheaded