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 ?

Frank Shearar · Accepted Answer · 2013-02-26 13:51:08Z

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))

I have added this to ClojureDocs and provided a link to this answer. I hope it's OK. clojuredocs.org/clojure.zip/…
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.

mrucci · Accepted Answer · 2018-03-03 20:09:37Z

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

Collectives™ on Stack Overflow

Clojure Zipper of nested Maps repressing a TRIE

2 Answers 2

2 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Linked

Related