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.

Answer 2

If you use collection.immutable.Map in 2.8 or above, then the withDefault method is available to you:

val m = collection.immutable.Map(1->"a", 2->"b", 3->"c")
val n = m withDefaultValue "default"

// n(7) will return "default"

UPDATE

If you're mapping over the collection, move the withDefaultValue to the end of the processing chain:

val o = (for ((k, v) <- m) yield (k, v)) withDefaultValue "default"
// o(0) will return "default"

Answer 3

Ok, here's an approach that's very, very close to what I want:

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                                            
  }

  implicit def canBuildFrom[NK] =
    new generic.CanBuildFrom[DefaultingMap[K, V], (NK, V), DefaultingMap[NK, V]] {
      def apply(from: DefaultingMap[K, V]) =
        new DefaultingMap[NK, V](from.newDefaultValue)
      def apply() =
        new DefaultingMap[NK, V](defaultValue)
    }

  def newDefaultValue = defaultValue
}

Now, if I get that CanBuildFrom into scope, everything works like a charm:

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

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

scala> import counter._
import counter._

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

scala> for ((k, v) <- counter; if v > 1) yield (k.toString, v * 2)
res2: DefaultingMap[java.lang.String,Int] = Map((a,4), (b,10))

However, if I leave off that import counter._, I get the same behavior as before. If I can just figure out how to get that implicit def canBuildFrom to be found, I'll be set...

Answer 4

The Scala 2.8 Collections API is a very nice document and I seem to remember it discussing this aspect of transformation, though I don't remember exactly where. I guess that isn't very helpful...

Answer 5

It won’t help you with the return type of map (but then again, the default value of the new collection cannot generally be defined by using the map transformation). But to give you another approach:

class DefaultHashMap[A, B](dflt: => B) extends scala.collection.mutable.Map[A, B] {
  val underlying = new scala.collection.mutable.HashMap[A, B]()

  def get(key: A) = underlying.get(key) orElse Some(default(key))
  def iterator: Iterator[(A, B)] = underlying.iterator
  def +=(kv: (A, B)) = { underlying += kv; this }
  def -=(key: A) = { underlying -= key; this }
  override def empty: DefaultHashMap[A, B] = new DefaultHashMap[A, B](dflt)
  override def default(key: A) = dflt
}