Puzzler 31

A View to a Shill

In Scala, there are often multiple ways of carrying out a given task. An example of this is transforming the elements of a map. One approach would be to use a for comprehension:

  def translate(m: Map[String, String]): Map[String, Int] =
    for ((k, v) <- m) yield (k, v.length)

This is actually desugared[1] to an invocation of map with a case clause:

  def translate(m: Map[String, String]): Map[String, Int] =
    m map { case (k, v) => (k, v.length) }

If only the values of a Map are being transformed, as in this example, the pattern variable k is effectively unused. In this case, the mapValues method provides a more elegant alternative:

  def translate(m: Map[String, String]): Map[String, Int] =
    m mapValues (_.length)

The following program demonstrates the use of map and the more concise mapValues method. What does it do?

  val ints = Map("15" -> List(1, 2, 3, 4, 5))
  val intsIter1 = ints map { case (k, v) => (k, v.toIterator) }
  val intsIter2 = ints mapValues (_.toIterator)
  
  println((intsIter1("15").next, intsIter1("15").next))
  println((intsIter2("15").next, intsIter2("15").next))

Possibilities

1. Prints:

     (1,2)
     (1,2)
   

2. Prints:

     (1,1)
     (1,1)
   

3. Both println statements throw a NoSuchElementException: next on empty iterator.
4. Prints:

     (1,2)
     (1,1)
   

Explanation

At first sight it appears that both statements should produce the same output, i.e., that the resulting maps should be identical. The first candidate answer, therefore, looks most reasonable. In reality, though, the result is different. The correct answer is number 4:

  scala> println((intsIter1(1).next, intsIter1(1).next))
  (1,2)
  
  scala> println((intsIter2(1).next, intsIter2(1).next))
  (1,1)

In particular, the second invocation of intsIter2(1).next produces 1. Could intsIter2(1) be iterating over the same element twice? No, the call to next does indeed advance the iterator. How then can the second call to intsIter2(1).next produce the same value as the first one? There can only be one explanation: the second call to intsIter2(1) returns a different iterator than the first. In other words, by some means, a new iterator is created every time a value is retrieved from intsIter2.

The documentation for mapValues confirms that this is indeed the case. Its description states simply that it "transforms the map by applying a function to every value"—the important detail is hidden in the returns part: a map view[2] that maps every key of this map to f(this(key)). The resulting map wraps the original map without copying any elements.

As a result, each retrieval from the wrapped map causes the mapping function, f, to be evaluated again, resulting in the creation of a new iterator. This contrasts with the map intsIter1, where iterators are created once when the map is transformed, and so every call to next is performed on the same iterator. This is evident from the following:

  scala> intsIter1(1) eq intsIter1(1)
  res0: Boolean = true
  
  scala> intsIter2(1) eq intsIter2(1)
  res1: Boolean = false

Discussion

The signature of mapValues does not indicate that it returns a view:

  def mapValues[C](f: (B) => C): Map[A, C]

A more specific return type or more explicit name, such as mapValuesView, would make it clearer that the result is actually a view on the original map.

It is also worth pointing out that there are performance implications associated with views, such as those returned by mapValues. Since each map value retrieval causes a function application to be performed, repeatedly iterating through such a lazy map can incur considerable overhead if the function is expensive.

Usually you can invoke the force method on a view to obtain a strict collection, but collection.immutable.Map, the type returned by mapValues, does not provide a force method. To work around this, you have to explicitly convert the map to a view before calling force. This produces the expected result:

  val intsIter2 = ints mapValues (_.toIterator)
  val strict = intsIter2.view.force
  
  scala> println(strict(1).next, strict(1).next)
  (1,2)

The surprising behavior of the code example in this puzzler is one of the reasons immutable data structures and pure functions are strongly favored in idiomatic Scala.

Familiarize yourself with the differences between views and regular collections, and be aware that mapValues returns a view even though it is not obvious from its name or signature.

Footnotes for Chapter 31:

[1] An additional example of desugaring a for expression appears in Puzzler 12.

[2] A view is a special kind of collection that lazily applies one or more transformations to an underlying "base" collection.