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.
精彩评论