Двунаправленная карта в clojure?

Каким будет лучший способ реализации двунаправленной карты в clojure? (В двунаправленном отображении я имею в виду ассоциативную карту, которая может обеспечить как доступ A- > B, так и B- > A. Таким образом, сами значения будут ключами для перехода в противоположном направлении.)

Я полагаю, что я мог бы создать две карты по одному в каждом направлении, но есть ли более идиоматический способ сделать это?

Мне интересно как в случаях, когда мы хотим биекцию, подразумевая, что никакие два ключа не могут сопоставляться с одним и тем же значением, а также случаи, когда это условие не наложено.

Ответы

Ответ 1

Вы всегда можете использовать библиотеку Java для этого, например, одну из коллекций в Apache commons. TreeBidiMap реализует java.util.Map, поэтому он даже может быть без усилий.

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

Некоторые вещи не будут работать, например, assoc и dissoc, поскольку они ожидают, что постоянные коллекции и TreeBidiMap изменятся.

Если вы действительно хотите сделать это в native Clojure, вы можете использовать метаданные для хранения хэша в обратном направлении. Это все равно удвоит ваши требования к памяти и удвоит время для каждого добавления и удаления, но поиск будет достаточно быстрым и, по крайней мере, все в комплекте.

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

Вам, вероятно, придется реализовать кучу других функций, чтобы, конечно, получить полную функциональность. Не уверен, насколько это возможно.

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

Ответ 2

В большинстве случаев я нашел следующие работы прекрасными:

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

Это просто слияние исходной карты с перевернутым отображением на новую карту, тогда вы можете использовать регулярные операции с результатом.

Это быстро и грязно, но, очевидно, вам следует избегать этой реализации, если любой из ключей может быть таким же, как любое из значений, или если значения в a-map не уникальны.

Ответ 3

Мы можем пересмотреть эту проблему следующим образом:
Учитывая список кортежей ([a1 b1] [a2 b2] ...), мы хотим иметь возможность быстрого поиска кортежей как с помощью a, так и b. Поэтому мы хотим отображать a -> [a b] и b -> [a b]. Это означает, что по крайней мере кортежи [a b] могут быть разделены. И если мы подумаем о его реализации, то быстро становится очевидным, что это таблица базы данных в памяти с столбцами A и B, которые индексируются обоими столбцами.

Итак, вы можете просто использовать легкую базу данных в памяти.

Извините, я не знаком с платформой Java, чтобы рекомендовать что-то конкретное. Причина Datomic приходит в голову, но это может быть излишним для этого конкретного случая использования. С другой стороны, он имеет неизменность, испеченную, которая кажется желательной для вас на основе вашего комментария к ответу Брайана.