Файл: Programming_in_Scala,_2nd_edition.pdf

it is invertible. The second function, however, maps the key/value pair to an integer, namely its value component. In that case, we cannot form a Map from the results, but we still can form an Iterable, a supertrait of 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 modeling 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.

def map[B, That](p: Elem => B)

(implicit bf: CanBuildFrom[B, That, This]): That = { val b = bf(this)

for (x <- this) b += f(x) b.result

}

Listing 25.3 · Implementation of map in TraversableLike.

Listing 25.3 shows trait TraversableLike’s implementation of map. It’s quite similar to the implementation of filter shown in Listing 25.2. 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.

package scala.collection.generic

trait CanBuildFrom[-From, -Elem, +To] { // Creates a new builder

def apply(from: From): Builder[Elem, To]

}

Listing 25.4 · The CanBuildFrom trait.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Listing 25.4 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:

CanBuildFrom[Set[_], A, Set[A]]

This means that when operating on an arbitrary Set (expressed by the existential type Set[_]) you can build a Set again, no matter what the element type A is. Given these two implicit instances of CanBuildFrom, you can then rely on Scala’s rules for implicit resolution to pick the one that’s appropriate and maximally specific.

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:

scala> val xs: Iterable[Int] = List(1, 2, 3) xs: Iterable[Int] = List(1, 2, 3)

scala> val ys = xs map (x => x * x) ys: Iterable[Int] = List(1, 4, 9)

The static type of ys above is Iterable, as expected. But its dynamic type is (and should be) still List! This behavior is achieved by one more indirection. The apply method in CanBuildFrom is passed the source collection as argument. Most builder factories for generic traversables (in fact all except builder factories for leaf classes) forward the call to a method genericBuilder of a collection. The genericBuilder method in turn calls the builder that belongs to the collection in which it is defined. So Scala uses static implicit resolution to resolve constraints on the types of

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

map, and virtual dispatch to pick the best dynamic type that corresponds to these constraints.

abstract class Base

case object A extends Base case object T extends Base case object G extends Base case object U extends Base

object Base {

val fromInt: Int => Base = Array(A, T, G, U)

val toInt: Base => Int = Map(A -> 0, T -> 1, G -> 2, U -> 3)

}

Listing 25.5 · RNA Bases.

25.3 Integrating new collections

What needs to be done if you want to integrate a new collection class, so that it can profit from all predefined operations at the right types? In this section you’ll be walked through two examples that do this.

Integrating sequences

Say you want to create a new sequence type for RNA strands, which are sequences of bases A (adenine), T (thymine), G (guanine), and U (uracil). The definitions for bases are easily set up as shown in Listing 25.5.

Every base is defined as a case object that inherits from a common abstract class Base. The Base class has a companion object that defines two functions that map between bases and the integers 0 to 3. You can see in the examples two different ways to use collections to implement these functions. The toInt function is implemented as a Map from Base values to integers. The reverse function, fromInt, is implemented as an array. This makes use of the fact that both maps and arrays are functions because they inherit from the Function1 trait.

The next task is to define a class for strands of RNA. Conceptually, a strand of RNA is simply a Seq[Base]. However, RNA strands can get quite long, so it makes sense to invest some work in a compact representation.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

import collection.IndexedSeqLike

import collection.mutable.{Builder, ArrayBuffer} import collection.generic.CanBuildFrom

final class RNA1 private (val groups: Array[Int], val length: Int) extends IndexedSeq[Base] {

import RNA1._

def apply(idx: Int): Base = { if (idx < 0 || length <= idx)

throw new IndexOutOfBoundsException Base.fromInt(groups(idx / N) >> (idx % N * S) & M)

}

}

object RNA1 {

//Number of bits necessary to represent group private val S = 2

//Number of groups that fit in an Int

private val N = 32 / S

// Bitmask to isolate a group private val M = (1 << S) - 1

def fromSeq(buf: Seq[Base]): RNA1 = {

val groups = new Array[Int]((buf.length + N - 1) / N) for (i <- 0 until buf.length)

groups(i / N) |= Base.toInt(buf(i)) << (i new RNA1(groups, buf.length)

}

def apply(bases: Base*) = fromSeq(bases)

}

Listing 25.6 · RNA strands class, first version.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Because there are only four bases, a base can be identified with two bits, and you can therefore store sixteen bases as two-bit values in an integer. The idea, then, is to construct a specialized subclass of Seq[Base], which uses this packed representation.

Listing 25.6 presents the first version of this class. It will be refined later. The class RNA1 has a constructor that takes an array of Ints as its first argument. This array contains the packed RNA data, with sixteen bases in each element, except for the last array element, which might be partially filled. The second argument, length, specifies the total number of bases on the array (and in the sequence). Class RNA1 extends IndexedSeq[Base]. Trait

IndexedSeq, which comes from package scala.collection.immutable, defines two abstract methods, length and apply. These need to be implemented in concrete subclasses. Class RNA1 implements length automatically by defining a parametric field (described in Section 10.6) of the same name. It implements the indexing method apply with the code given in Listing 25.6. Essentially, apply first extracts an integer value from the groups array, then extracts the correct two-bit number from that integer using right shift (>>) and mask (&). The private constants S, N, and M come from the RNA1 companion object. S specifies the size of each packet (i.e. two); N specifies the number of two-bit packets per integer; and M is a bit mask that isolates the lowest S bits in a word.

Note that the constructor of class RNA1 is private. This means that clients cannot create RNA1 sequences by calling new, which makes sense, because it hides the representation of RNA1 sequences in terms of packed arrays from the user. If clients cannot see what the representation details of RNA sequences are, it becomes possible to change these representation details at any point in the future without affecting client code. In other words, this design achieves a good decoupling of the interface of RNA sequences and its implementation. However, if constructing an RNA sequence with new is impossible, there must be some other way to create new RNA sequences, else the whole class would be rather useless. In fact there are two alternatives for RNA sequence creation, both provided by the RNA1 companion object. The first way is method fromSeq, which converts a given sequence of bases (i.e., a value of type Seq[Base]) into an instance of class RNA1. The fromSeq method does this by packing all the bases contained in its argument sequence into an array, then calling RNA1’s private constructor with that array and the length of the original sequence as arguments. This makes use of the fact that a private constructor of a class is visible in the class’s companion object.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index