Pimping Map to MultiMap

Hi,

Some time ago I complained there is no MultiMap working with immutable
Maps. So I've created this simple thing, to be able to use any Map[_,
Set[_]] as an immutable MultiMap:

object MultiMapUtil {

class MultiMap[K, V, M <: Map[K, Set[V]]](map: M) {

def addBinding(k: K, v: V): M = {
val r = (map.getOrElse(k, Set.empty[V]) + v)
(map + (k -> r)).asInstanceOf[M]
}

def removeBinding(k: K, v: V): M = {
val r = (map.getOrElse(k, Set.empty[V]) - v)
(if (r.isEmpty) map - k else map + (k -> r)).asInstanceOf[M]
}
}

implicit def mapToMultiMap[K, V, S[V] <: Set[V], M[K, S] <: Map[K,
S]](map: M[K, S[V]]) =
new MultiMap[K, V, M[K, S[V]]](map)
}

It seems to work:
TreeMap.empty[Int, HashSet[Int]]
.addBinding(1,2)
.addBinding(1,3)
.addBinding(1,4)
.addBinding(0,2)

scala.collection.immutable.TreeMap[Int,scala.collection.immutable.HashSet[Int]]
= Map((0,Set(2)), (1,Set(2, 3, 4)))

But I feel a little uncomfortable with the asInstanceOf.
Can it be done better? How do you like it?

Best regards,
Piotr Kołaczkowski