Nested Default Maps in Scala

Question

I'm trying to construct nested maps in Scala, where both the outer and inner map use the "withDefaultValue" method. For example, the following :

val m = HashMap.empty[Int, collection.mutable.Map[Int,Int]].withDefaultValue( HashMap.empty[Int,Int].withDefaultValue(3))
m(1)(2)
res: Int = 3
m(1)(2) = 5
m(1)(2) 
res: Int = 5
m(2)(3) = 6
m
res : scala.collection.mutable.Map[Int,scala.collection.mutable.Map[Int,Int]] = Map()

So the map, when addressed by the appropriate keys, gives me back what I put in. However, the map itself appears empty! Even m.size returns 0 in this example. Can anyone explain what's going on here?

Answer 1

I just had the exact same problem, and was happy to find dhg's answer. Since typing getOrElseUpdate all the time is not very concise, I came up with this little extension of the idea that I want to share: You can declare a class that uses getOrElseUpdate as default behavior for the () operator:

class DefaultDict[K, V](defaultFunction: (K) => V) extends HashMap[K, V] {
  override def default(key: K): V = return defaultFunction(key)
  override def apply(key: K): V = 
    getOrElseUpdate(key, default(key))
}

Now you can do what you want to do like this:

var map = new DefaultDict[Int, DefaultDict[Int, Int]](
  key => new DefaultDict(key => 3))
map(1)(2) = 5

Which does now result in map containing 5 (or rather: containing a DefaultDict containing the value 5 for the key 2).

Answer 2

Short answer

It's definitely not a bug.

Long answer

The behavior of withDefaultValue is to store a default value (in your case, a mutable map) inside the Map to be returned in the case that they key does not exist. This is not the same as a value that is inserted into the Map when they key is not found.

Let's look closely at what's happening. It will be easier to understand if we pull the default map out as a separate variable so we can inspect is at will; let's call it default

import collection.mutable.HashMap
val default = HashMap.empty[Int,Int].withDefaultValue(3)

So default is a mutable map (that has its own default value). Now we can create m and give default as the default value.

import collection.mutable.{Map => MMap}
val m = HashMap.empty[Int, MMap[Int,Int]].withDefaultValue(default)

Now whenever m is accessed with a missing key, it will return default. Notice that this is the exact same behavior as you have because withDefaultValue is defined as:

def withDefaultValue (d: B): Map[A, B]

Notice that it's d: B and not d: => B, so it will not create a new map each time the default is accessed; it will return the same exact object, what we've called default.

So let's see what happens:

m(1) // Map()

Since key 1 is not in m, the default, default is returned. default at this time is an empty Map.

m(1)(2) = 5

Since m(1) returns default, this operation stores 5 as the value for key 2 in default. Nothing is written to the Map m because m(1) resolves to default which is a separate Map entirely. We can check this by viewing default:

default // Map(2 -> 5)

But as we said, m is left unchanged

m // Map()

---

Now, how to achieve what you really wanted? Instead of using withDefaultValue, you want to make use of getOrElseUpdate:

def getOrElseUpdate (key: A, op: ⇒ B): B

Notice how we see op: => B? This means that the argument op will be re-evaluated each time it is needed. This allows us to put a new Map in there and have it be a separate new Map for each invalid key. Let's take a look:

val m2 = HashMap.empty[Int, MMap[Int,Int]]

No default values needed here.

m2.getOrElseUpdate(1, HashMap.empty[Int,Int].withDefaultValue(3)) // Map()

Key 1 doesn't exist, so we insert a new HashMap, and return that new value. We can check that it was inserted as we expected. Notice that 1 maps to the newly added empty map and that they 3 was not added anywhere because of the behavior explained above.

m2 // Map(1 -> Map())

Likewise, we can update the Map as expected:

m2.getOrElseUpdate(1, HashMap.empty[Int,Int].withDefaultValue(1))(2) = 6

and check that it was added:

m2 // Map(1 -> Map(2 -> 6))