Typing Scala collections

I wanted to learn the new Scala collections framework by making a very general prefix tree. Not only must the keys and the values be parameters, but the type of the maps used in each node must be parameters too. So I tried this:

import collection.immutable.MapLike

class PrefixMap[+M[K1,+V1] <: Map[K1,V1] with MapLike[K1,V1,M[K1,V1]],K,+V](val content: Option[V], val children: M[K,PrefixMap[M,K,V]])
  extends Map[Iterable[K],V]
  with MapLike[Iterable[K],V,PrefixMap[M,K,V]] {

    override def empty: PrefixMap[M,K,V] = new PrefixMap[M,K,V](None, children.empty)
}

But this doesn't compile:

PrefixMap.scala:19: error: type mismatch;
 found   : scala.collection.immutable.Map[K,PrefixMap[M,K,V]]
 required: M[K,PrefixMap[M,K,V]]
    override def 开发者_如何学Pythonempty: PrefixMap[M,K,V] = new PrefixMap[M,K,V](None, children.empty)
                                                                               ^
one error found

This confuses me. I can see from the documentation that a MapLike has an empty that returns "This". So, since children is of type M[K,PrefixMap[M,K,V]], children.empty should be of that type too.

What's going wrong, and can it be mended?

Well, the problem is that MapLike defines an empty that returns This, but Map.empty returns Map!

Try, for instance:

override def empty: PrefixMap[M,K,V] = new PrefixMap[M,K,V](None, (children: MapLike[K,PrefixMap[M,K,V],M[K,PrefixMap[M,K,V]]]).empty)

This will compile, because you are hiding Map's type. The code won't compile because it is missing abstract methods, but that's another matter.