Puzzler 33

The Devil Is in the Defaults

In many languages, assigning default values to entries in a map involves tedious, boilerplate code:

  import collection.mutable
  val accBalances = mutable.Map[String, Int]()
  
  // opening credit is linked to the account holder's name
  def getBalance(accHolder: String): Int = {
    if (!(accBalances isDefinedAt accHolder)) {
      accBalances += (accHolder -> accHolder.length)
    }
    accBalances(accHolder)
  }
  
  scala> println(getBalance("Alice"))
  5

Fortunately, you can eliminate this clutter in Scala (and avoid mutable maps as well!) by providing a default function:

  import collection.immutable
  val accBalances = immutable.Map[String, Int]() withDefault {
    newCustomer => newCustomer.length }
  
  scala> println(accBalances("Bob"))
  3

This is a nice, clean way of providing a default value based on the map key. Often, though, the default is not dependent on the key. In that case, Map's withDefaultValue method is a better fit:

  import collection.immutable
  val accBalances = 
    immutable.Map[String, Int]() withDefaultValue 10
  
  scala> println(accBalances("Bob"))
  10

In the following example, each account holder starts off with a "thank you for joining" balance of 100 dollars. Accounts are represented in two different ways, as simple balances in accBalances and as balance histories in accBalancesWithHist. Two new customers then cash in on their unexpected gift. What is the result of executing the following code?

  import collection.mutable
  import collection.mutable.Buffer
  
  val accBalances: mutable.Map[String, Int] =
    mutable.Map() withDefaultValue 100
  
  def transaction(accHolder: String, amount: Int,
      accounts: mutable.Map[String, Int]) {
    accounts += accHolder -> (accounts(accHolder) + amount)
  }
  
  val accBalancesWithHist: mutable.Map[String, Buffer[Int]] =
    mutable.Map() withDefaultValue Buffer(100)
  
  def transactionWithHist(accHolder: String, amount: Int,
      accounts: mutable.Map[String, Buffer[Int]]) {
    val newAmount = accounts(accHolder).head + amount
    accounts += accHolder ->
      (newAmount +=: accounts(accHolder))
  }
  
  transaction("Alice", -100, accBalances)
  println(accBalances("Alice"))
  println(accBalances("Bob"))

  transactionWithHist("Dave", -100, accBalancesWithHist)
  println(accBalancesWithHist("Carol").head)
  println(accBalancesWithHist("Dave").head)

Possibilities

1. Prints:

     -100
     0
     0
     -100
   

2. Prints:

     0
     100
     0
     100
   

3. Prints:$sn8978]$

     0
     100
     100
     0
   

4. Prints:

     0
     100
     0
     0
   

Explanation

You may wonder whether updating the map before retrieving any values somehow affects the default, or if the order in which the entries are accessed makes a difference. Adding history to the account representation surely has no impact, though?

Indeed it does. The correct answer is number 4:

  scala> println(accBalances("Alice"))
  0
  
  scala> println(accBalances("Bob"))
  100
  
  scala> println(accBalancesWithHist("Carol").head)
  0
  
  scala> println(accBalancesWithHist("Dave").head)
  0

So Alice and Bob's account balances are as expected, but Carol and Dave's accounts with history are not behaving as intended. To understand what is going on, compare the actual account objects for Carol and Dave:

  scala> println(accBalancesWithHist("Carol")
           eq accBalancesWithHist("Dave"))
  true

In other words, once the account history is added, Carol and Dave (and indeed all other account holders) are sharing the same account! The behavior of withDefault may lead you to think that withDefaultValue also acts as a "factory," providing new instances of the default value for each map entry. This is not the case: the same value is used as the default for all entries.

Discussion

Since sharing the same value across all map entries can have unexpected consequences, the safest and most predictable approach to providing defaults is to use withDefault, certainly for mutable default values. This creates a new instance of the default value for each map entry:

  val accBalancesWithHist2: mutable.Map[String, Buffer[Int]] =
    mutable.Map() withDefault { _ => Buffer(100) }
  
  transactionWithHist("Dave", -100, accBalancesWithHist2)
  
  scala> println(accBalancesWithHist2("Carol").head)
  100
  
  scala> println(accBalancesWithHist2("Dave").head)
  0

If you want to avoid the slight boilerplate of the unused underscore (_) parameter to withDefault's default function, or feel that a method name explicitly mentioning values improves readability, you can define your own withDefaultValue method:

  import collection.mutable
  import collection.mutable.Buffer
  implicit class MapDefaults[A, B](
      val map: mutable.Map[A, B]) extends AnyVal {
    def withNewDefaultValue(d: => B): mutable.Map[A, B] =
      map withDefault { _ => d }
  }
  
  ...
  
  val accBalancesWithHist: mutable.Map[String, Buffer[Int]] =
    mutable.Map() withNewDefaultValue Buffer(100)
  
  transactionWithHist("Dave", -100, accBalancesWithHist)
  
  scala> println(accBalancesWithHist("Carol").head)
  100
  
  scala> println(accBalancesWithHist("Dave").head)
  0
  
  scala> println(accBalancesWithHist("Carol")
           eq accBalancesWithHist("Dave"))
  false

Here, declaring the value passed to withNewDefaultValue as a by-name parameter[1][2] causes it to be re-evaluated every time the default function is called. This results in each map entry being assigned a "fresh" instance of the default value.

If the default value is immutable, sharing the same instance across all map entries is not a problem. In fact, if the value is expensive to construct, this will be be cheaper than creating a new instance for each map entry.

Use Map.withDefaultValue for immutable defaults only, and Map.withDefault otherwise. Be aware that withDefaultValue results in the same instance of the default value being shared across all map entries.

Footnotes for Chapter 33:

[1] Odersky, The Scala Language Specification, Section 4.6.1. [Ode14]

[2] See Puzzler 23 for a more detailed discussion of by-name parameters.