Why PrefixMap ++ PrefixMap become mutable.Map

Question

Running a PrefixMap example of programming in Scala in sbt console.

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: scala.collection.mutable.Map[String,Int] = Map(abc -> 12, abb -> 13, aaa -> 15)

This result confused me.

I've thought when "++" method is called, "++" method uses implicit canBuildFrom in object PrefixMap and new PrefixMap instance is created, but it seems to use another implicit value from somewhere and new Map instance is created.

Why is res2 type not PrefixMap? Or, I made a mistake somewhere?

Following is a code from PrefixMap example.

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)

  implicit def canBuildFrom[T]
    : CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] =
      new CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] {
        def apply(from: PrefixMap[_]) = 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]
}

user_182660 · Answer

First of all it is important to understand that there is a difference between the type of a variable and the type of the value stored in that variable. In your example the actual type of the result ++ is still PrefixMap but the type of the variable (i.e. what the compilers can prove) is just mutable.Map and this is what you see in REPL. You can easily verify this by printing res2.getClass to get the actual type.

I think this happens because Map has actually two different ++ methods:

one comes from TraversabelLike and it is a smart one with CanBuildFrom and all the other fancy stuff
another comes from scala.collection.MapLike overridden at scala.collection.mutable.MapLike and it is much less generic

 // collection.MapLike so here Map is collection.Map
 def ++[V1 >: V](xs: GenTraversableOnce[(K, V1)]): Map[K, V1]

 // mutable.MapLike so here the output Map is the mutable.map
 override def ++[V1 >: V](xs: GenTraversableOnce[(K, V1)]): Map[K, V1]

Since your code is located in a specific context where compilers knows exactly the class (as opposed to something like a generic .filter which has to use TraversableLike infrastructure), the compilers uses the simpler ++ coming from mutable.MapLike.

I'm not sure why this other MapLike.++ method exists in the first place. Probably this is to support backward compatibility with some legacy design (Scala collections library has been re-designed several times). But the only way to make this bunch of methods (there are several more like +) to work as you wish, is to do what mutable.MapLike does: i.e. override them in your PrefixMap defining more specific types. Also beware that MapLike.++ internally uses clone(), so you better to work correctly with that or to re-implement it.

Why PrefixMap ++ PrefixMap become mutable.Map

1 Answers