Файл: Programming_in_Scala,_2nd_edition.pdf

class Queue[+T] private ( private[this] var leading: List[T], private[this] var trailing: List[T]

){

private def mirror() = if (leading.isEmpty) {

while (!trailing.isEmpty) {

leading = trailing.head :: leading trailing = trailing.tail

}

}

def head: T = { mirror() leading.head

}

def tail: Queue[T] = { mirror()

new Queue(leading.tail, trailing)

}

def enqueue[U >: T](x: U) =

new Queue[U](leading, x :: trailing)

}

Listing 19.10 · An optimized functional queue.

all, queues now contain two reassignable fields of the covariant parameter type T. Is this not a violation of the variance rules? It would be indeed, except for the detail that leading and trailing have a private[this] modifier and are thus declared to be object private.

As mentioned in Section 13.5, object private members can be accessed only from within the object in which they are defined. It turns out that accesses to variables from the same object in which they are defined do not cause problems with variance. The intuitive explanation is that, in order to construct a case where variance would lead to type errors, you need to have a reference to a containing object that has a statically weaker type than the type the object was defined with. For accesses to object private values, however,

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

this is impossible.

Scala’s variance checking rules contain a special case for object private definitions. Such definitions are omitted when it is checked that a type parameter with either a + or - annotation occurs only in positions that have the same variance classification. Therefore, the code in Listing 19.10 compiles without error. On the other hand, if you had left out the [this] qualifiers from the two private modifiers, you would see two type errors:

Queues.scala:1: error: covariant type T occurs in contravariant position in type List[T] of parameter of setter leading_=

class Queue[+T] private (private var leading: List[T],

ˆ

Queues.scala:1: error: covariant type T occurs in contravariant position in type List[T] of parameter of setter trailing_=

private var trailing: List[T]) {

ˆ

19.8 Upper bounds

In Listing 16.1 on page 360, we showed a merge sort function for lists that took a comparison function as a first argument and a list to sort as a second, curried argument. Another way you might want to organize such a sort function is by requiring the type of the list to mix in the Ordered trait. As mentioned in Section 12.4, by mixing Ordered into a class and implementing Ordered’s one abstract method, compare, you enable clients to compare instances of that class with <, >, <=, and >=. For example, Listing 19.11 shows Ordered being mixed into a Person class. As a result, you can compare two persons like this:

scala> val robert = new Person("Robert", "Jones") robert: Person = Robert Jones

scala> val sally = new Person("Sally", "Smith") sally: Person = Sally Smith

scala> robert < sally res0: Boolean = true

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

class Person(val firstName: String, val lastName: String) extends Ordered[Person] {

def compare(that: Person) = { val lastNameComparison =

lastName.compareToIgnoreCase(that.lastName) if (lastNameComparison != 0)

lastNameComparison else

firstName.compareToIgnoreCase(that.firstName)

}

override def toString = firstName +" "+ lastName

}

Listing 19.11 · A Person class that mixes in the Ordered trait.

def orderedMergeSort[T <: Ordered[T]](xs: List[T]): List[T] = { def merge(xs: List[T], ys: List[T]): List[T] =

(xs, ys) match { case (Nil, _) => ys case (_, Nil) => xs

case (x :: xs1, y :: ys1) =>

if (x < y) x :: merge(xs1, ys) else y :: merge(xs, ys1)

}

val n = xs.length / 2 if (n == 0) xs

else {

val (ys, zs) = xs splitAt n merge(orderedMergeSort(ys), orderedMergeSort(zs))

}

}

Listing 19.12 · A merge sort function with an upper bound.

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

To require that the type of the list passed to your new sort function mixes in Ordered, you need to use an upper bound. An upper bound is specified similar to a lower bound, except instead of the >: symbol used for lower bounds, you use a <: symbol, as shown in Listing 19.12. With the “T <: Ordered[T]” syntax, you indicate that the type parameter, T, has an upper bound, Ordered[T]. This means that the element type of the list passed to orderedMergeSort must be a subtype of Ordered. Thus, you could pass a List[Person] to orderedMergeSort, because Person mixes in Ordered. For example, consider this list:

scala> val people = List(

new Person("Larry", "Wall"),

new Person("Anders", "Hejlsberg"), new Person("Guido", "van Rossum"), new Person("Alan", "Kay"),

new Person("Yukihiro", "Matsumoto")

)

people: List[Person] = List(Larry Wall, Anders Hejlsberg, Guido van Rossum, Alan Kay, Yukihiro Matsumoto)

Because the element type of this list, Person, mixes in (and is therefore a subtype of) Ordered[People], you can pass the list to orderedMergeSort:

scala> val sortedPeople = orderedMergeSort(people) sortedPeople: List[Person] = List(Anders Hejlsberg, Alan Kay,

Yukihiro Matsumoto, Guido van Rossum, Larry Wall)

Now, although the sort function shown in Listing 19.12 serves as a useful illustration of upper bounds, it isn’t actually the most general way in Scala to design a sort function that takes advantage of the Ordered trait. For example, you couldn’t use the orderedMergeSort function to sort a list of integers, because class Int is not a subtype of Ordered[Int]:

scala> val wontCompile = orderedMergeSort(List(3, 2, 1)) <console>:5: error: inferred type arguments [Int] do

not conform to method orderedMergeSort's type parameter bounds [T <: Ordered[T]]

val wontCompile = orderedMergeSort(List(3, 2, 1))

ˆ

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