Typeclass in Scala Libraries and the Compiler

Typeclass in Scala is a design pattern that provides ad hoc polymorphism. It is a way of associating a common abstraction to a type such that different types can be applied to polymorphic functions. The benefit of typeclass is that inheritance or subtyping can be avoided, and more importantly, to address the retroactive extension of a program. Many important concepts, such as Functor, Monoid, Monad, etc, are applications of type class.

The use and applications of type classes were advertised in Odersky's Type Classes as Objects and Implicits, and have been discussed in length. Assuming that the readers are familiar with the basic form of typeclass, this article discusses this design pattern in greater detail by illustrating the extensive use of type classes in the Scala library itself and explains how the Scala compiler interprets this design concept.

To use readily available type classes in a Scala library, we not only need to understand the typeclass definition, but also know what implicits are available based on implicit resolution rules. In this article, we discuss these type classes in detail and explain how the compiler works with these type classes. We hope this can help the readers to write more efficient Scala code use this powerful pattern in their design.

This is a series of discussion. In the part one of this series, we will discuss the TypeTags typeclass and the CanBuildFrom typeclass.

TypeTags Typeclass

As with other JVM languages, Scala types are erased at compile time through type erasure. With Scala 2.10, Scala introduced TypeTags, which carry type information at compile time to runtime. There are three types of TypeTags: ClassTag, TypeTag, and TypeTag #WeakTypeTag.

The ClassTag typeclass is a partial type descriptor that contains only erased type information. An instance of ClassTag is requested to the compiler by providing the ClassTag in the implicit parameter list with an abstract type T. Let’s see how the compiler works with this type class.

def paramInfo[T](x: T)(implicit tag: ClassTag[T]): Unit = {    println (tag.runtimeClass)  }

The implicit parameter instructs the compiler to do the implicit search; the compiler will provide an appropriate object for the implicit parameter based on its type.

We call this function from the client side with a concrete type:

paramInfo(List(1,2,3))

The compiler will provide an instance of ClassTag for the concrete type, in our case, an immutable List:

class scala.collection.immutable.List

Note that information about the type parameter [Int] was not present in ClassTag.

Type erasure with Array is special — arrays are not subject to type erasure. In the following code, ClassTag contains information of the type parameter [String], as the erased type information is of the type parameter:

paramInfo(Array("aaa", "bbb"))

The compiler provides the following encoding:

ClassTag.apply(scala.runtime.ScalaRunTime.arrayClass(classOf[java.lang.String])

Here, the erased type is the type parameter [String] instead of the container Array.

In some cases, ClassTag implicit is not directly referenced but is provided for availability of other type classes. In such cases, context bound can be used so that the encoding can be more concise:

def paramInfo[T :ClassTag](x: T)  =…

Unlike ClassTag, which only carries erased type information, the TypeTag typeclass is an object that guarantees complete type information from compile time to runtime — it is the link to universe, the interface to runtime reflection. To access TypeTag, import the runtime universe:

import scala.reflect.runtime.universe._

Meanwhile, request the implicit value of TypeTag by adding it to the implicit parameter list; The Scala compiler will find an instance of TypeTag, and the type information can be accessed:

def paramInfo[T](x: T)(implicit tag: TypeTag[T]): Unit = {    
  val targs = tag.tpe match { case TypeRef(_, _, args) => args }    
  println(s"type of $x has type arguments $targs")
}

As for the client side, we call this function:

paramInfo(List("aa", "bb", "cc"))

We can find all the type information, including type parameters:

type of List(aa, bb, cc) has type arguments List(java.lang.String)

The compiler is more involving to provide complete type information by creating synthetic classes, and reifying through universe and mirrors.

If the type parameters are abstract types, the WeakTypeTag typeclass makes a best effort to reference to concrete types, i.e., TypeTag will be used if type conformation is available for the referenced type arguments. Otherwise, it will contain a reference to the abstract type. Thus, the information obtained from the WeakTypeTag typeclass can be partially abstract.

def weakParamInfo[T](x: T)(implicit tag: WeakTypeTag[T]): Unit = {
  val targs = tag.tpe match { case TypeRef(_, _, args) => args }
  println(s"weakTypeTag: type of $x has type arguments $targs")
}

At the client side...

paramInfo4

...will return:

weakTypeTag: type of List () has type arguments List(T)

Where T is the type parameter introduced in the function paramInfo4.

CanBuildFrom Typeclass

Say you are given a collection of a certain type and you are to create a new collection of this type. This task involves the following type information:

• The type of the collection to be transferred from.
• The type of the collection to be transferred to.
• The type of the items in the collection.

In the Scala library, the CanBuildFrom typeclass is doing exactly this job:

trait CanBuildFrom[-From, -Elem, +To] { …}

The CanBuildFrom typeclass is parametrized with three type parameters: the From collection type, the To collection type, and the type of the items to be built. Given a properly typed instance of CanBuildFrom, a call to apply() will return a Builder factory of the To collection so that you can add elements and obtain this collection.

CanBuildFrom implicit is the link in Scala transformers. Transformer is a method that takes collections of objects and produces another collection as a result. For instance, the following code...

List(“1”, “2”, “3”) map (x => x.toInt)

...transforms a List of strings to a list of Int. map() defined in the trait TravasibleLike and mixin to List. The implicit parameter is a typed CanBuildFrom instance that informs the compiler to resolve the implicit objects based on the rules of implicit resolution. In List, map() has following signature:

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[List[A], B, That]): That

In our example, A is of type String, From is of type List[String], B is of type Int, and To is of type List[Int]; thus, the compiler is informed to look for an implicit instance of CanBuildFrom(List[String], Int, List[Int]) typeclass. This can be found in the companion object of our List:

implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, List[A]] = …

Here we need to introduce breakOut, an instance of the CanBuildFrom typeclass in Scala library. Let’s see how it works to simplify the transformers in Scala.

Take an example in this Scala document:

val map : Map[Int,String] = List("London", "Paris").map(x => (x.length, x))(breakOut)

This function is to convert a list of String to a Map of tuples. If we do not provide the breakOut instance, the Scala compiler is not able to find an implicit instance of CanBuildFrom that has the following type parameters:

CanBuildFrom[List[String], (Int, String), Map[Int, String])

An option is to invoke another transformer, toMap:

val map : Map[Int,String] = List("London", "Paris").map(x => (x.length, x)).toMap

Where toMap is defined as:

def toMap[T, U](implicit ev: A <:< (T, U)): Map[T, U]

Here, another typeclass is in play. <:<[A, (T, U)], or its syntactic sugar, A <:< (T, U), defined in Predef, is provided in the implicit parameter list. This is a conformance typeclass that helps the compiler report errors at compiler time: type A conforms to type (T,U), otherwise an error is reported.

implicit def $conforms[A]: A <:< A = …

The reason that <:<[A, A] conforms <:<[-From, +To] is that from the variance, -From means that A is a supertype of type To, and +To means that A is subtype of type From, so To <: A <: From, so To is a supertype of From, and this is the only implicit definition the compiler can find. A is a supertype of A. The evidence is not used at all in the method but is essential in ensuring type conformance.

This approach is all good except for inefficiency: There are two transformers are involved, one to convert each element to a Tuple and produce an intermediary List, the other to convert the intermediary List to a Map.

Here, breakOut can be used to avoid creating the intermediary List. breakOut is an instance of CanBuildFrom defined as:

def breakOut[From, T, To](implicit b: CanBuildFrom[Nothing, T, To]):CanBuildFrom[From, T, To] = …

By providing breakOut as an explicit parameter to map, the compiler is informed to use this incidence, and in turn, to find the required CanBuildFrom instance through another implicit lookup for breakOut. Let’s come back to this line:

val map : Map[Int,String] = List("London", "Paris").map(x => (x.length, x))(breakOut)

Here, From is of type List[String], T is of type (Int, String), and To is of type Map[Int, String]. As CanBuildFrom’s first type parameter is contra-variant, and Nothing is a bottom class, any type is legitimate in place of the Nothing type. By looking at the Map companion object, such CanBuildFrom implicit is available:

implicit def canBuildFrom[K, V]: CanBuildFrom[Coll, (K, V), Map[K, V]] = new MapCanBuildFrom[K, V]

In the end, the creation of an intermediary List is avoided as the MapCanBuildFrom factory will create a Map directly.