Clojure Zipper von verschachtelten Maps TRIE Unterdrückung

Question

Wie kann ich einen Clojure Reißverschluss für einen TRIE schaffen, durch verschachtelte Karten dargestellt, wurden die Schlüssel die Buchstaben.?

Etwas wie folgt aus:

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

Stellt eine Trie mit 2 Worten 'Banane' und 'ana'. (Falls notwendig, ist es möglich, hier einige Änderungen in den Karten vorzunehmen.)

Ich habe versucht, map? vals assoc als die 3 Funktionen zum Reißverschluss jeweils zu übergeben. Aber es scheint nicht zu funktionieren ..

Welche drei Funktionen soll ich verwenden?

Und wie der Einsatz-in-trie wie auf dem Reißverschluss basiert aussehen würde?

Answer 1

map?vals#(zipmap (keys %1) %2) würde tun, aber nicht unterstützt Einfügen/Entfernen von Kindern (da Kinder nur Werte sind, wissen Sie nicht, welchen Schlüssel zu entfernen/hinzufügen).

Die unten angegebene map-zipper unterstützt das Einfügen/Entfernen, da Knoten [k v] -Paare sind (mit Ausnahme der Wurzel, die eine Map ist).

(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

Die solution proposed by @cgrant ist groß, aber beschreibt implizit ein Baum, in dem alle Zweige und Blattknoten einen zugehörigen Wert (der Schlüssel im Wörterbuch), außer für den Wurzelknoten, die ohne Wert nur ein Zweig ist. So , der Baum {"/" nil}, ist nicht ein Baum mit einem einzelnen Blattknoten, sondern ein Baum mit einem anonymen Wurzel Zweig und ein einzelner Blattknoten mit dem Wert /. In der Praxis bedeutet dies, dass bei jeder Traversierung des Baumes zuerst eine (zip/down t) ausgeführt werden muss, um den Wurzelknoten abzusteigen.

Eine alternative Lösung ist das explizite Modellieren des Stamms in der Map, dh das Erstellen von Zipps aus Maps mit einem einzelnen Schlüssel im Stammverzeichnis. Zum Beispiel:

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