MultiMap.scala

import collection.{SeqLike, SetLike}
import collection.generic.CanBuildFrom
import collection.mutable

implicit class MultiSeqMapOps[A, B, CC[+ ~] <: SeqLike[~, CC[~]]](val self: Map[A, CC[B]]) extends AnyVal {
  def add[B1 >: B](key: A, value: B1)(implicit cbf: CanBuildFrom[CC[B], B1, CC[B1]]): Map[A, CC[B1]] = {
    val u = self.get(key).fold {
      val _b = cbf()
      _b += value
      _b.result
    } { _ :+ value }
    self.updated(key, u)
  }
}

implicit class MultiSetMapOps[A, B, CC[~] <: SetLike[~, CC[~]] with Set[~]](val self: Map[A, CC[B]])
  extends AnyVal {
  
  def add(key: A, value: B)(implicit cbf: CanBuildFrom[Nothing, B, CC[B]]): Map[A, CC[B]] = {
    val u = self.get(key).fold {
      val _b = cbf()
      _b += value
      _b.result
    } { _ + value }
    self.updated(key, u)
  }
}

val m1 = Map.empty[Int, Seq[String]]
val m2 = m1.add(0, "foo")
val m3 = m2.add(1, "bar")
val m4 = m3.add(0, "baz")

val m5 = Map.empty[Int, Set[String]]
val m6 = m5.add(0, "foo")
val m7 = m6.add(1, "bar")
val m8 = m7.add(0, "baz")

////////////// versus

implicit class MultiMapOps[A, B, CC[_]](val self: Map[A, CC[B]]) extends AnyVal {
  def mapValue[To >: CC[B] <: TraversableOnce[_]](key: A)(fun: CC[B] => To)
                                                 (implicit cbf: CanBuildFrom[CC[B], B, CC[B]]): Map[A, To] = {
    val before = self.getOrElse(key, cbf().result)
    val now    = fun(before)
    if (now.isEmpty) self - key else self.updated(key, now)
  }
}

val m1  = Map.empty[Int, Seq[String]]
val m2  = m1.mapValue(0)(_ :+ "foo")
val m3  = m2.mapValue(1)(_ :+ "bar")
val m4  = m3.mapValue(2)(_ :+ "baz")
val m4b = m4.mapValue(0)(_ take 0)

val m5  = Map.empty[Int, Set[String]]
val m6  = m5.mapValue(0)(_ + "foo")
val m7  = m6.mapValue(1)(_ + "bar")
val m8  = m7.mapValue(2)(_ + "baz")
val m8b = m8.mapValue(0)(_ - "foo")

////////////////////////////

implicit class MultiMapFactory[A, B](val self: TraversableOnce[(A, B)]) extends AnyVal {
  def toMultiMap[Col[_]](implicit cbf: CanBuildFrom[Nothing, B, Col[B]]): Map[A, Col[B]] = {
    var m = Map.empty[A, mutable.Builder[B, Col[B]]]
    self.foreach { case (k, v) =>
      val b = m.getOrElse(k, {
        val _b = cbf()
        m += k -> _b
        _b
      })
      b += v
    }
    m.mapValues(_.result())
  }
}

List(1 -> "foo", 2 -> "bar", 3 -> "bar").map(_.swap).toMultiMap[Seq]
List(1 -> List("foo"), 2 -> List("foo", "bar")).flatMap { case (a, b) => b.map(a -> _) } .toMultiMap[Seq]

Alternative toMultiMap version: http://stackoverflow.com/questions/22090371/scala-grouping-list-of-tuples#22092330