An immutable multi-map that expresses the value type as a type function of the key type. Create it with a type constructor that expresses the relationship:

trait Key { type Type = T }
case class MyValue[T](...)

// type function from Key to MyValue
type KV[K <: Key] = MyValue[K#Type]

val map = TypedMultiMap.empty[Key, KV]

// a plain Int => String map would use this function:
type plain[K <: Int] = String

// a map T => T would use this function:
type identity[T <: AnyRef] = T

Caveat: using keys which take type parameters does not work due to conflicts with the existential interpretation of Key[_]. A workaround is to define a key type like above and provide a subtype that provides its type parameter as type member Type.