Clojure中嵌套映射的Zipper压缩TRIE

Question

我可以帮助您翻译这段内容。需要创建一个Clojure Zipper，用于表示由嵌套的映射组成的TRIE，其中键是字母。类似于以下内容：

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

表示一个包含2个单词'banana'和'ana'的trie树。（如果需要，在maps中可以进行一些更改...）

我尝试将map? vals assoc作为3个函数分别传递给zipper。但似乎不起作用...

我应该使用哪3个函数？

基于zipper，插入到trie树中的样子是怎样的？

- 0xMG

Answer 1

map? vals #(zipmap (keys %1) %2) 可以实现，但不支持插入/删除子元素（因为子元素仅是值，你不知道要删除/添加哪个键）。

下面的 map-zipper 支持插入/删除，因为节点是 [k v] 对（除了根节点是一个 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))

- cgrand

---

我已经将这个内容添加到ClojureDocs，并提供了指向这个答案的链接。希望没问题。http://clojuredocs.org/clojure.zip/zipper#example_54d91161e4b081e022073c72 - muhuk

这是一个不错的解决方案，但随着尺寸的增加和映射从PersistentArrayMap变为PersistentHashMap，顺序将不再保留。因此，在“append-child”后导航到新节点，使用“z/down z/rightmost”将无法保证有效。 - Phil Cooper

Answer 2

@cgrant提出的解决方案非常好，但隐含地描述了一棵树，其中所有的分支和叶节点都有一个关联值（字典中的键），除了根节点只是一个没有值的分支。

因此，树{"/" nil}不是一棵只有一个叶节点的树，而是一棵带有匿名根分支和单个叶节点值为/的树。实际上，这意味着每次遍历树时都必须先执行(zip/down t)以便下降到根节点。

另一种解决方案是在映射内明确建模根节点，即仅从具有根节点单个键的映射创建拉链。例如：{"/" {"etc/" {"hosts" nil}}} 然后可以使用以下方式实现拉链：

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

- mrucci