Файл: Programming_in_Scala,_2nd_edition.pdf

decide whether or not their subclasses may be equal to instances of the superclass. Because ColoredPoint overrides canEqual, for example, a colored point may never be equal to a plain-old point. But because the anonymous subclass referenced from pAnon does not override canEqual, its instance can be equal to a Point instance.

One potential criticism of the canEqual approach is that it violates the Liskov Substitution Principle (LSP). For example, the technique of implementing equals by comparing run-time classes, which led to the inability to define a subclass whose instances can equal instances of the superclass, has been described as a violation of the LSP.7 The reasoning is that the LSP states you should be able to use (substitute) a subclass instance where a superclass instance is required. In the previous example, however, “coll contains cp” returned false even though cp’s x and y values matched those of the point in the collection. Thus it may seem like a violation of the LSP, because you can’t use a ColoredPoint here where a Point is expected. We believe this is the wrong interpretation, though, because the LSP doesn’t require that a subclass behaves identically to its superclass, just that it behaves in a way that fulfills the contract of its superclass.

The problem with writing an equals method that compares run-time classes is not that it violates the LSP, but that it doesn’t give you a way to create a subclass whose instances can equal superclass instances. For example, had we used the run-time class technique in the previous example, “coll contains pAnon” would have returned false, and that’s not what we wanted. By contrast, we really did want “coll contains cp” to return false, because by overriding equals in ColoredPoint, we were basically saying that an indigo-colored point at coordinates (1, 2) is not the same thing as an uncolored point at (1, 2). Thus, in the previous example we were able to pass two different Point subclass instances to the collection’s contains method, and we got back two different answers, both correct.

30.3 Defining equality for parameterized types

The equals methods in the previous examples all started with a pattern match that tested whether the type of the operand conformed to the type of the class containing the equals method. When classes are parameterized, this scheme needs to be adapted a little bit. As an example, consider binary

7Bloch, Effective Java Second Edition, p. 39 [Blo08]

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

trees. The class hierarchy shown in Listing 30.3 defines an abstract class Tree for a binary tree, with two alternative implementations: an EmptyTree object and a Branch class representing non-empty trees. A non-empty tree is made up of some element elem and a left and right child tree. The type of its element is given by a type parameter T.

trait Tree[+T] { def elem: T

def left: Tree[T] def right: Tree[T]

}

object EmptyTree extends Tree[Nothing] { def elem =

throw new NoSuchElementException("EmptyTree.elem") def left =

throw new NoSuchElementException("EmptyTree.left") def right =

throw new NoSuchElementException("EmptyTree.right")

}

class Branch[+T]( val elem: T,

val left: Tree[T], val right: Tree[T]

) extends Tree[T]

Listing 30.3 · Hierarchy for binary trees.

We’ll now add equals and hashCode methods to these classes. For class Tree itself there’s nothing to do, because we assume that these methods are implemented separately for each implementation of the abstract class. For object EmptyTree, there’s still nothing to do because the default implementations of equals and hashCode that EmptyTree inherits from AnyRef work just fine. After all, an EmptyTree is only equal to itself, so equality should be reference equality, which is what’s inherited from AnyRef.

But adding equals and hashCode to Branch requires some work. A Branch value should only be equal to other Branch values, and only if the two values have equal elem, left and right fields. It’s natural to apply

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

Section 30.3 Chapter 30 · Object Equality 700

the schema for equals that was developed in the previous sections of this chapter. This would give:

class Branch[T]( val elem: T,

val left: Tree[T], val right: Tree[T]

)extends Tree[T] {

override def equals(other: Any) = other match { case that: Branch[T] => this.elem == that.elem &&

this.left == that.left && this.right == that.right

case _ => false

}

}

Compiling this example, however, gives an indication that “unchecked” warnings occurred. Compiling again with the -unchecked option reveals the following problem:

$ fsc -unchecked Tree.scala

Tree.scala:14: warning: non variable type-argument T in type pattern is unchecked since it is eliminated by erasure

case that: Branch[T] => this.elem == that.elem &&

ˆ

As the warning says, there is a pattern match against a Branch[T] type, yet the system can only check that the other reference is (some kind of) Branch; it cannot check that the element type of the tree is T. You encountered in Chapter 19 the reason for this: element types of parameterized types are eliminated by the compiler’s erasure phase; they are not available to be inspected at run-time.

So what can you do? Fortunately, it turns out that you need not necessarily check that two Branches have the same element types when comparing them. It’s quite possible that two Branches with different element types are equal, as long as their fields are the same. A simple example of this would be the Branch that consists of a single Nil element and two empty subtrees. It’s plausible to consider any two such Branches to be equal, no matter what static types they have:

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

scala> val b1 = new Branch[List[String]](Nil, EmptyTree, EmptyTree)

b1: Branch[List[String]] = Branch@158c7fa

scala> val b2 = new Branch[List[Int]](Nil, EmptyTree, EmptyTree)

b2: Branch[List[Int]] = Branch@1f4a968

scala> b1 == b2 res19: Boolean = true

The positive result of the comparison above was obtained with the implementation of equals on Branch shown previously. This demonstrates that the element type of the Branch was not checked—if it had been checked, the result would have been false.

Note that one can disagree which of the two possible outcomes of the comparison would be more natural. In the end, this depends on the mental model of how classes are represented. In a model where type-parameters are present only at compile-time, it’s natural to consider the two Branch values b1 and b2 to be equal. In an alternative model where a type parameter forms part of an object’s value, it’s equally natural to consider them different. Since Scala adopts the type erasure model, type parameters are not preserved at run time, so that b1 and b2 are naturally considered to be equal.

There’s only a tiny change needed to formulate an equals method that does not produce an unchecked warning: instead of an element type T, use a lower case letter, such as t:

case that: Branch[t] => this.elem == that.elem && this.left == that.left && this.right == that.right

Recall from Section 15.2 that a type parameter in a pattern starting with a lower-case letter represents an unknown type. Hence, the pattern match:

case that: Branch[t] =>

will succeed for Branch values of any type. The type parameter t represents the unknown element type of the Branch. It can also be replaced by an underscore, as in the following case, which is equivalent to the previous one:

case that: Branch[_] =>

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

The only thing that remains is to define for class Branch the other two methods, hashCode and canEqual, which go with equals. Here’s a possible implementation of hashCode:

override def hashCode: Int = 41 * (

41 * (

41 + elem.hashCode ) + left.hashCode

) + right.hashCode

This is only one of many possible implementations. As shown previously, the principle is to take hashCode values of all fields, and to combine them using additions and multiplications by some prime number. Here’s an implementation of method canEqual in class Branch:

def canEqual(other: Any) = other match { case that: Branch[_] => true

case _ => false

}

The implementation of the canEqual method used a typed pattern match. It would also be possible to formulate it with isInstanceOf:

def canEqual(other: Any) = other.isInstanceOf[Branch[_]]

If you feel like nit-picking (and we encourage you to do so!), you might wonder what the occurrence of the underscore in the type above signifies. After all, Branch[_] is technically a type parameter of a method, not a type pattern, so how is it possible to leave some parts of it undefined? The answer to that question is found in the next chapter: Branch[_] is a shorthand for a so-called existential type, which is roughly speaking a type with some unknown parts in it. So even though technically the underscore stands for two different things in a pattern match and in a type parameter of a method call, in essence the meaning is the same: it lets you label something that is unknown. The final version of Branch is shown in Listing 30.4.

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