Type information is lost when working with high-kinded objects in Scala

I am trying to factorize some code and ended up having to work with higher-kinded types. The following minimal example works fine:

trait Builder[M[_]] { def build[A]: M[A] def buildPair[A, B]: (M[A], M[B]) = (build[A], build[B]) } class List[A] class BuilderList extends Builder[List] { def build[A] = new List[A] } val l: List[String] = (new BuilderList).build[String] val ll: (List[String], List[Double]) = (new BuilderList).buildPair[String, Double] defined trait Builder defined class List defined class BuilderList l: List[String] = List@5c7754a7 ll: (List[String], List[Double]) = (List@62874648,List@7b0f6537) 

If I now want to apply this to a type with two type arguments, say

class Map[K, V] 

I would like to be able to write

trait BuilderMap[K] extends Builder[Map[K, _]] {...} 

but of course this does not work because type arguments in Scala are not curried.

I found that the following trick allowed me to pass compilation:

trait PartialApplier[F[_, _], K] { type PartiallyApplied[_] = F[K, _] } class BuilderMap[K] extends Builder[PartialApplier[Map, K]#PartiallyApplied] { def build[V] = new Map[K, V] } 

But then, some strange effect happens and I can't figure out the reason why:

scala> val m: Map[Int, String] = (new BuilderMap[Int]).build[String] m: Map[Int,String] = Map@71da0c64 scala> val mm: (Map[Int, String], Map[Int, Double]) = (new BuilderMap[Int]).buildPair[String, Double] <console>:21: error: type mismatch; found : (Map[Int, _], Map[Int, _]) required: (Map[Int,String], Map[Int,Double]) val mm: (Map[Int, String], Map[Int, Double]) = (new BuilderMap[Int]).buildPair[String, Double] 

It seems that the functions defined in the higher-kinded trait Builder lose some type information when I use the PartialApplier trick.

Is there a way to make all this work smoothly together? Maybe the PartialApplier trick is not the right way to go!