Une carte bidirectionnelle à clojure?

Question

Quelle serait la meilleure façon de mettre en œuvre une carte bidirectionnelle dans clojure? (Par carte bidirectionnelle, j'entends une carte associative qui peut fournir à la fois l'accès A-> B et B-> A. Donc en effet, les valeurs elles-mêmes seraient des clés pour aller dans la direction opposée.)

I Supposons que je puisse créer deux cartes, une dans chaque direction, mais y a-t-il une façon plus idiomatique de le faire?

Je suis intéressé à la fois dans les cas où nous voulons une bijection, ce qui implique que pas deux clés pourraient correspondre à la même valeur, et les cas où cette condition n'est pas imposée.

Answer 1

Vous pouvez toujours utiliser une bibliothèque Java pour cela, comme l'une des collections de Apache commons. TreeBidiMap implémente java.util.Map donc c'est même seq-capable sans aucun effort.

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

Certaines choses ne fonctionnent pas bien, comme assoc et dissoc, car ils attendent de collections persistantes et TreeBidiMap est mutable.

Si vous voulez vraiment le faire en Clojure natif, vous pouvez utiliser des métadonnées pour contenir le hachage en sens inverse. Cela va encore doubler vos besoins en mémoire et doubler le temps pour chaque ajout et suppression, mais les recherches seront assez rapides et au moins tout est regroupé.

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

Vous devrez probablement mettre en œuvre un tas d'autres fonctions pour obtenir toutes les fonctionnalités bien sûr. Je ne suis pas certain de la faisabilité de cette approche.

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

Answer 2

Pour la plupart des cas, j'ai trouvé les œuvres suivantes bien:

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

Ce sera tout simplement fusionner la carte originale avec la carte inversée dans une nouvelle carte, vous pouvez utiliser les opérations de carte régulières Avec le résultat.

C'est rapide et sale, mais vous devez évidemment éviter cette implémentation si l'une des clés est identique à l'une des valeurs ou si les valeurs de a-map ne sont pas uniques.

Answer 3

Nous pouvons reformuler ce problème comme suit:
Étant donné une liste de tuples ([a1 b1] [a2 b2] ...) nous voulons être en mesure de rechercher rapidement tuples par les deux a et b. Nous voulons donc des cartographies a -> [a b] et b -> [a b]. Ce qui signifie que au moins tuples pourraient être partagés. Et si nous envisageons de l'implémenter, il devient rapidement apparent qu'il s'agit d'une table de base de données en mémoire avec les colonnes A et B qui sont indexées par les deux colonnes.

Vous pouvez donc simplement utiliser une base de données en mémoire légère. Désolé, je ne suis pas familier avec la plate-forme Java assez pour recommander quelque chose de spécifique. De la cause Datomic vient à l'esprit, mais cela pourrait être une exagération pour ce cas d'utilisation particulier. D'un autre côté, il a immuabilité cuit dans lequel vous semble souhaitable en fonction de votre commentaire à la réponse de Brian.