为何PrefixMap调用++方法后返回mutable.Map而非PrefixMap？

你遇到的问题核心在于编译器没有选中你自定义的CanBuildFrom实例，而是默认使用了mutable.Map自带的CanBuildFrom。让我们一步步拆解原因和解决方案：

问题根源 #

你的CanBuildFrom定义是这样的：

implicit def canBuildFrom[T] : CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] = ...

这里的问题有两个关键点：

1. PrefixMap是不变类型：你的PrefixMap[T]继承自不变的mutable.Map[String, T]，因此PrefixMap[Int]和PrefixMap[_]之间没有子类型关系（对于不变类，C[Int]不是C[_]的子类型，反之亦然）。而CanBuildFrom的第一个类型参数From是逆变的，这意味着编译器无法将CanBuildFrom[PrefixMap[_], ...]匹配到实际需要的CanBuildFrom[PrefixMap[Int], ...]。
2. mutable.Map的CanBuildFrom更"具体"：由于PrefixMap[Int]是mutable.Map[String, Int]的子类，而CanBuildFrom的From参数是逆变的，CanBuildFrom[Map[String, Int], (String, Int), Map[String, Int]]（来自mutable.Map）会被编译器认为比你的自定义CanBuildFrom更匹配，因此被优先选中。

解决方案 #

调整你的CanBuildFrom定义，让它的From参数支持任意类型参数的PrefixMap，而不是通配符。修改后的代码如下：

import collection._
import scala.collection.mutable.{Builder, MapBuilder}
import scala.collection.generic.CanBuildFrom

object PrefixMap {
  def empty[T] = new PrefixMap[T]
  def apply[T](kvs: (String, T)*): PrefixMap[T] = {
    val m: PrefixMap[T] = empty
    for (kv <- kvs) m += kv
    m
  }
  def newBuilder[T]: Builder[(String, T), PrefixMap[T]] = new MapBuilder[String, T, PrefixMap[T]](empty)
  
  // 修改这里：添加类型参数S，让From类型为PrefixMap[S]
  implicit def canBuildFrom[S, T] : CanBuildFrom[PrefixMap[S], (String, T), PrefixMap[T]] = new CanBuildFrom[PrefixMap[S], (String, T), PrefixMap[T]] {
    def apply(from: PrefixMap[S]) = newBuilder[T]
    def apply() = newBuilder[T]
  }
}

class PrefixMap[T] extends mutable.Map[String, T] with mutable.MapLike[String, T, PrefixMap[T]] {
  var suffixes: immutable.Map[Char, PrefixMap[T]] = Map.empty
  var value: Option[T] = None
  def get(s: String): Option[T] = if(s.isEmpty) value else suffixes get (s(0)) flatMap (_.get(s substring 1))
  def withPrefix(s: String): PrefixMap[T] = {
    if(s.isEmpty) this
    else {
      val leading = s(0)
      suffixes get leading match {
        case None => suffixes = suffixes + (leading -> empty)
        case _ =>
      }
      suffixes(leading) withPrefix (s substring 1)
    }
  }
  override def update(s: String, elem: T) = withPrefix(s).value = Some(elem)
  override def remove(s: String): Option[T] = if(s.isEmpty) { val prev = value; value = None; prev} else suffixes get (s(0)) flatMap (_.remove(s substring 1))
  def iterator: Iterator[(String, T)] = (for (v <- value.iterator) yield ("", v)) ++ (for ((chr, m) <- suffixes.iterator; (s, v) <- m.iterator) yield (chr +: s, v))
  def += (kv: (String, T)): this.type = { update(kv._1, kv._2); this }
  def -= (s: String): this.type = { remove(s); this }
  override def empty = new PrefixMap[T]
}

现在再测试你的示例：

scala> PrefixMap("abc" -> 12, "abb" -> 13)
res0: PrefixMap[Int] = Map(abc -> 12, abb -> 13)
scala> PrefixMap("aaa" -> 15)
res1: PrefixMap[Int] = Map(aaa -> 15)
scala> res0 ++ res1
res2: PrefixMap[Int] = Map(abc -> 12, abb -> 13, aaa -> 15)

这次res2的类型就是PrefixMap[Int]了！

补充说明 #

• CanBuildFrom的逆变特性：CanBuildFrom[-From, -Elem, +To]中，From是逆变的，意味着如果A <: B，那么CanBuildFrom[B, ...] <: CanBuildFrom[A, ...]。修改后的CanBuildFrom[PrefixMap[S], ...]比CanBuildFrom[Map[String, S], ...]更具体（因为PrefixMap[S] <: Map[String, S]），所以编译器会优先选择你的自定义实现。
• 为什么原来的PrefixMap[_]不行：对于不变的PrefixMap[T]，PrefixMap[_]是一个存在类型，它不代表任何具体的PrefixMap子类型，因此无法匹配实际的PrefixMap[Int]作为From参数。

内容的提问来源于stack exchange，提问作者Mizunashi