Immutable multimap via implicit class

MultiMap.scala

  implicit class MultiMap[K, V](map: Map[K, Set[V]]) {
    def addBinding(k: K, v: V) = addBindings(k, Set(v))

    def addBindings(k: K, vs: Set[V]) = map.get(k) match {
      case None     => map + (k -> vs)
      case Some(xs) => map + (k -> (vs ++ xs))
    }

    def removeBinding(k: K, v: V) = map.get(k) match {
      case None     => map
      case Some(vs) =>
        val vs2 = vs - v
        if (vs2.isEmpty)
          map - k
        else
          map + (k -> vs2)
    }

    def removeAll(v: V) = map.keys.foldLeft(map)((m, k) => m.removeBinding(k, v))
  }