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 ?
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))
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."))))
