Eine bidirektionale Karte in clojure?

Question

Was wäre der beste Weg, um eine bidirektionale Karte in Clojure zu implementieren? (Mit bidirektionaler Karte meine ich eine assoziative Karte, die sowohl A-> B- als auch B-> A-Zugang bieten kann. In der Tat wären die Werte selbst Schlüssel für die umgekehrte Richtung.)

I Angenommen, ich könnte zwei Karten erstellen, eine in jede Richtung, aber gibt es eine idiomatische Art, dies zu tun?

Ich bin sowohl in Fällen interessiert, wo wir eine Bijektion wollen, was bedeutet, dass keine zwei Tasten auf den gleichen Wert abbilden konnte, und Fälle, in denen diese Bedingung nicht auferlegt wird.

Answer 1

Man konnte immer eine Java-Bibliothek für diese, wie eine der Sammlungen in Apache commons. TreeBidiMap implementiert java.util.Map, so dass es sogar ohne weiteres möglich ist.

user> (def x (org.apache.commons.collections.bidimap.TreeBidiMap.)) 
#'user/x 
user> (.put x :foo :bar) 
nil 
user> (keys x) 
(:foo) 
user> (.getKey x :bar) 
:foo 
user> (:foo x) 
:bar 
user> (map (fn [[k v]] (str k ", " v)) x) 
(":foo, :bar") 

Manches wird aber nicht funktionieren, wie assoc und dissoc, da sie persistent Sammlungen erwarten und TreeBidiMap ist wandelbar.

Wenn Sie wirklich diese in nativer Clojure tun wollen, können Sie Metadaten verwenden, um die Reverse-Richtung Hash zu halten. Dadurch werden Ihre Speicheranforderungen verdoppelt und die Zeit für jedes Hinzufügen und Löschen verdoppelt. Suchvorgänge werden jedoch schnell genug ausgeführt, und mindestens alles ist gebündelt.

(defn make-bidi [] 
    (with-meta {} {})) 

(defn assoc-bidi [h k v] 
    (vary-meta (assoc h k v) 
      assoc v k)) 

(defn dissoc-bidi [h k] 
    (let [v (h k)] 
    (vary-meta (dissoc h k) 
       dissoc v))) 

(defn getkey [h v] 
    ((meta h) v)) 

Sie müssten wahrscheinlich eine Reihe anderer Funktionen implementieren, um die volle Funktionalität zu erhalten. Nicht sicher, wie machbar dieser Ansatz ist.

user> (def x (assoc-bidi (make-bidi) :foo :bar)) 
#'user/x 
user> (:foo x) 
:bar 
user> (getkey x :bar) 
:foo 

Answer 2

In den meisten Fällen habe ich die folgenden Werke gefunden fein:

(defn- bimap 
    [a-map] 
    (merge a-map (clojure.set/map-invert a-map))) 

Dies wird einfach die Original-Karte mit der invertierten Karte in eine neue Karte fusioniert, dann können Sie reguläre Karte Operationen verwenden mit dem Ergebnis.

Es ist schnell und schmutzig, aber Sie sollten diese Implementierung natürlich vermeiden, wenn einer der Schlüssel mit einem der Werte übereinstimmt oder wenn die Werte in a-map nicht eindeutig sind.

Answer 3

Wir können dieses Problem reframe wie folgt:
Bei einer Liste von Tupeln ([a1 b1] [a2 b2] ...) wir schnell in der Lage sein wollen, sowohl a und b Tupel nachzuschlagen. Wir wollen also die Zuordnungen a -> [a b] und b -> [a b]. Was bedeutet, dass mindestens Tupeln geteilt werden könnten. Und wenn wir darüber nachdenken, es zu implementieren, wird schnell klar, dass dies eine In-Memory-Datenbanktabelle mit den Spalten A und B ist, die von beiden Spalten indiziert wird.

So können Sie nur eine leichte In-Memory-Datenbank verwenden.

Sorry, bin ich mit Java-Plattform nicht vertraut genug, um etwas spezifisch zu empfehlen. Natürlich kommt Datomic in den Sinn, aber es könnte ein Overkill für diesen speziellen Anwendungsfall sein. Auf der anderen Seite hat es Unveränderlichkeit gebacken, die Ihnen auf der Grundlage Ihrer Meinung zu Brians Antwort wünschenswert erscheint.