Clojure Застежка-молния вложенных карт, подавляющая TRIE

Question

Как создать застежку-молнию Clojure для TRIE, представленную вложенными картами, были ли эти буквы?

Что-то вроде этого:

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

Представляет с 2 синтаксического дерева слов 'банан' и 'ана'. (При необходимости его можно внести некоторые изменения в карты ..)

Я попытался передать map? vals assoc в качестве 3 функций на молнию соответственно. Но он, похоже, не работает.

Какие 3 функции использовать?

И как будет выглядеть вставка-в-три на основе молнии?

Answer 1

map? будет делать, но не поддерживает установку/удаление детей (так как дети являются только значениями, вы не знаете, какой ключ удалить или добавить).

map-zipper ниже поддерживает вставку/удаление, поскольку узлы являются [k v] парами (кроме корня, который является картой).

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

Answer 2

solution proposed by @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."))))