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