Flattening a map of sets

Question

I am trying to flatten a map where the keys are traversables, in the sense that:

Map( Set(1, 2, 3) -> 'A', Set(4, 5, 6) -> 'B')

should flatten to:

Map(5 -> B, 1 -> A, 6 -> B, 2 -> A, 3 -> A, 4 -> B)

Here is what I did:

def fuse[A, B, T <: Traversable[A]](mapOfTravs: Map[T, B]): Map[A, B] = {
  val pairs = for {
    trav <- mapOfTravs.keys
    key <- trav
  } yield (key, mapOfTravs(trav))
  pairs.toMap
}   

It works. But:

1. Is there a simpler way to do this?

2. I'm not very comfortable with the Scala type system and I'm sure this can be improved. I have to specify the types explicitly whenever I use my function:

   val map2 = Map( Set(1, 2, 3) -> 'A', Set(4, 5, 6) -> 'B')
   val fused2 = fuse[Int, Char, Set[Int]](map2)
   
   val map1: Map[Traversable[Int], Char] = Map( Set(1, 2, 3) -> 'A', Set(4, 5, 6) -> 'B')
   val fused1 = fuse[Int, Char, Traversable[Int]](map1)
   

P.S.: this fuse function does not make much sense when the key traversables have a non-null intersection.

Answer 1

This is basically what you're doing in the for comprehension, but simplified a little bit:

  def fuse[A, B, T <: Traversable[A]](mapOfTravs: Map[T, B]): Map[A, B] = {
    mapOfTravs.flatMap({ case (s, c) => s.map(i => i -> c) })
  }

Not much you can do about the types, I'm sure there's some type lambda shenanigans that you can do, I'm just not sure how to do them...

UPDATE Here's a slightly better for version, same as the above flatMap:

  def fuse2[A, B, T <: Traversable[A]](mapOfTravs: Map[T, B]): Map[A, B] = {
    for {
      (keys, value) <- mapOfTravs
      key <- keys
    } yield key -> value
  }

Answer 2

Like @Azzie, I was thinking zip, but maybe Azzie has the advantage with those zees.

scala> val m = Map( Set(1, 2, 3) -> 'A', Set(4, 5, 6) -> 'B')
m: scala.collection.immutable.Map[scala.collection.immutable.Set[Int],Char] = Map(Set(1, 2, 3) -> A, Set(4, 5, 6) -> B)

scala> (m map { case (k, v) => k zip (Stream continually v) }).flatten.toMap
res0: scala.collection.immutable.Map[Int,Char] = Map(5 -> B, 1 -> A, 6 -> B, 2 -> A, 3 -> A, 4 -> B)

scala> (m map { case (k, v) => k zipAll (Nil, null, v) }).flatten.toMap
res1: scala.collection.immutable.Map[Any,Char] = Map(5 -> B, 1 -> A, 6 -> B, 2 -> A, 3 -> A, 4 -> B)

scala> m flatMap { case (k, v) => k zip (Stream continually v) }
res2: scala.collection.immutable.Map[Int,Char] = Map(5 -> B, 1 -> A, 6 -> B, 2 -> A, 3 -> A, 4 -> B)

It's not obvious how to generalize it nicely.

Answer 3

This looks horrible and using 0 is kind of cheating but it does the job

 m.map( {case (s,c) => s.zipAll(Set(c),0,c)} ).flatten.toMap