A bi-directional map in clojure?

Question

What would be the best way to implement a bi-directional map in clojure? (By bi-directional map, I mean an associative map which can provide both A->B and B->A access. So in effect, the values themselves would be keys for going in the opposite direction.)

I suppose I could set up two maps, one in each direction, but is there a more idiomatic way of doing this?

I'm interested both in cases where we want a bijection, implying that no two keys could map to the same value, and cases where that condition isn't imposed.

Crescendo

Answer 1

You could always use a Java library for this, like one of the collections in Apache commons. TreeBidiMap implements java.util.Map so it's even seq-able without any 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")

Some things won't work though, like assoc and dissoc, since they expect persistent collections and TreeBidiMap is mutable.

If you really want to do this in native Clojure, you could use metadata to hold the reverse-direction hash. This is still going to double your memory requirements and double the time for every add and delete, but lookups will be fast enough and at least everything is bundled.

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

You'd probably have to implement a bunch of other functions to get full functionality of course. Not sure how feasible this approach is.

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

Oleograph

Thanks, that's helpful. I would prefer to have a clojure native option, so your second idea is something I might try. – Crescendo

Answer 2

For most cases, I've found the following works fine:

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

This will simply merge the original map with the inverted map into a new map, then you can use regular map operations with the result.

It's quick and dirty, but obviously you should avoid this implementation if any of the keys might be the same as any of the values or if the values in a-map aren't unique.

Foreshow

Answer 3

We can reframe this problem as follows:
Given a list of tuples ([a1 b1] [a2 b2] ...) we want to be able to quickly lookup tuples by both a and b. So we want mappings a -> [a b] and b -> [a b]. Which means that at least tuples [a b] could be shared. And if we think about implementing it then it quickly becomes apparent that this is an in-memory database table with columns A and B that is indexed by both columns.

So you can just use a lightweight in-memory database.

Sorry, I'm not familiar with Java Platform enough to recommend something specific. Of cause Datomic comes to mind, but it could be an overkill for this particular use case. On the other hand it has immutability baked in which seems desirable to you based on your comment to Brian's answer.

Gurgitation