Q:

How to compute inverse of a multi-map

I have a Scala Map: 
    x: [b,c]
    y: [b,d,e]
    z: [d,f,g,h]
I want inverse of this map for look-up.
    b: [x,y]
    c: [x]
    d: [x,z] and so on.
Is there a way to do it without using in-between mutable maps
If its not a multi-map - Then following works:
typeMap.flatMap { case (k, v) => v.map(vv => (vv, k))}

A:

EDIT: fixed answer to include what Marth rightfully pointed out. My answer is a bit more lenghty than his as I try to go through each step and not use the magic provided by flatMaps for educational purposes, his is more straightforward :)
I'm unsure about your notation. I assume that what you have is something like:
val myMap = Map[T, Set[T]] (
  x -> Set(b, c),
  y -> Set(b, d, e),
  z -> Set(d, f, g, h)
)

You can achieve the reverse lookup as follows:
val instances = for {
  keyValue <- myMap.toList
  value <- keyValue._2
}
yield (value, keyValue._1)

At this point, your instances variable is a List of the type:
(b, x), (c, x), (b, y) ...

If you now do:
val groupedLookups = instances.groupBy(_._1)

You get:
b -> ((b, x), (b, y)),
c -> ((c, x)),
d -> ((d, y), (d, z)) ...

Now we want to reduce the values so that they only contain the second part of each pair. Therefore we do:
val reverseLookup = groupedLookup.map(_._1 -> _._2.map(_._2))

Which means that for every pair we maintain the original key, but we map the list of arguments to something that only has the second value of the pair.
And there you have your result. 
(You can also avoid assigning to an intermediate result, but I thought it was clearer like this)

