「Example8.1」の編集履歴（バックアップ）一覧に戻る
Now that we know how to make classes generic it is natural to generalize some of the earlier classes we have written. For instance class IntSet could be generalized to sets with arbitrary element types. Let’s try. The abstract class for generic sets is easily written.
abstract class Set[A] {
def incl(x: A): Set[A]
def contains(x: A): Boolean
}
However, if we still want to implement sets as binary search trees, we encounter a problem. The contains and incl methods both compare elements using methods < and >. For IntSet this was OK, since type Int has these two methods. But for an arbitrary type parameter a, we cannot guarantee this. Therefore, the previous implementation of, say, contains would generate a compiler error.
def contains(x: Int): Boolean =
if (x < elem) left contains x
^ < not a member of type A.
One way to solve the problem is to restrict the legal types that can be substituted for type A to only those types that contain methods < and > of the correct types. There is a trait Ordered[A] in the standard class library Scala which represents values which are comparable (via < and >) to values of type A. This trait is defined as follows:
/** A class for totally ordered data. */
trait Ordered[A] {
/** Result of comparing ‘this’ with operand ‘that’.
* returns ‘x’ where
* x < 0 iff this < that
* x == 0 iff this == that
* x > 0 iff this > that
*/
def compare(that: A): Int
def < (that: A): Boolean = (this compare that) < 0
def > (that: A): Boolean = (this compare that) > 0
def <= (that: A): Boolean = (this compare that) <= 0
def >= (that: A): Boolean = (this compare that) >= 0
def compareTo(that: A): Int = compare(that)
}
We can enforce the comparability of a type by demanding that the type is a subtype of Ordered. This is done by giving an upper bound to the type parameter of Set:
trait Set[A <: Ordered[A]] {
def incl(x: A): Set[A]
def contains(x: A): Boolean
}
The parameter declaration A <: Ordered[A] introduces A as a type parameter which must be a subtype of Ordered[A], i.e. its values must be comparable to values of the same type.
With this restriction, we can now implement the rest of the generic set abstraction as we did in the case of IntSets before.
class EmptySet[A <: Ordered[A]] extends Set[A] {
def contains(x: A): Boolean = false
def incl(x: A): Set[A] = new NonEmptySet(x, new EmptySet[A], new EmptySet[A])
}
class NonEmptySet[A <: Ordered[A]]
(elem: A, left: Set[A], right: Set[A]) extends Set[A] {
def contains(x: A): Boolean =
if (x < elem) left contains x
else if (x > elem) right contains x
else true
def incl(x: A): Set[A] =
if (x < elem) new NonEmptySet(elem, left incl x, right)
else if (x > elem) new NonEmptySet(elem, left, right incl x)
else this
}
Note that we have left out the type argument in the object creations new NonEmptySet(...). In the same way as for polymorphic methods, missing type arguments in constructor calls are inferred from value arguments and/or the expected result type.
Here is an example that uses the generic set abstraction. Let’s first create a subclass of Ordered, like this:
case class Num(value: Double) extends Ordered[Num] {
def compare(that: Num): Int =
if (this.value < that.value) -1
else if (this.value > that.value) 1
else 0
}
Then:
val s = new EmptySet[Num].incl(Num(1.0)).incl(Num(2.0)) s.contains(Num(1.5))
This is OK, as type Num implements the trait Ordered[Num]. However, the following example is in error.
val s = new EmptySet[java.io.File]
^ java.io.File does not conform to type
parameter bound Ordered[java.io.File].
One probem with type parameter bounds is that they require forethought: if we had not declared Num a subclass of Ordered, we would not have been able to use Num elements in sets. By the same token, types inherited from Java, such as Int, Double, or String are not subclasses of Ordered, so values of these types cannot be used as set elements.
A more flexible design, which admits elements of these types, uses view bounds instead of the plain type bounds we have seen so far. The only change this entails in the example above is in the type parameters:
trait Set[A <% Ordered[A]] ... class EmptySet[A <% Ordered[A]] ... class NonEmptySet[A <% Ordered[A]] ...
View bounds <% are weaker than plain bounds <:: A view bounded type parameter clause [A <% T] only specifies that the bounded type A must be convertible to the bound type T, using an implicit conversion.
The Scala library predefines implicit conversions for a number of types, including the primitive types and String. Therefore, the redesign set abstraction can be instantiated with these types as well. More explanations on implicit conversions and view bounds are given in Section 15.
