Designing a convenient default valued map in Scala

Question

I find myself using a lot of nested maps, e.g a Map[Int, Map[String, Set[String]]], and I'd like to have new Maps, Sets, etc. created automatically when I access a new key. E.g. something like the following:

val m = ...
m(1992)("foo") += "bar"

Note that I don't want to use getOrElseUpdate here if I don't have to because it gets pretty verbose when you have nested maps and obscures what's actually going on in the code:

m.getOrElseUpdate(1992, Map[String, Set[String]]()).getOrElseUpdate("foo", Set[String]()) ++= "bar"

So I'm overriding HashMap's "default" method. I've tried two ways of doing this, but neither is fully satisfactory. My first solution was to write a method that created the map, but it seems that I still have to specify the full nested Map type when I declare the variable or things don't work:

scala> def defaultingMap[K, V](defaultValue: => V): Map[K, V] = new HashMap[K, V] {                      |   override def default(key: K) = {
 |     val result = defaultValue
 |     this(key) = result
 |     result
 |   }
 | }
defaultingMap: [K,V](defaultValue: => V)scala.collection.mutable.Map[K,V]

scala> val m: Map[Int, Map[String, Set[String]]] = defaultingMap(defaultingMap(Set[String]()))
m: scala.collection.mutable.Map[Int,scala.collection.mutable.Map[String,scala.collection.mutable.Set[String]]] = Map()

scala> m(1992)("foo") += "bar"; println(m)                                                    
Map(1992 -> Map(foo -> Set(bar)))

scala> val m = defaultingMap(defaultingMap(Set[String]()))
m: scala.collection.mutable.Map[Nothing,scala.collection.mutable.Map[Nothing,scala.collection.mutable.Set[String]]] = Map()

scala> m(1992)("foo") += "bar"; println(m)
<console>:11: error: type mismatch;
 found   : Int(1992)
 required: Nothing
       m(1992)("foo") += "bar"; println(m)
         ^

My second solution was to write a factory class with a method, and that way I only have to declare each type a single time. But then each time I want a new default valued map, I have to both instantiate the factory class and then call the method, which still seems a little verbose:

scala> class Factory[K] {                                       
 |   def create[V](defaultValue: => V) = new HashMap[K, V] {
 |     override def default(key: K) = {                     
 |       val result = defaultValue                          
 |       this(key) = result                                 
 |       result                                             
 |     }                                                    
 |   }                                                      
 | }                                                        
defined class Factory

scala> val m = new Factory[Int].create(new Factory[String].create(Set[String]()))
m: scala.collection.mutable.HashMap[Int,scala.collection.mutable.HashMap[String,scala.collection.mutable.Set[String]]] = Map()

scala> m(1992)("foo") += "bar"; println(m)
Map(1992 -> Map(foo -> Set(bar)))

I'd really like to have something as simple as this:

val m = defaultingMap[Int](defaultingMap[String](Set[String]()))

Anyone see a way to do that?

Answer 1

With Scala 2.8:

object DefaultingMap {
  import collection.mutable
  class defaultingMap[K] {
    def apply[V](v: V): mutable.Map[K,V] = new mutable.HashMap[K,V] {
      override def default(k: K): V = {
        this(k) = v
        v
      }
    }
  }
  object defaultingMap {
    def apply[K] = new defaultingMap[K]
  }

  def main(args: Array[String]) {
    val d4 = defaultingMap[Int](4)
    assert(d4(3) == 4)
    val m = defaultingMap[Int](defaultingMap[String](Set[String]()))
    m(1992)("foo") += "bar"
    println(m)
  }
}

You can't curry type parameters in Scala, therefore the trick with the class to capture the key type is necessary.

By the way: I don't think that the resulting API is very clear. I particularly dislike the side-effecting map access.

Answer 2

Turns out I need to extend MapLike as well, or when I call filter, map, etc. my default valued map will get turned back into a regular Map without the defaulting semantics. Here's a variant of mkneissl's solution that does the right thing for filter, map, etc.

import scala.collection.mutable.{MapLike,Map,HashMap}

class DefaultingMap[K, V](defaultValue: => V) extends HashMap[K, V]
with 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
  }
}

object DefaultingMap {
  def apply[K] = new Factory[K]
  class Factory[K] {
    def apply[V](defaultValue: => V) = new DefaultingMap[K, V](defaultValue)
  }
}

And here that is, in action, doing the right thing with filter:

scala> val m = DefaultingMap[String](0)
m: DefaultingMap[String,Int] = Map()

scala> for (s <- "the big black bug bit the big black bear".split(" ")) m(s) += 1

scala> val m2 = m.filter{case (_, count) => count > 1}
m2: DefaultingMap[String,Int] = Map((the,2), (big,2), (black,2))