Martin Odersky's ScalaDay's 2011 Example: Yielding a Map?

Question

I was working through Odersky's ScalaDays 2011 keynote talk, where he constructs a phone number synonym generator in remarkably few lines of code, when I got to this particular line (assigning charCode):

val mnem: Map[Char, String] = // phone digits to mnemonic chars (e.g. '2' -> "ABC")
val charCode: Map[Char, Char] = for ((digit, str) <- mnem; letter <- str)
    yield (letter -> digit)   // gives ('A', '2'), ('B', '2') etc

Why is charCode of type Map?

When I yield tuples in other examples, I merely obtain a sequence of tuples -- not a map. For example:

scala> for (i <- 1 to 3) yield (i -> (i+1))
res16: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,2), (2,3), (3,4))

One can easily convert that to a map with toMap(), like so...

scala> (for (i <- 1 to 3) yield (i -> (i+1))).toMap
res17: scala.collection.immutable.Map[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4)

... but somehow, Odersky's example avoids this.

What Scala magic, if any, am I overlooking here?

---

Addendum 1: Implicit conversion? I'd like to add some detail pertaining to Oxbow Lake's comment (NB: my comment there may be partially in error, having misunderstood slightly, perhaps, what he was getting at).

I suspected that some kind of implicit conversion was happening because a map was required. So I tried Odersky's iterator in the interpreter, with no hints as to what it should produce:

scala> val mnem = Map('2' -> "ABC", '3' -> "DEF", '4' -> "GHI") // leaving as a map, still
scala> for ((digit, str) <- mnem; letter <- str) yield (letter, digit)
res18: scala.collection.immutable.Map[Char,Char] = Map(E -> 3, F -> 3, A -> 2, I -> 4, G -> 4, B -> 2, C -> 2, H -> 4, D -> 3)

(Note that I'm leaving mnem as a map here.)

Likewise, telling the compiler I wanted a map didn't change my own result:

scala> val x: Map[Int,Int] = for (i <- 1 to 3) yield (i -> (i+1))
<console>:7: error: type mismatch;
 found   : scala.collection.immutable.IndexedSeq[(Int, Int)]
 required: Map[Int,Int]
       val x: Map[Int,Int] = for (i <- 1 to 3) yield (i -> (i+1))

On the other hand, following Eastsun's hints (and this seems to be what OL was saying, too), the following (dorky) modification does produce a map:

scala> for ((i,j) <- Map(1 -> 2, 2 -> 2)) yield (i -> (i+1))
res20: scala.collection.immutable.Map[Int,Int] = Map(1 -> 2, 2 -> 3)

So if the iterated value comes from a map, somehow a map is produced?

I expect the answer is to be understood by (a) converting the "for" loop to its longhand equivalents (a call/calls to map) and (b) understanding what implicits are being magically invoked.

---

Addendum 2: Uniform Return Type: (huynhjl:) That seems to be it. My first example converts to

(1 to 3).map(i => (i, i+1)) // IndexedSeq[(Int, Int)]

Whereas the second becomes something akin to this:

Map(1 -> 2, 2 -> 2).map(i => (i._1, i._1+1)) // Map[Int,Int]

The type of "Map.map" is, then

def map [B, That] (f: ((A, B)) ⇒ B)(implicit bf: CanBuildFrom[Map[A, B], B, That]): That   

Ah, trivial. ;-)

---

Addendum 3: Well, okay, that was too simple, still. Miles Sabin provides a/the more correct desugaring, below. Even more trivial. ;-)

Answer 1

It's easier to understand why you get a Map back if you desugar the for comprehension,

val charCode: Map[Char, Char] = for ((digit, str) <- mnem; letter <- str)
  yield (letter -> digit)

is equivalent to,

val charCode = mnem.flatMap {
  case (digit, str) => str.map { letter => (letter -> digit) }
}

So the type inferred for charCode here will be the result type of flatMap applied to a Map. flatMap's signature is quite complex,

def flatMap [B, That]
  (f: ((A, B)) => GenTraversableOnce[B])
  (implicit bf: CanBuildFrom[Map[A, B], B, That]): That

because it's providing the infrastructure that the Scala compiler needs to compute the appropriate result type given the type of the Map and the type of the function being (flat)Map'd across it.

As has been mentioned elsewhere, the collections framework has been designed in such a way that containers will be (flat)Map'd to containers of the same shape where possible. In this case we're mapping across a Map[Char, String], so its elements are equivalent to pairs (Char, String). And the function we're mapping is producing pairs (Char, Char), which concatenated can give us back a Map[Char, Char].

We can verify that the compiler believes this too by looking up the corresponding CanBuildFrom instance,

scala> import scala.collection.generic.CanBuildFrom
import scala.collection.generic.CanBuildFrom

scala> implicitly[CanBuildFrom[Map[Char, String], (Char, Char), Map[Char, Char]]]
res0: scala.collection.generic.CanBuildFrom[Map[Char,String],(Char, Char),Map[Char,Char]] = scala.collection.generic.GenMapFactory$MapCanBuildFrom@1d7bd99

Notice that the CanBuildFrom's last type argument is Map[Char, Char]. This fixes the "That" type parameter in flatMap's signature, and that gives us the result type for this flatMap, and hence the inferred type of charCode.

Answer 2

charCode is a Map because mnem is a Map. You got a sequece because 1 to 3 is a sequence

Some interesting examples:

EDIT: I add a link to show how the magic of breakOut works. Scala 2.8 breakOut

Welcome to Scala version 2.10.0.r25713-b20110924020351 (Java HotSpot(TM) Client VM, Java 1.6.0_26).
Type in expressions to have them evaluated.
Type :help for more information.

scala> val seq = 1 to 3
seq: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3)

scala> val seq2 = for(i <- seq) yield (i -> (i+1))
seq2: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,2), (2,3), (3,4))

scala> import collection.breakOut
import collection.breakOut

scala> val map2: Map[Int,Int] = (for(i<-seq) yield(i->(i+1)))(breakOut)
map2: Map[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4)

scala> val list2: List[(Int,Int)] = (for(i<-seq) yield(i->(i+1)))(breakOut)
list2: List[(Int, Int)] = List((1,2), (2,3), (3,4))

scala> val set2: Set[(Int,Int)] = (for(i<-seq) yield(i->(i+1)))(breakOut)
set2: Set[(Int, Int)] = Set((1,2), (2,3), (3,4))

scala> val map = (1 to 3).zipWithIndex.toMap
map: scala.collection.immutable.Map[Int,Int] = Map(1 -> 0, 2 -> 1, 3 -> 2)

scala> val map3 = for((x,y) <- map) yield(x,"H"+y)
map3: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> H0, 2 -> H1, 3 -> H2)

scala> val list3: List[(Int,String)] = (for((x,y) <- map) yield(x,"H"+y))(breakOut)
list3: List[(Int, String)] = List((1,H0), (2,H1), (3,H2))

scala> val set3: Set[(Int,String)] = (for((x,y) <- map) yield(x,"H"+y))(breakOut)
set3: Set[(Int, String)] = Set((1,H0), (2,H1), (3,H2))

scala> val array3: Array[(Int,String)] = (for((x,y) <- map) yield(x,"H"+y))(breakOut)
array3: Array[(Int, String)] = Array((1,H0), (2,H1), (3,H2))

scala>

Answer 3

The magic you are overlooking is called the uniform return type principle. See An Overview of the Collections API section in http://www.scala-lang.org/docu/files/collections-api/collections.html. The collection library tries very hard to return the most specialized type based on the type of collection you start with.

It's true for map and flatMap and for loops.

The magic is explained in http://www.scala-lang.org/docu/files/collections-api/collections-impl.html, see Factoring out common operations.