Файл: Programming_in_Scala,_2nd_edition.pdf

class Queue[T](

private val leading: List[T], private val trailing: List[T]

){

private def mirror = if (leading.isEmpty)

new Queue(trailing.reverse, Nil) else

this

def head = mirror.leading.head

def tail = {

val q = mirror

new Queue(q.leading.tail, q.trailing)

}

def enqueue(x: T) =

new Queue(leading, x :: trailing)

}

Listing 19.1 · A basic functional queue.

of mirror, which means a constant amount of work. Assuming that head, tail, and enqueue operations appear with about the same frequency, the amortized complexity is hence constant for each operation. So functional queues are asymptotically just as efficient as mutable ones.

Now, there are some caveats that need to be attached to this argument. First, the discussion only was about asymptotic behavior, the constant factors might well be somewhat different. Second, the argument rested on the fact that head, tail and enqueue are called with about the same frequency. If head is called much more often than the other two operations, the argument is not valid, as each call to head might involve a costly re-organization of the list with mirror. The second caveat can be avoided; it is possible to design functional queues so that in a sequence of successive head operations only the first one might require a re-organization. You will find out at the end of this chapter how this is done.

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

19.2 Information hiding

The implementation of Queue shown in Listing 19.1 is now quite good with regards to efficiency. You might object, though, that this efficiency is paid for by exposing a needlessly detailed implementation. The Queue constructor, which is globally accessible, takes two lists as parameters, where one is reversed—hardly an intuitive representation of a queue. What’s needed is a way to hide this constructor from client code. In this section, we’ll show you some ways to accomplish this in Scala.

Private constructors and factory methods

In Java, you can hide a constructor by making it private. In Scala, the primary constructor does not have an explicit definition; it is defined implicitly by the class parameters and body. Nevertheless, it is still possible to hide the primary constructor by adding a private modifier in front of the class parameter list, as shown in Listing 19.2:

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

)

Listing 19.2 · Hiding a primary constructor by making it private.

The private modifier between the class name and its parameters indicates that the constructor of Queue is private: it can be accessed only from within the class itself and its companion object. The class name Queue is still public, so you can use it as a type, but you cannot call its constructor:

scala> new Queue(List(1, 2), List(3))

<console>:6: error: constructor Queue cannot be accessed in object $iw

new Queue(List(1, 2), List(3))

ˆ

Now that the primary constructor of class Queue can no longer be called from client code, there needs to be some other way to create new queues. One possibility is to add an auxiliary constructor, like this:

def this() = this(Nil, Nil)

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

The auxiliary constructor shown in the previous example builds an empty queue. As a refinement, the auxiliary constructor could take a list of initial queue elements:

def this(elems: T*) = this(elems.toList, Nil)

Recall that T* is the notation for repeated parameters, as described in Section 8.8.

Another possibility is to add a factory method that builds a queue from such a sequence of initial elements. A neat way to do this is to define an object Queue that has the same name as the class being defined and contains an apply method, as shown in Listing 19.3:

object Queue {

// constructs a queue with initial elements ‘xs’ def apply[T](xs: T*) = new Queue[T](xs.toList, Nil)

}

Listing 19.3 · An apply factory method in a companion object.

By placing this object in the same source file as class Queue, you make the object a companion object of the class. You saw in Section 13.5 that a companion object has the same access rights as its class. Because of this, the apply method in object Queue can create a new Queue object, even though the constructor of class Queue is private.

Note that, because the factory method is called apply, clients can create queues with an expression such as Queue(1, 2, 3). This expression expands to Queue.apply(1, 2, 3) since Queue is an object instead of a function. As a result, Queue looks to clients as if it was a globally defined factory method. In reality, Scala has no globally visible methods; every method must be contained in an object or a class. However, using methods named apply inside global objects, you can support usage patterns that look like invocations of global methods.

An alternative: private classes

Private constructors and private members are one way to hide the initialization and representation of a class. Another, more radical way is to hide the class itself and only export a trait that reveals the public interface of the

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

object Queue {

def apply[T](xs: T*): Queue[T] = new QueueImpl[T](xs.toList, Nil)

private class QueueImpl[T]( private val leading: List[T], private val trailing: List[T]

)extends Queue[T] {

def mirror =

if (leading.isEmpty)

new QueueImpl(trailing.reverse, Nil) else

this

def head: T = mirror.leading.head

def tail: QueueImpl[T] = { val q = mirror

new QueueImpl(q.leading.tail, q.trailing)

}

def enqueue(x: T) =

new QueueImpl(leading, x :: trailing)

}

}

Listing 19.4 · Type abstraction for functional queues.

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

class. The code in Listing 19.4 implements this design. There’s a trait Queue, which declares the methods head, tail, and enqueue. All three methods are implemented in a subclass QueueImpl, which is itself a private inner class of object Queue. This exposes to clients the same information as before, but using a different technique. Instead of hiding individual constructors and methods, this version hides the whole implementation class.

19.3 Variance annotations

Queue, as defined in Listing 19.4, is a trait, but not a type. Queue is not a type because it takes a type parameter. As a result, you cannot create variables of type Queue:

scala> def doesNotCompile(q: Queue) {}

<console>:5: error: trait Queue takes type parameters def doesNotCompile(q: Queue) {}

ˆ

Instead, trait Queue enables you to specify parameterized types, such as

Queue[String], Queue[Int], or Queue[AnyRef]:

scala> def doesCompile(q: Queue[AnyRef]) {} doesCompile: (Queue[AnyRef])Unit

Thus, Queue is a trait, and Queue[String] is a type. Queue is also called a type constructor, because with it you can construct a type by specifying a type parameter. (This is analogous to constructing an object instance with a plain-old constructor by specifying a value parameter.) The type constructor Queue “generates” a family of types, which includes Queue[Int],

Queue[String], and Queue[AnyRef].

You can also say that Queue is a generic trait. (Classes and traits that take type parameters are “generic,” but the types they generate are “parameterized,” not generic.) The term “generic” means that you are defining many specific types with one generically written class or trait. For example, trait Queue in Listing 19.4 defines a generic queue. Queue[Int] and Queue[String], etc., would be the specific queues.

The combination of type parameters and subtyping poses some interesting questions. For example, are there any special subtyping relationships between members of the family of types generated by Queue[T]? More specifically, should a Queue[String] be considered a subtype of Queue[AnyRef]?

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