Файл: Programming_in_Scala,_2nd_edition.pdf

class Queue[+T] (private val leading: List[T], private val trailing: List[T] ) {

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

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

}

Listing 19.6 · A type parameter with a lower bound.

The new definition gives enqueue a type parameter U, and with the syntax, “U >: T”, defines T as the lower bound for U. As a result, U is required to be a supertype of T.1 The parameter to enqueue is now of type U instead of type T, and the return value of the method is now Queue[U] instead of Queue[T].

As an example, suppose there is a class Fruit with two subclasses, Apple and Orange. With the new definition of class Queue, it is possible to append an Orange to a Queue[Apple]. The result will be a Queue[Fruit].

This revised definition of enqueue is type correct. Intuitively, if T is a more specific type than expected (for example, Apple instead of Fruit), a call to enqueue will still work, because U (Fruit) will still be a supertype of

T (Apple).2

The new definition of enqueue is arguably better than the old, because it is more general. Unlike the old version, the new definition allows you to append an arbitrary supertype U of the queue element type T. The result is then a Queue[U]. Together with queue covariance, this gives the right kind of flexibility for modeling queues of different element types in a natural way.

This shows that variance annotations and lower bounds play well together. They are a good example of type-driven design, where the types of an interface guide its detailed design and implementation. In the case of queues, you would probably not have thought of the refined implementation of enqueue with a lower bound, but you might have decided to make queues covariant. In that case, the compiler would have pointed out the variance error for enqueue. Correcting the variance error by adding a lower bound makes enqueue more general and queues as a whole more usable.

1Supertype and subtype relationships are reflexive, which means a type is both a supertype and a subtype of itself. Even though T is a lower bound for U, you could still pass in a T to enqueue.

2Technically, what happens is a flip occurs for lower bounds. The type parameter U is in a negative position (1 flip), while the lower bound (>: T) is in a positive position (2 flips).

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

This observation is also the main reason that Scala prefers declarationsite variance over use-site variance as it is found in Java’s wildcards. With use-site variance, you are on your own designing a class. It will be the clients of the class that need to put in the wildcards, and if they get it wrong, some important instance methods will no longer be applicable. Variance being a tricky business, users usually get it wrong, and they come away thinking that wildcards and generics are overly complicated. With definition-side variance, you express your intent to the compiler, and the compiler will double check that the methods you want available will indeed be available.

19.6 Contravariance

So far in this chapter, all examples you’ve seen were either covariant or nonvariant. But there are also cases where contravariance is natural. For instance, consider the trait of output channels shown in Listing 19.7:

trait OutputChannel[-T] { def write(x: T)

}

Listing 19.7 · A contravariant output channel.

Here, OutputChannel is defined to be contravariant in T. So an output channel of AnyRefs, say, is a subtype of an output channel of Strings. Although it may seem non-intuitive, it actually makes sense. To see why, consider what you can do with an OutputChannel[String]. The only supported operation is writing a String to it. The same operation can also be done on an OutputChannel[AnyRef]. So it is safe to substitute an

OutputChannel[AnyRef] for an OutputChannel[String]. By contrast, it would not be safe to substitute an OutputChannel[String] where an OutputChannel[AnyRef] is required. After all, you can send any object to an OutputChannel[AnyRef], whereas an OutputChannel[String] requires that the written values are all strings.

This reasoning points to a general principle in type system design: it is safe to assume that a type T is a subtype of a type U if you can substitute a value of type T wherever a value of type U is required. This is called the Liskov Substitution Principle. The principle holds if T supports the same operations as U and all of T’s operations require less and provide more

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

trait Function1[-S, +T] { def apply(x: S): T

}

Listing 19.8 · Covariance and contravariance of Function1s.

than the corresponding operations in U. In the case of output channels, an

OutputChannel[AnyRef] can be a subtype of an OutputChannel[String] because the two support the same write operation, and this operation requires less in OutputChannel[AnyRef] than in OutputChannel[String]. “Less” means the argument is only required to be an AnyRef in the first case, whereas it is required to be a String in the second case.

Sometimes covariance and contravariance are mixed in the same type. A prominent example is Scala’s function traits. For instance, whenever you write the function type A => B, Scala expands this to Function1[A, B]. The definition of Function1 in the standard library uses both covariance and contravariance: the Function1 trait is contravariant in the function argument type S and covariant in the result type T, as shown in Listing 19.8. This satisfies the Liskov substitution principle, because arguments are something that’s required, whereas results are something that’s provided.

As an example, consider the application shown in Listing 19.9. In this example, class Publication contains one parametric field, title, of type String. Class Book extends Publication and forwards its string title parameter to the constructor of its superclass. The Library singleton object defines a set of books and a method printBookList, which takes a function, named info, of type Book => AnyRef. In other words, the type of the lone parameter to printBookList is a function that takes one Book argument and returns an AnyRef. The Customer application defines a method, getTitle, which takes a Publication as its lone parameter and returns a String, the title of the passed Publication.

Now take a look at the last line in Customer. This line invokes Library’s printBookList method and passes getTitle, wrapped in a function value:

Library.printBookList(getTitle)

This line of code type checks even though String, the function’s result type, is a subtype of AnyRef, the result type of printBookList’s info parameter. This code passes the compiler because function result types are de-

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

class Publication(val title: String)

class Book(title: String) extends Publication(title)

object Library {

val books: Set[Book] = Set(

new Book("Programming in Scala"), new Book("Walden")

)

def printBookList(info: Book => AnyRef) { for (book <- books) println(info(book))

}

}

object Customer extends Application {

def getTitle(p: Publication): String = p.title Library.printBookList(getTitle)

}

Listing 19.9 · Demonstration of function type parameter variance.

clared to be covariant (the +T in Listing 19.8). If you look inside the body of printBookList, you can get a glimpse of why this makes sense.

The printBookList method iterates through its book list, and invokes the passed function on each book. It passes the AnyRef result returned by info to println, which invokes toString on it and prints the result. This activity will work with String as well as any other subclass of AnyRef, which is what covariance of function result types means.

Now consider the parameter type of the function being passed to the printBookList method. Although printBookList’s parameter type is declared as Book, the getTitle we’re passing in takes a Publication, a supertype of Book. The reason this works is that since printBookList’s parameter type is Book, the body of the printBookList method will only be allowed to pass a Book into the function. And because getTitle’s parameter type is Publication, the body of that function will only be able to access on its parameter, p, members that are declared in class Publication. Because any method declared in Publication is also available on its subclass Book, everything should work, which is what contravariance of function parameter

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

Figure 19.1 · Covariance and contravariance in function type parameters.

types means. You can see all this graphically in Figure 19.1.

The code in Listing 19.9 compiles because Publication => String is a subtype of Book => AnyRef, as shown in the center of the Figure 19.1. Because the result type of a Function1 is defined as covariant, the inheritance relationship of the two result types, shown at the right of the diagram, is in the same direction as that of the two functions shown in the center. By contrast, because the parameter type of a Function1 is defined as contravariant, the inheritance relationship of the two parameter types, shown at the left of the diagram, is in the opposite direction as that of the two functions.

19.7 Object private data

The Queue class seen so far has a problem in that the mirror operation might repeatedly copy the trailing into the leading list if head is called several times in a row on a list where leading is empty. The wasteful copying could be avoided by adding some judicious side effects. Listing 19.10 presents a new implementation of Queue, which performs at most one trailing to leading adjustment for any sequence of head operations.

What’s different with respect to the previous version is that now leading and trailing are reassignable variables, and mirror performs the reverse copy from trailing to leading as a side-effect on the current queue instead of returning a new queue. This side-effect is purely internal to the implementation of the Queue operation; since leading and trailing are private variables, the effect is not visible to clients of Queue. So by the terminology established in Chapter 18, the new version of Queue still defines purely functional objects, in spite of the fact that they now contain reassignable fields.

You might wonder whether this code passes the Scala type checker. After

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