¿Un mapa bidireccional en clojure?

Question

¿Cuál sería la mejor manera de implementar un mapa bidireccional en clojure? (Por mapa bidireccional, me refiero a un mapa asociativo que puede proporcionar tanto acceso A-> B y B-> A. De hecho, los valores mismos serían claves para ir en la dirección opuesta).

I Supongamos que puedo configurar dos mapas, uno en cada dirección, pero ¿hay una forma más idiomática de hacer esto?

Estoy interesado tanto en los casos en que queremos una biyección, lo que implica que no hay dos claves pueden mapear al mismo valor, y los casos en que esa condición no se impone.

Answer 1

Siempre puede utilizar una biblioteca de Java para esto, como una de las colecciones en Apache commons. TreeBidiMap implementa java.util.Map, por lo que incluso puede seq-able sin ningún esfuerzo.

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

Algunas cosas no funcionarán sin embargo, al igual que assoc y dissoc, ya que esperan colecciones persistentes y TreeBidiMap es mutable.

Si realmente quieres hacer esto en Clojure nativo, podrías usar metadatos para mantener el hash de dirección inversa. Esto todavía duplicará los requisitos de memoria y duplicará el tiempo para cada agregar y eliminar, pero las búsquedas serán lo suficientemente rápidas y al menos todo estará incluido.

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

Probablemente tenga que implementar muchas otras funciones para obtener una funcionalidad completa, por supuesto. No estoy seguro de cuán factible es este enfoque.

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

Answer 2

Para la mayoría de los casos, he encontrado los siguientes trabajos bien:

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

esto simplemente fusionar el mapa original con el mapa invertido en un nuevo mapa, a continuación, puede utilizar las operaciones regulares mapa con el resultado.

Es rápido y sucio, pero obviamente debe evitar esta implementación si alguna de las claves puede ser la misma que cualquiera de los valores o si los valores en a-map no son únicos.

Answer 3

Podemos replantear este problema de la siguiente manera:
Dada una lista de tuplas ([a1 b1] [a2 b2] ...) queremos ser capaces de buscar rápidamente tuplas por tanto a y b. Entonces queremos mapeos a -> [a b] y b -> [a b]. Lo que significa que al menos tuplas podrían ser compartidas. Y si pensamos en implementarlo, rápidamente se vuelve evidente que se trata de una tabla de base de datos en memoria con las columnas A y B indexadas por ambas columnas.

Así que puede utilizar una base de datos liviana en memoria.

Lo siento, no estoy lo suficientemente familiarizado con Java Platform como para recomendar algo específico. De la causa Datomic viene a la mente, pero podría ser una exageración para este caso de uso en particular. Por otro lado, tiene inmutabilidad horneada, lo que parece deseable para usted en base a su comentario a la respuesta de Brian.