Puzzler 12

To Map, or Not to Map

Alongside standard functional idioms, such as for comprehensions and the combinators map and flatMap, Scala supports imperative operations on collections through for loops and the foreach method.

In this puzzler, both kinds of operations--functional and imperative--are used used to print the Roman numeral symbols in ascending order. What is the result of executing the following code in the REPL?

  case class RomanNumeral(symbol: String, value: Int)
  
  implicit object RomanOrdering extends Ordering[RomanNumeral] {
    def compare(a: RomanNumeral, b: RomanNumeral) = 
      a.value compare b.value
  }
  
  import collection.immutable.SortedSet
  
  val numerals = SortedSet(
    RomanNumeral("M", 1000), 
    RomanNumeral("C", 100),
    RomanNumeral("X", 10), 
    RomanNumeral("I", 1),
    RomanNumeral("D", 500), 
    RomanNumeral("L", 50),
    RomanNumeral("V", 5)
  )
  
  println("Roman numeral symbols for 1 5 10 50 100 500 1000:")
  for (num <- numerals; sym = num.symbol) { print(s"${sym} ") }
  numerals map { _.symbol } foreach { sym => print(s"${sym} ") }

Possibilities

1. Prints:

     Roman numeral symbols for 1 5 10 50 100 500 1000:
     I V X L C D M
     C D I L M V X
   

2. Prints:

     Roman numeral symbols for 1 5 10 50 100 500 1000:
     M C X I D L V
     M C X I D L V
   

3. Prints:

     Roman numeral symbols for 1 5 10 50 100 500 1000:
     I V X L C D M
     I V X L C D M
   

4. Prints:

     Roman numeral symbols for 1 5 10 50 100 500 1000:
     C D I L M V X
     I V X L C D M
   

Explanation

On the basis of the candidate answers, what you have to determine is which iteration order is applicable to the invocations: the order in which the numerals were added to the set, the order of their values, or of their symbols.

Since you are dealing with a sorted set you may assume that the sort order, rather than the declaration order, will determine the iteration sequence. And the ordering appears to be correctly implemented, based on the value. So surely both statements should iterate through the numerals in ascending numerical value and print I V X L C D M?

Not so—the correct answer is number 1:

  Roman numeral symbols for 1 5 10 50 100 500 1000:
  
  scala> for (num <- numerals; sym = num.symbol) { 
           print(s"${sym} ") }
  I V X L C D M
  scala> numerals map { _.symbol } foreach { sym =>
           print(s"${sym} ") }
  C D I L M V X

To start to understand the result, examine the first statement, which behaves as expected. According to The Scala Language Specification, a simple for (i <- expr) { fun(i) } loop is desugared to an invocation of the foreach method: expr foreach { i => fun(i) }.[1]

In this case, the for loop is not quite so simple, because of the additional value definition,[2] sym = num.symbol. To be able to pass both num and sym into the loop body, the compiler replaces numerals in the generator by a collection of (num, sym) tuples. It then invokes foreach on this collection of tuples and extracts both elements from the tuple before passing them to the actual loop body.[3] In short, the for loop is desugared roughly to the following:

  numerals map { num =>
    val sym = num.symbol
    (num, sym)
  } foreach { case (num, sym) =>
    println(sym)
  }

This turns out to be surprisingly similar to the second statement:

  numerals map { num => num.symbol } foreach { ... }

In both cases, therefore, foreach is not invoked on the original numerals set, but on the result of the map invocation. This, in turn, explains the different results.

What does map return? One of the main features of Scala collections is that transformations, such as map, preserve the type of the collection. In this case, the result is thus not an arbitrary collection with the same iteration order as the original, but a new SortedSet. This new SortedSet's iteration order is determined by its elements, not by the order of the elements in the original collection.

Since tuples are ordered first by their first elements,[4] which are simply the elements of numerals in succession, the iteration order of numerals and the sorted set of tuples is the same. As a result, the symbols are printed in the expected sequence, i.e., in order of ascending value.

The set of symbols that is created in the second statement, however, is a sorted set of strings, and is consequently ordered lexicographically. For this reason, the second statement prints the symbols alphabetically, rather than in the expected order of increasing value.

Discussion

Of course, in this particular case you can simply avoid the intermediate map and iterate over numerals directly, avoiding the unexpected reordering and an unnecessary iteration over the collection:

  scala> for (num <- numerals) { print(s"${num.symbol} ") }
  I V X L C D M
  
  scala> numerals foreach { num => print(s"${num.symbol} ") }
  I V X L C D M

In the general case, a possible alternative is to apply the transformation to a view[5] of the original collection:

  scala> numerals.view map { _.symbol } foreach { sym =>
           print(s"${sym} ") }
  I V X L C D M

Calling map on the view does not create an intermediate SortedSet. Instead, the num => num.symbol operation is applied lazily, only when the next element of the transformed numerals collection is retrieved and printed in the foreach loop.

The iteration order of the view is identical to that of the original collection, so the symbols are printed in the intended sequence.

As of Scala 2.11, however, there is still significant debate regarding the usability of views. A simple alternative is to start with a collection type whose iteration order is not affected by transformations, such as Seq:

  scala> numerals.toSeq map { _.symbol } foreach { sym =>
           print(s"${sym} ") }
  I V X L C D M

This usually comes at the cost of an additional iteration over the original collection, but it's easy and straightforward to use.

If you are carrying out transformations on a collection, especially when chaining multiple operations, note that the iteration order of the original collection is not automatically preserved. Convert the original to a sequence if stable iteration order is required.

---

Footnotes for Chapter 12:

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

[2] Ibid.

[3] Ibid.

[4] See the Scaladoc for scala.math.Ordering. [EPF]

[5] See section "Views" in the Scala collections library documentation. [Odea]