Using Implicits to Select Types

Scala 2.8's collection revision is doing interesting things. The most obvious one will be the methods revision. One thing that shouldn't be all that obvious, though, is how much code will be shared, and how that shared code will still look like it was specific to a class.

I'll quote here a couple of examples from the Scala 2.8 Collection's Whitepaper (pdf at the bottom):

scala> "abc" map (x => (x + 1).toChar)
res1: scala.runtime.RichString = bcd

scala> "abc" map (x => (x + 1))
res2: scala.collection.immutable.Vector[Int] = Vector(98, 99, 100)

scala> Map("a" -> 1, "b" -> 2) map { case (x, y) => (y, x) }
res3: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> a, 2 -> b)

scala> Map("a" -> 1, "b" -> 2) map { case (x, y) => y }
res4: scala.collection.immutable.Iterable[Int] = List(1, 2)

Now, this "map" method is inherited from a common trait, and yet it knows when the result of a map over a RichString is a RichString, when the result of a map over a Map is a Map, and when it's not. How can it be?

The answer is implicit parameters. One thing about implicits, is that a more specific implicit has preference over a more generic one. Take a look at this example:

scala> abstract class X[T] { def id : Unit }
defined class X

scala> implicit def a[T] = new X[T] { def id = println("generic") }
a: [T]X[T]

scala> implicit def b = new X[Int] { def id = println("Int") }
b: X[Int]

scala> def f[T](a : T)(implicit g : X[T]) = g.id
f: [T](T)(implicit X[T])Unit

scala> f(5)
Int

scala> f('c')
generic

Both "a" and "b" have the correct type, X[T]. The second definition, though, will return X[Int], which is more specific than X[T], which the first definition returns. So, whenever X[Int] is required, "b" will take precedence over "a". Naturally, if some other type of X is required, "b" won't be used at all.

This is how map can do its trick. To compose the result, it uses methods from the class Builder[-Elem, +To]. Such a build will create a collection of type To from elements of type Elem. Now, this is not enough to solve map's problem. For example, I want a RichString as result, if I'm doing a map over a RichString, but not if I'm mapping over a List of Chars. See the two examples below:

scala> "abc" map (x => (x + 1).toChar)
res1: scala.runtime.RichString = bcd

scala> List('a', 'b', 'c') map (x => (x + 1).toChar)
res11: List[Char] = List(b, c, d)

So, for methods with more complex semantics, like map, we need something else which can produce the correct Builder. For that, the trait BuilderFactory[Elem,

+To, From] exists. BuilderFactory will produce a Builder for a method which takes a collection of type From, and uses elements of type Elem to produce a collection of type To.

Now, the more generic implicit for a BuilderFactory is BuilderFactory[A, Iterable[A], Iterable[_]], which should be pretty obvious. Other implicits exists, though, such as BuilderFactory[Char, RichString, RichString]. Now, look at map's declaration:

def map[B, That](p: Elem => B)(implicit bf: BuilderFactory[B, That, This]): That

So, when you do "abc".map( x => (x + 1).toChar), the compiler knows that "B" is Char (the result of the function being mapped). "This" is known to be RichString, from the definition of class RichString itself. Now, given that "B" = Char and "This" = RichString, then BuilderFactory[Char, RichString, RichString] is a more specific match than the other implicit definitions. And, because it gets used, "That" gets defined to be RichString also, thus defining the result type for that map.

The cleverness of it is to use implicits to define unknown type parameters as a function of known type parameters. This is can be a very useful pattern for those who want to take maximum advantage of static type checking.