Implement a scala collection so that map, filter, etc. produce the right type

Question

I'm trying to implement a default valued map, and I'd like filters, maps, etc. over a DefaultingMap to also produce a DefaultingMap whenever possible. Here's my initial implementation:

class DefaultingMap[K, V](defaultValue: => V)
extends mutable.HashMap[K, V]
with mutable.MapLike[K, V, DefaultingMap[K, V]] {

  override def empty = new DefaultingMap[K, V](defaultValue)

  override def default(key: K): V = {                 
    val result = this.defaultValue
    this(key) = result
    result                                            
  }
}

I get objects of type DefaultingMap when I use filter, but not when I use map:

scala> val counter = new DefaultingMap[Char, Int](0)
counter: DefaultingMap[Char,Int] = Map()

scala> for (c <- "ababcbbb") counter(c) += 1

scala> counter.filter{case (k, v) => v > 1}
res1: DefaultingMap[Char,Int] = Map((a,2), (b,5))

scala> counter.map{case (k, v) => (k, v * 2)}
res2: scala.collection.mutable.HashMap[Char,Int] = Map((a,4), (c,2), (b,10))

The difference between these two methods seems to be that map takes an implicit CanBuildFrom. So I gather that I need to have an implicit def somewhere to provide the CanBuildFrom. My first intuition was to do what's done in HashMap:

object DefaultingMap extends generic.MutableMapFactory[DefaultingMap] {

  def empty[K, V]: DefaultingMap[K, V] = // Not possible!

  implicit def canBuildFrom[K, V]:
    generic.CanBuildFrom[Coll, (K, V), DefaultingMap[K, V]] = 
      new MapCanBuildFrom[K, V]
}

I believe this would get it to compile, but this approach won't work because it's impossible to define the empty method - you need to know what the defaultValue should be. If I could define the CanBuildFrom in the class itself, instead of the companion object, I would be okay because the defaultValue is available there.

How can I get this to work?

Answer 1

Mutable maps are Builders in Scala, so the MapFactory by default takes an empty map of the type in question to obtain a builder.

If you have custom map build rules, one of the things you can do is to define your custom factory similar to collection.generic.MapFactory. You would have to define it in a similar way like there, but make both the empty method and the newBuilder method take an additional argument for the defaultValue.

Something along the lines of (if you read more about the Scala 2.8 collections API in the other link suggested, you'll find that you don't have to implement generic companion objects for maps):

import collection._                                                                      


class DefaultingMap[K, V](val defaultValue: V)                                                                      
extends mutable.HashMap[K, V]                                                                                       
with mutable.MapLike[K, V, DefaultingMap[K, V]] {                                                                   

  override def empty = new DefaultingMap(defaultValue)                                                              

}                                                                                                                   


object DefaultingMap {                                                                                              
  def newBuilder[K, V](d: V): DefaultingMap[K, V] = new DefaultingMap[K, V](d)                                      

  implicit def canBuildFrom[K, V] =                                                                                 
    new generic.CanBuildFrom[DefaultingMap[K, V], (K, V), DefaultingMap[K, V]] {                                    
      def apply(from: DefaultingMap[K, V]) = newBuilder[K, V](from.defaultValue)                                    
      def apply() = error("unsupported default apply")                                                              
    }                                                                                                               
}                                                                                                                   


object Main {                                                                                                       
  def main(args: Array[String]) {                                                                                   
    println((new DefaultingMap[Int, Int](5)).defaultValue)                                                          
    println(((new DefaultingMap[Int, Int](5)).map(x => x)).defaultValue)                                            
  }                                                                                                                 
}

Prints:

$ scalac defaulting.scala
$ scala Main
5
5

I admit, still, this does not solve the problem for the parameterless apply.