Many-value map in Scala

Question

In Scala 2.8, I have an immutable map with multiple values for each key:

Map[T,Iterable[U]]

Is there a superior representation? Secondly, how would you generate such a map from

Iterable[(T,U)]

? I am presently using:

def toGroupedMap[T,U](vals: Iterable[(T,U)]): Map[T,Iterable[U]] =
  vals.groupBy(_._1).map({ case (s,it) => (s,it.map(_._2)) }).toMap

Which works, but feels clunky.

EDIT: I should specify that I am working with immutable data. Is there an immutable equivalent to MultiMap?

Answer 1

Look into the MultiMap mix-in for Map.

Answer 2

A multimap is what you need. Here's an example of creating one and then adding entries to it from a List[(String, Int)]. I'm sure there's a prettier way.

scala> val a = new collection.mutable.HashMap[String, collection.mutable.Set[Int]]() with collection.mutable.MultiMap[String, Int]
a: scala.collection.mutable.HashMap[String,scala.collection.mutable.Set[Int]] with scala.collection.mutable.MultiMap[String,Int] = Map()

scala> List(("a", 1), ("a", 2), ("b", 3)).map(e => a.addBinding(e._1, e._2))                                                      
res0: List[scala.collection.mutable.HashMap[String,scala.collection.mutable.Set[Int]] with scala.collection.mutable.MultiMap[String,Int]] = List(Map(a -> Set(1, 2), b -> Set(3)), Map(a -> Set(1, 2), b -> Set(3)), Map(a -> Set(1, 2), b -> Set(3)))

scala> a("a")
res2: scala.collection.mutable.Set[Int] = Set(1, 2)

Answer 3

If you don't really need immutability, then as others have said, MultiMap is the way to go. If you do really need immutability, then the approach you've taken is as easy as anything else; there isn't anything built in (AFAIK), and any creation of a immutable MultiMap is going to take a lot more work than the method you've got there.

Whether the representation is superior depends on your usage. Do you often want to do things with all values corresponding to one key? Can you insert the same value multiple times into your map? If yes to both, your representation is the right one.

If you want the same value inserted at most once at one key, then you should use Set[U] instead of Iterable[U] (which can easily be done by adding .toSet to it.map(_._2)).

If you dislike having to deal with sets/iterables and are just putting up with it (i.e. you'd really rather just have key-value pairs than key-setofvalues pairs), you'd have to write a wrapper class around the map that presents a single map interface and would do the right thing with +, -, and iterator.

Here's an example that turned out a little longer than I had anticipated (here formatted for cut and paste into the REPL):

import scala.collection._
class MapSet[A,B](
  val sets: Map[A,Set[B]] = Map[A,Set[B]]()
) extends Map[A,B] with MapLike[A,B,MapSet[A,B]] {
  def get(key: A) = sets.getOrElse(key,Set[B]()).headOption
  def iterator = new Iterator[(A,B)] {
    private val seti = sets.iterator
    private var thiskey:Option[A] = None
    private var singles:Iterator[B] = Nil.iterator
    private def readyNext {
      while (seti.hasNext && !singles.hasNext) {
        val kv = seti.next
        thiskey = Some(kv._1)
        singles = kv._2.iterator
      }
    }
    def hasNext = {
      if (singles.hasNext) true
      else {
        readyNext
        singles.hasNext
      }
    }
    def next = {
      if (singles.hasNext) (thiskey.get , singles.next)
      else {
        readyNext
        (thiskey.get , singles.next)
      }
    }
  }
  def +[B1 >: B](kv: (A,B1)):MapSet[A,B] = {
    val value:B = kv._2.asInstanceOf[B]
    new MapSet( sets + ((kv._1 , sets.getOrElse(kv._1,Set[B]()) + value)) )
  }
  def -(key: A):MapSet[A,B] = new MapSet( sets - key )
  def -(kv: (A,B)):MapSet[A,B] = {
    val got = sets.get(kv._1)
    if (got.isEmpty || !got.get.contains(kv._2)) this
    else new MapSet( sets + ((kv._1 , got.get - kv._2)) )
  }
  override def empty = new MapSet( Map[A,Set[B]]() )
}

and we can see that this works as desired like so:

scala> new MapSet() ++ List(1->"Hi",2->"there",1->"Hello",3->"Bye")
res0: scala.collection.Map[Int,java.lang.String] = Map(1 -> Hi, 1 -> Hello, 2 -> there, 3 -> Bye)

scala> res0 + (2->"ya")
res1: scala.collection.Map[Int,java.lang.String] = Map(1 -> Hi, 1 -> Hello, 2 -> there, 2 -> ya, 3 -> Bye)

scala> res1 - 1
res2: scala.collection.Map[Int,java.lang.String] = Map(2 -> there, 2 -> ya, 3 -> Bye)

(though if you wanted to get a MapSet back after ++, you'd need to override ++; the Map hierarchy doesn't have its own builders to take care of things like this).