Factoring out common operations

Contents

Factoring out common operations

The main design objectives of the collection library redesign were to have, at the same time, natural types and maximal sharing of implementation code. In particular, Scala's collections follow the "same-result-type" principle: wherever possible, a transformation method on a collection will yield a collection of the same type. For instance, the filter operation should yield, on every collection type, an instance of the same collection type. Applying filter on a List should give a List; applying it on a Map should give a Map, and so on. In the rest of this section, you will find out how this is achieved.

The Scala collection library avoids code duplication and achieves the "same-result-type" principle by using generic builders and traversals over collections in so-called implementation traits. These traits are named with a Like suffix; for instance, IndexedSeqLike is the implementation trait for IndexedSeq, and similarly, TraversableLike is the implementation trait for Traversable. Collection classes such as Traversable or IndexedSeq inherit all their concrete method implementations from these traits. Implementation traits have two type parameters instead of one for normal collections. They parameterize not only over the collection's element type, but also over the collection's representation type, i.e., the type of the underlying collection, such as Seq[I] or List[T]. For instance, here is the header of trait TraversableLike:

Taking filter as an example, this operation is defined once for all collection classes in the trait TraversableLike. An outline of the relevant code is shown in the above outline of class TraversableLike. The trait declares two abstract methods, newBuilder and foreach, which are implemented in concrete collection classes. The filter operation is implemented in the same way for all collections using these methods. It first constructs a new builder for the representation type Repr, using newBuilder. It then traverses all elements of the current collection, using foreach. If an element x satisfies the given predicate p (i.e., p(x) is true), it is added with the builder. Finally, the elements collected in the builder are returned as an instance of the Repr collection type by calling the builder's result method.

A bit more complicated is the map operation on collections. For instance, if f is a function from String to Int, and xs is a List[String], then xs map f should give a List[Int]. Likewise, if ys is an Array[String], then ys map f should give a Array[Int]. The problem is how to achieve that without duplicating the definition of the map method in lists and arrays. The newBuilder/foreach framework shown in class TraversableLike is not sufficient for this because it only allows creation of new instances of the same collection type whereas map needs an instance of the same collection type constructor, but possibly with a different element type.

What's more, even the result type constructor of a function like map might depend in non-trivial ways on the other argument types. Here is an example:

Note that map's result type depends on the type of function that's passed to it. If the result type of that function argument is again an Int, the result of map is a BitSet, but if the result type of the function argument is something else, the result of map is just a Set. You'll find out soon how this type-flexibility is achieved in Scala.

The problem with BitSet is not an isolated case. Here are two more interactions with the interpreter that both map a function over a map:

You might ask, why not restrict map so that it can always return the same kind of collection? For instance, on bit sets map could accept only Int-to-Int functions and on maps it could only accept pair-to-pair functions. Not only are such restrictions undesirable from an object-oriented modelling point of view, they are illegal because they would violate the Liskov substitution principle: A Map is an Iterable. So every operation that's legal on an Iterable must also be legal on a Map.

Scala solves this problem instead with overloading: not the simple form of overloading inherited by Java (that would not be flexible enough), but the more systematic form of overloading that's provided by implicit parameters.

The listing above shows trait TraversableLike's implementation of map. It's quite similar to the implementation of filter shown in class TraversableLike. The principal difference is that where filter used the newBuilder method, which is abstract in class TraversableLike, map uses a builder factory that's passed as an additional implicit parameter of type CanBuildFrom.

The listing above shows the definition of the trait CanBuildFrom, which represents builder factories. It has three type parameters: Elem indicates the element type of the collection to be built, To indicates the type of collection to build, and From indicates the type for which this builder factory applies. By defining the right implicit definitions of builder factories, you can tailor the right typing behavior as needed. Take class BitSet as an example. Its companion object would contain a builder factory of type CanBuildFrom[BitSet, Int, BitSet]. This means that when operating on a BitSet you can construct another BitSet provided the type of the collection to build is Int. If this is not the case, you can always fall back to a different implicit builder factory, this time implemented in mutable.Set's companion object. The type of this more general builder factory, where A is a generic type parameter, is:

So implicit resolution provides the correct static types for tricky collection operations such as map. But what about the dynamic types? Specifically, say you have a list value that has Iterable as its static type, and you map some function over that value:

Next: Integrating new collections

Factoring out common operations

Contents