Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Turn a hash map inside out in Clojure

Tags:

clojure

I am very new to Clojure and have an interesting problem for you Clojure gurus. I'm working through the book "Programming Collective Intelligence" and trying to code the examples in Clojure (the book has them all in Python). In the first chapter we have a hash map setup of movie critics and the rankings they've given to different movies. It looks like this:

{"Lisa Rose" {"Lady in the Water" 2.5, "Snakes on a Plane" 3.5 },
 "Gene Seymour" {"Lady in the Water" 3.0, "Snakes on a Plane" 3.5}}

The problem is this. How to turn that inside out so that I get a hash map that looks like this:

{"Lady in the Water" {"Lisa Rose" 2.5, "Gene Seymour" 3.0},
 "Snakes on a Plane" {"Lisa Rose" 3.5, "Gene Seymour" 3.5}}

What would be your function to accomplish this?

like image 236
Dave Kincaid Avatar asked Sep 02 '11 21:09

Dave Kincaid


3 Answers

(let [m {"Lisa Rose" {"Lady in the Water" 2.5, "Snakes on a Plane" 3.5 },
         "Gene Seymour" {"Lady in the Water" 3.0, "Snakes on a Plane" 3.5}}]
  (apply merge-with merge
         (for [[ok ov] m
               [ik iv] ov]
           {ik {ok iv}})))

{"Snakes on a Plane" {"Gene Seymour" 3.5, "Lisa Rose" 3.5},
 "Lady in the Water" {"Gene Seymour" 3.0, "Lisa Rose" 2.5}}
like image 116
amalloy Avatar answered Nov 15 '22 00:11

amalloy


(defn inverse-map [m]
  (let [inner-keys (-> m first val keys)
        outer-keys (keys m)]
    (apply merge-with merge
           (for [ik inner-keys
                 ok outer-keys]
             {ik {ok (get-in input [ok ik])}}))))

This assumes that all keys of interest in the inner maps are present on the first inner map. If this is incorrect, (-> m first val keys) would have to be replaced with something returning a collection of all keys of interest, e.g. (->> m (map values) (mapcat keys)).

The idea is to build a map of the form {inner-key {outer-key the-value-at-inner-key-in-the-map-at-outer-key}}, then merge them together appropriately.

Return value on the map in the question text is as specified.

Now, the above creates a lot of intermediate structures, which may be a problem performance-wise. If speed is of the essence, you can switch to loop and transients:

(defn transient-inverse-map [m]
  (let [inner-keys (-> m first val keys)
        outer-keys (keys m)
        t (transient {})]
    (loop [inner-keys inner-keys
           t t]
      (if (seq inner-keys)
        (recur (next inner-keys)
               (assoc! t ik
                       (let [ik (first inner-keys)
                             t  (transient {})]
                         (loop [outer-keys outer-keys
                                t t]
                           (if (seq outer-keys)
                             (let [ok (first outer-keys)]
                               (recur (next outer-keys)
                                      (assoc! t ok (get-in m [ok ik]))))
                             (persistent! t))))))
        (persistent! t)))))

The idea is the same, if harder to discern from the code.

like image 32
Michał Marczyk Avatar answered Nov 15 '22 00:11

Michał Marczyk


I can propose following: We have map - collection of entries. Turn every entry inside out and them merge them: Initial:

{:Lisa {:Lady 2.5, :Snakes 3.5},
 :Gene {:Lady 3.0, :Snakes 3.5}}

Inverse every entry:

([:Lady {:Lisa 2.5}], [:Snakes {:Lisa 3.5}])
([:Lady {:Gene 3.0}], [:Snakes {:Gene 3.5}])

Concat them:

([:Lady {:Lisa 2.5}], [:Snakes {:Lisa 3.5}], [:Lady {:Gene 3.0}], [:Snakes {:Gene 3.5}])

And them merge them to one map:

{:Lady {:Lisa 2.5, :Gene 3.0},
 :Snakes {:Lisa 3.5, :Gene 3.5}}

Code:

(defn inverse-map [m]
        (let [inverse-entry (fn [[name movies]]
                                (map (fn [[movie rating]]
                                         [movie {name rating}])
                                     movies))]
           (->> (map inverse-entry m)
                (reduce concat)
                (reduce (fn [res [movie entry]]
                            (update-in res [movie] merge entry))
                        {}))))

So we get map, (it is collection of vectors [key value]), inverse every entry (vector [key value]). Now we have collection of collections of vectors, concat them to one collection. And finally, using reduce we add every vector to map.

I suppose there is more elegant solution, but mine also works.

like image 3
Mikita Belahlazau Avatar answered Nov 15 '22 01:11

Mikita Belahlazau