Chapter 19

Abstraction and Polymorphism

Understanding the concept of abstraction is critical for improving your capabilities as a programmer. The ability to express our thoughts in more abstract ways is a significant part of what has allowed modern software systems to scale to the size they are today. We have dealt a little with abstraction already. Back in section 6.4 we saw how we could pass a function as an argument to allow us to accumulate multiple different types of values using a single recursive function. The basic idea of abstraction is that you want to write code where some part of what it does is not fully specified until it is used. We have used this idea significantly through the different methods in the Application Programming Interface (API). At this point it is time to explore the different mechanisms that allow us to create abstraction and write some code that uses them.

19.1 Polymorphism

One of the most powerful ways to add abstraction into code is through polymorphism. From the Greek roots, the word literally means "many shapes". In the context of programming though it means many types. So far the code that we have written, with the exception of a few lines of code in 7.5.2, has been monomorphic. This means that our code only worked with one type. Perhaps the best example of when this was a limitation comes from chapter 13 where we wrote sorts that used the Double type originally, but had to make a second version when we wanted to sort a case class. That was because our original sort was monomorphic. It only worked with the one type we wrote it for and nothing else.

If you go back and look at that code you will see how inefficient that can be. The difference between our sorts was very small. We did a copy and paste and then modified only two lines in the code. That type of duplication is wasteful and it leaves us with overly long code that is prone to errors and hard to work with. Plus, one would expect that with so few changes between the versions, it should be possible to make one version that handles them all. To put it a different way, we should be able to abstract out the differences so that we have one version that will work in the different situations we want. In this case, part of that abstraction is abstracting over types. To do that we need polymorphism.

There are multiple different styles of polymorphism, but we can group them into two broad categories: universal and ad-hoc. Universal polymorphism implies that code can work with an infinite number of types. By contrast, ad-hoc polymorphism only works with a finite number of types. We will primarily consider universal polymorphism in two different forms, inclusion polymorphism and parametric polymorphism.

19.2 Inclusion Polymorphism (Inheritance and Subtyping)

Inclusion polymorphism is a form of universal polymorphism that we get from subtyping. That is to say when all elements of one type are also part of another type. This is a topic that was touched on in section 7.5.3 and figure 7.1 showed a simplified Unified Modeling Language (UML) class diagram with some of the different types in Scala. Figure 19.1 shows an updated version of that diagram that includes direct subtyping relationships as well as some implicit conversions that are written into the Scala libraries to make things easier for you.

This figure shows you what subtyping relationships exist, but it does not explain how they get into the code or how we can use them to write polymorphic code. The answer to the first question is something called inheritance. Inheritance is the standard way we get subtyping and inclusion polymorphism in most object-oriented languages that are built on the concept of a class. When one class, B, inherits from another class, A it implies two things. One of those things is that B is a subtype of A. The other is that B gets all the data and methods that were part of A. The latter we will call code-reuse. It helps us to not duplicate code, and might seem like the more important of the two aspects, however, the real power of polymorphism is the result of the subtyping.

So what does it mean for type B to be a subtype of type A? We can say that B is a subtype of A if any situation where an object of type A is needed, we can give it an object of type B and it will work. To put this into a more concrete form, consider the following example. You have a recipe that calls for three different types of fruit. The recipe gives you instructions for how to prepare the fruit and include it with the other ingredients. In this case, Fruit is the supertype and we have a description of how to do something with. There are many different subtypes of Fruit that we could choose to use including Apple, Cherry, Banana, and Strawberry. This particular example is illustrated using a simple UML diagram in figure 19.2. Here we see the type Fruit at the top with generalization arrows connecting it to the various subtypes. The direction of the arrows in UML is significant because while subtypes have to know about their supertype, a supertype generally does not, and should not, know about subtypes.

In code, this means that you can write a function like makeBreakfastShake that works with type Fruit and it should work with instances of Apple, Banana, Cherry, or Strawberry. Consider this code that might represent that function.

def makeBreakfastShake(fruit:Fruit) {

 if(!fruit.canEatSkin) {

 fruit.peel

 }

 blender += fruit

 blender += juice

 blender += ice

 blender.blend

}

The idea is that we could call this function using code like this.

makeBreakfastShake(new Banana)

makeBreakfastShake(new Strawberry)

We want this to work because Banana and Strawberry are both subtypes of Fruit. The question is, what is required for this to happen? For the type Fruit to work with makeBreakfastShake it needs to have a method called canEatSkin that takes no arguments and returns a Boolean and a method peel that also takes no arguments. For objects of type Banana to work in place of Fruit, they have to have those same methods.

As you can see, it turns out that the code-reuse part of inheritance is not just there to reduce code duplication, it helps with subtyping. A subtype is guaranteed to have all the methods and data members of the supertype that might be called by outside code.

Of course, you might not always want those methods to do the same things. In this case, objects of the Banana type should return false for canEatPeel while objects of the Strawberry type should return true. Changing the implementation of a method in the supertype is called overriding. Indeed, this is why the override keyword was needed back in chapter 12 on the paint method. Figure 19.3 shows a UML class diagram using the more complete format for the classes so that you can see the methods that might be in them.

The Fruit type in this diagram has six different methods that pertain to all different subtypes of Fruit. Each of these can be implemented in some default way. The four subtypes only list the methods that they override. The other methods are present in their default implementation as a result of inheritance.

Going back to figure 19.1 you notice that there is a lot of inheritance that goes on in the basic structure of the type system in Scala. Every class that you create automatically inherits from a type called AnyRef, which inherits from Any. You can look in the API to see the types Any, AnyRef, and AnyVal right at the top of the list of classes. If you look in AnyRef you will see that there are a number of different methods that will be in any class you create. We can demonstrate this by making a little class in the REPL and calling one of those methods.

scala> class Vect3D(val x:Double,val y:Double,val z:Double)

defined class Vect3D

scala> val jHat = new Vect3D(0,1,0)

jHat: Vect3D = Vect3D@24753433

scala> jHat.toString

res0: java.lang.String = Vect3D@24753433

Here we have a class for an immutable 3-D vector type that has no methods, just public members for three components. The second line creates an instance on this class which is followed by a notification that the variable jHat is of type Vect3D and has a given value. The value is a bit odd, having the name of the class followed by an @ symbol and a number. The third line shows a call to one of the methods inherited from AnyRef, the toString method. This call makes it clear where the text for the value came from. The toString method is actually defined on the type Any and, as such, is safe to call on any object in Scala. For that reason, it is used extensively to get a representation of objects. Here we see that it is called by the REPL.

Unfortunately, the default implementation of toString is not all that informative. For that reason, it is something that you often override. This code listing shows how we can do that.

scala> class Vect3D(val x:Double,val y:Double,val z:Double) {

 | override def toString():String = "Vect3D("+x+", "+y+", "+z+")"

 |}

defined class Vect3D

scala> val jHat = new Vect3D(0,1,0)

jHat: Vect3D = Vect3D(0.0, 1.0, 0.0)

scala> jHat.toString

res1: String = Vect3D(0.0, 1.0, 0.0)

The inclusion of override with a def that has the same signature as the inherited toString gives us a different implementation. You can see that this is now used in the REPL when the value of the object is printed as well as when the method is called directly.

This example shows an inherited method and how we can override it, but it does not actually demonstrate how to get inheritance in our code. It uses the inheritance that we get by default. If we want to inherit from something other than AnyRef, we use the extends keyword. This keyword is placed after the arguments to the class and before the open curly brace that starts the body of the class.

class Name(args) extends Supertype {body}

If you do not put in the extends keyword you get extends AnyRef by default.

To illustrate this, let us look at a different example that is a classic case of inheritance. We define a supertype called Shape that has some methods for things that we expect all shapes to be able to do.

class Shape {

 def area:Double = 0.0

 def circumference:Double = 0.0

 def draw(g:Graphics2D) {}

}

There are many different types of shape that we might want to have as subtypes of this class. Here are two possible examples.

class Rectangle(val width:Double,val height:Double) extends Shape {

 override def area:Double = width∗height

 override def circumference:Double = 2.0∗(width+height)

 override def draw(g:Graphics2D) {

 g.fill(new Rectangle2D.Double(0.0,0.0,width,height))

 }

}

class Circle(val radius:Double) extends Shape {

 override def area:Double = math.Pi∗radius∗radius

 override def circumference:Double = 2.0∗math.Pi∗radius

 override def draw(g:Graphics2D) {

 g.fill(new Ellipse2D.Double(0.0,0.0,2.0∗radius,2.0∗radius))

 }

}

Each of these classes takes some arguments and extends Shape, then overrides all of the methods of Shape.

We can now write code that takes an instance of Shape and pass it an instance of either Rectangle or Circle and it will work. The reason it will work is that inheritance guarantees us that any method we could call on an instance of Shape will be defined in the subtypes. Consider the following function and two calls to it.

def areaCircumferenceRatio(s:Shape):Double = {

 s.area/s.circumference

}

val circleACR = areaCircumferenceRatio(new Circle(5))

val rectACR = areaCircumferenceRatio(new Rectangle(4,5))

This is the heart of polymorphism, one piece of code that can work on multiple types. This is universal polymorphism because at any point in the future we could create a new subtype of Shape and it would work with this code as well.

As a general rule, inheritance should be used to represent an "is-a" relationship. In the examples we have seen so far, it seems quite natural to say that an apple is-a@is-a fruit or that a rectangle is-a shape. If you can not say that, then inheritance probably is not the construct you want to use. Instead, you should use composition. This is where you put an instance of the type as a member of some class instead of inheriting from it. To get the functionality, you make calls on that member. Composition is used to model a "has-a" relationship. We will see many examples of this type of construction later in the book. It should be emphasized that you do not want to abuse inheritance. The code-reuse aspect might seem great, but the subtyping should only be used when it makes sense.

The opposite is also true. There are times when you will have an is-a relationship and subtyping makes sense, but not all of the methods you would get through code-reuse fit. In those situations you should also refrain from using inheritance. An example of this is a square. Clearly a square is-a shape. In addition, a square is-a rectangle. That relationship can be expressed with the following one-line class.

class Square(length:Double) extends Rectangle(length,length)

Here the class Square takes one argument for the length of an edge. It extends Rectangle, and passes that length as both the height and the width arguments. As this example shows, when the subtype takes arguments, they are passed in an argument list that follows the name of the supertype after extends.

Given what we have written for Rectangle, this implementation of Square is perfectly acceptable and calls to all the methods of an instance of Square will work as desired. That is only because our Rectangle type happens to be immutable. Consider this alternative implementation of Rectangle.

class Rectangle(var width:Double,var height:Double) extends Shape {

 override def area:Double = width∗height

 override def circumference:Double = 2.0∗(width+height)

 override def draw(g:Graphics2D) {

 g.fill(new Rectangle2D.Double(0.0,0.0,width,height))

 }

}

If you use this with the above definition of Square everything compiles fine and it might even seem to run fine. However, there is something truly broken with this implementation. To see this, consider the following code.

val square = new Square(5)

square.width=20 // WARNING: Works in code, but not what we want.

println(square.area)

This does something that should not be possible. It makes a "square" that is 20 by 5. That certainly does not seem to fit the normal definition of a square.

The problem here is that when we make the Rectangle type mutable we effectively introduced two new methods: def width_=(w:Double) and def height_=(h:Double). These methods are not suitable for the Square, but by virtue of inheritance, our Square type gets them.

It is tempting to try to fix this by explicitly overriding the methods that set the width and height fields as is done in this code.

class Square(length:Double) extends Rectangle(length,length) {

 override def width_=(w:Double) {// ERROR: Can’t override mutable variables.

 width = w

 height = w

 }

 override def height_=(h:Double) {// ERROR: Can’t override mutable variables.

 height = h

 width = h

 }

}

This does not compile because you are not allowed to override methods associated with variables. Even if it were allowed, or if we used different methods to access and set the variables, it would not be a good idea. To understand why, consider what a programmer is expecting to happen when a line like rect.width = 20 is executed. Clearly the programmer who writes this line is expecting it to change the value stored in the width field. If the height field changes as well, that would be unexpected behavior and might well violate assumptions made elsewhere in the function. That could lead to bugs that are remarkably hard to find because the code would work fine when used with an instance of Rectangle, and reasoning about the program will not likely help the programmer find the error.

So be careful with how you use inheritance. It should only be used when you want both the subtyping and the code-reuse.

19.2.1 private Visibility and Inheritance

One thing that is lacking in our Shape example is a color for the shapes. Since there is a draw method, it would make sense for them to have a color to be drawn in, and because all shapes would have that color value, it would make sense for it to be part of the Shape class. Here are implementations of Shape, Rectangle, and Circle where the color field is a private, mutable value in Shape.

class Shape(private var color:Color) {

 def area:Double = 0.0

 def circumference:Double = 0.0

 def draw(g:Graphics2D) {}

}

class Rectangle(val width:Double,val height:Double,c:Color) extends Shape(c) {

 override def area:Double = width∗height

 override def circumference:Double = 2.0∗(width+height)

 override def draw(g:Graphics2D) {

 g.setPaint(color) // ERROR: Can’t get to the private color data member.

 g.fill(new Rectangle2D.Double(0.0,0.0,width,height))

 }

}

class Circle(val radius:Double,c:Color) extends Shape(c) {

 override def area:Double = math.Pi∗radius∗radius

 override def circumference:Double = 2.0∗math.Pi∗radius

 override def draw(g:Graphics2D) {

 g.setPaint(color) // ERROR: Can’t get to the private color data member.

 g.fill(new Ellipse2D.Double(0.0,0.0,2.0∗radius,2.0∗radius))

 }

}

The reason it is private is because it is mutable and we do not want to allow any piece of code that gets hold of a Shape object to be able to change that value. As the comments indicate, these classes will not compile. While subtypes get copies of everything in the supertype, they do not have direct access to private elements. So using this approach, the subtypes can not get to color unless we add a method for them to access it through.

This behavior is what we really desire. When something is made private, that means that other parts of code outside of that class should not be able to access it. Anyone can make a subtype of a class. If that gave them access to private data, then private would not really be all that safe. Granted, if color were declared as a val instead of a var, we would not need to hide it because the java.awt.Color class is immutable so other code could not change it, even if it could access it.

19.2.2 Protected Visibility

Of course, there are times, like our colored shape example, when you do want to have data or methods that are only accessible to the subtypes. This is the reason for the protected visibility. When a method or data member is modified with the protected keyword, it is visible in that class and its subclasses, but not to any other code. Using this, we could modify the Shape class to the following.

class Shape(protected var color:Color) {

 def area:Double = 0.0

 def circumference:Double = 0.0

 def draw(g:Graphics2D) {}

}

With color set to be protected, the previous code for Rectangle and Circle will work.

The protected visibility is something that is not used very often. If a value really needs to be hidden it should be private. Making it protected is a signal to programmers that it is needed by subclasses, but that they need to know what they are doing if they are going to use or alter it.

19.2.3 Calling Methods on the Supertype

Sometimes when you override a method in a subtype, you still want the code from the supertype to be run. There are actually situations where you are expected to call the method in the supertype before doing additional work. To support this type of behavior, you can use the super keyword like an object that references the part of the current object that is the supertype.

This can be used to solve the coloring problem in a way that keeps the color private. Consider the following implementation of Shape.

class Shape(private var color:Color) {

 def area:Double = 0.0

 def circumference:Double = 0.0

 def draw(g:Graphics2D) {

 g.setPaint(color)

 }

}

This has a private member color so it is not visible to the subtypes and is well encapsulated so we do not have to worry about other code changing it. Unlike the last version with a private color, this one has some code in the draw method that sets the paint on the Graphics2D object to color. Having this in the code allows us to do the following in Rectangle.

class Rectangle(val width:Double,val height:Double,c:Color) extends Shape(c) {

 override def area:Double = width∗height

 override def circumference:Double = 2.0∗(width+height)

 override def draw(g:Graphics2D) {

 super.draw(g)

 g.fill(new Rectangle2D.Double(0.0,0.0,width,height))

 }

}

By making a call to draw on super, this version can set the color when draw is called without actually having access to the value in the supertype. The same type of thing could be done in Circle.

One advantage to this approach is that as long as all the subtypes of Shape follow the pattern of making a call to super.draw before they draw their own geometry, it would be possible to add other settings such as different strokes or transformations to the Shape type without altering the draw methods in the subtypes. In large libraries, this same behavior can be problematic as it forces the supertype to stick with a certain behavior because all the subtypes, including those written by other authors, are expecting it to be maintained.

19.2.4 Anonymous Classes

At some point in this chapter you might have been thinking back to some things from earlier in the book and wondering how they were related to inheritance. A code segment like the following might specifically come to mind.

val panel = new Panel {

 override def paint(g:Graphics2D) {

 ...

 }

}

This was the first situation where we saw the keyword override. As you just learned, that signifies that you are creating a class that provides an alternate implementation for some method. Though you did not know it at the time, this syntax is creating a new class, an anonymous class. In this case, that new class inherits from Panel. You can think of it as being like this code.

class AnonymousPanelClass extends Panel {

 override def paint(g:Graphics2D) {

 ...

 }

}

val panel = new AnonymousPanelClass

In the first version, the compiler actually creates a new class with a name that includes characters you are not allowed to use in your program for class names so it is impossible to refer to the type you have created. Instead, you have to treat the new object as an instance of the supertype.

You will see that this type of thing is done a lot in Scala. Fortunately, the syntax for anonymous classes is so natural in Scala that you rarely think of what you are doing as inheritance. Instead you think of it more like you are making a specialized instance of some type that has some additional functionality.

One place where the fact that you are in an anonymous class or some other nested class is when you try to use this. By default, this refers to the current instance of the most closely bound class. If you want to refer to the instance of a class that is wrapped around the code you are using, but is not the closest one, simply prefix this with the name of the bounding type you are interested in. So if the declaration of panel above was nested in some other class call GUIProgram, you could refer to the current instance of GUIProgram inside of the code you write for panel by using GUIProgram.this.

19.2.5 Abstract Classes

Let us now go back to the Shape example with its two subclasses. This version has a constant public color, but uses the call to super to provide uniform behavior.

class Shape(val color:Color) {

 def area:Double = 0.0

 def circumference:Double = 0.0

 def draw(g:Graphics2D) {

 g.setPaint(color)

 }

}

class Rectangle(val width:Double,val height:Double,c:Color) extends Shape(c) {

 override def area:Double = width∗height

 override def circumference:Double = 2.0∗(width+height)

 override def draw(g:Graphics2D) {

 super.draw(g)

 g.fill(new Rectangle2D.Double(0.0,0.0,width,height))

 }

}

class Circle(val radius:Double,c:Color) extends Shape(c) {

 override def area:Double = math.Pi∗radius∗radius

 override def circumference:Double = 2.0∗math.Pi∗radius

 override def draw(g:Graphics2D) {

 super.draw(g)

 g.fill(new Ellipse2D.Double(0.0,0.0,2.0∗radius,2.0∗radius))

 }

}

There are some aspects of this code that should feel less than ideal to you. They can really be summed up in the following line.

val s = new Shape(Color.red)

This line of code compiles and runs just fine. The question is, what does it really mean? If you were to call area or circumference on the object that s references, you would get back 0.0. If you were to call draw, nothing would be drawn.

The problem is that while Shape is certainly a valid type, it is not a complete specification of an object. This is because while we certainly feel that all shapes should have areas and circumferences, we can not really define them in the completely general sense. We need to be able to say that a type has a method or some piece of member data, but not give it a definition. We also want Shape to represent a supertype only and objects should only be instantiated for the subtypes. This can be done with the following code.

abstract class Shape(val color:Color) {

 def area:Double

 def circumference:Double

 def draw(g:Graphics2D) {

 g.setPaint(color)

 }

}

Two things have been changed here. We have taken away the equal sign and what follows it for area and circumference. We have also added the keyword abstract to the class declaration.

Methods and member data that are not given a value in a class declaration are considered to be abstract. If anything in a class is abstract, then the class itself must be labeled as abstract. If you leave that off, you will get a syntax error. When a type inherits from an abstract class, it must either provide an implementation for the abstract members and methods or that subtype must also be labeled abstract.

Given this revised Shape class, the Rectangle and Circle classes shown above will work just fine and we will no longer have the conceptual difficulties produced by instantiating the Shape class directly. In addition, the override keyword is not required when you implement a method that is abstract in the supertype. There are two reasons for this. First, on the semantic side, you are not actually overriding an implementation in the supertype. Second, and more importantly, if the method is abstract and you do not implement it, that will generate a syntax error unless the class is labeled as abstract.

To help you understand this second reason, let us look at an example of why Scala requires the override keyword in the first place when you are overriding a method. Consider this version of Rectangle.

class Rectangle(val width:Double,val height:Double,c:Color) extends Shape(c) {

 def area:Double = width∗height

 def circumference:Double = 2.0∗(width+height)

 override def draw(g:Graphics) {// ERROR: Not really an override

 g.setPaint(color)

 g.fill(new Rectangle2D.Double(0.0,0.0,width,height))

 }

}

The override keyword has been dropped from area and circumference because they are abstract in the supertype. There is a comment on the draw method telling you that it will not compile. Can you tell what is wrong? There is a very subtle error here that most people would miss without the comment and it is quite possible that you are having a hard time identifying it even with the comment. The error is the x is listed as being type Graphics instead of Graphics2D. That kind of little typo is very easy to do when you are coding and, if it were not a syntax error it could produce a logic error that is very difficult to track down. Scala requires override in this usage so that it will be a syntax error if you change the type. In the situation where override is not required because the method in the supertype is abstract, a typo in the argument or method name will leave that method unimplemented, which will generate a different error indicating that the class has to be abstract because some method is abstract.

19.2.6 traits

The class and object constructs are not the only ways to create new types in Scala. A third option, which is significant to us in this chapter, is the trait. A trait is very similar to an abstract class in many ways. The two primary differences are that traits can not take arguments and you can inherit from more than one trait.

It was not specifically said above, but you might have noticed there was no description of how to list multiple classes after extends. This was not an oversight, you are not allowed to list multiple classes there. You are allowed to follow the class with multiple traits or just have one or more traits. The various types you inherit from are separated by the with keyword.

To understand why you would want to do this, consider the following example. Imagine you are writing software to simulate people moving through a building to help with designing the space. You have a type called Person that represents everyone that can be in the simulation. The company you are working with knows there are certain categories of people who behave in significantly different ways that the simulation must handle. For example, they need types for Parent, Child, and GeneralAdult. The need for facilities in the building means they also need types for Male and Female. This last part creates a problem for single inheritance because you want to be able to represent a type Father by inheriting from Parent and Male. The subtype relationship makes sense there, but if both of those type are written as classes, you will not be able to use them both.

There are two ways that you could approach this problem with traits. A somewhat standard inheritance scheme might use the following structure.

trait Person {...}

trait Parent extends Person {...}

trait Male extends Person {...}

class Father extends Parent with Male {...}

Here both Parent and Male are subtypes of Person and Father inherits from both. In this case Person has to be a trait. This is because a trait can only inherit from other traits, not classes. Below that, either Parent or Male could have been a class, but not both because Father could not inherit from both of them then. Without a pressing reason to make one a class the choice of a trait provides consistency.

An alternate approach to constructing these types could be to use the traits as mix-in types. Here is what the code could look like.

class Person {...}

trait Parent {...}

trait Male {...}

class Father extends Person with Parent with Male {...}

In this construction both the Parent and Male types are traits that do not inherit from the Person. Instead, they are mixed in with the Person to create the Father. This approach is perhaps a bit more advanced and if the Parent and Male types involve code that requires them to know they will be used with a Person, you will need to use self-types which are discussed in appendix B. What matters now is that you be aware that this option exists so that as we build different inheritance hierarchies you will understand what is going on.

19.2.7 final

When something is abstract, it basically means that it has to be "overridden" in a subclass.1 There are times when it is also useful to be able to say that something can not be overridden, or changed in a subtype. This requirement can be enforced with the final keyword. You can use final to modify member data or methods that you do not want to be changed in subtypes. It can also be used to modify a whole class when you do not want to allow there to be any subtypes of that class.

You might wonder why you would want to make something final. One answer to this question is that you want to preserve some type of behavior in the current implementation that should not be altered in subtypes. It can also be a way of telling things that use a class that there is no possibility of getting different behavior from an object of that type than what they would get from that specific type.

The most common example of a place where you should use final to preserve a behavior in a type is when a class defines a type that is immutable. The strengths of immutable types, and how they can be used to simplify code is something that has been addressed quite a bit already in this book. Without inheritance, if you wrote a type to be immutable, you knew that any object of that type could be passed to other code without fear of it being changed.2 With inheritance, that does not automatically hold true unless you make the class final. The reason for this is that subtypes could add mutable data and/or override methods such that the new implementations include some reference to a mutable state.

To help you understand this, consider the following example class.

class CharInStrComp(str:String) {

 def positionCompare(str2:String,index:Int) : Int = {

 if(index >= str.length) {

  if(index >= str2.length) 0 else 1

 } else if(index >= str2.length) -1 else {

  str(index).compareTo(str2(index))

 }

 }

}

This class is immutable. Technically it does not even have member data to mutate. So if you have an object created from this class it can be passed around freely. With inheritance though it would be possible to do this.

class CntCharInStrComp(str:String) extends CharInStrComp(str) {

 var cnt = 0

 override def positionCompare(str2:String,index:Int) : Int = {

 cnt += 1

 super.positionCompare(str2,index)

 }

}

If you make an instance of CntCharInStrComp, it can be used in any place that wants a CharInStrComp. The only problem is that if this is done in a place where the code relies on objects being immutable, that code can now break because it is being passed an object that is mutable. To prevent this from happening, the original version should be made final, as is shown here.

final class CharInStrComp(str:String) {

 def positionCompare(str2:String,index:Int) : Int = {

 if(index >= str.length) {

  if(index >= str2.length) 0 else 1

 } else if(index >= str2.length) -1 else {

  str(index).compareTo(str2(index))

 }

 }

}

Now any attempt to make a subtype, whether mutable or not, will produce an error.

The final keyword is often underused in programming. However, it is good to get into the habit of making things final when there are not supposed to be subtypes or when something should not be overridden. This is not only a safe practice to get into, code that is labeled as final, can sometimes be compiled to faster implementations as well.

19.2.8 Method Resolution

When you are using inheritance, it is possible for you to create types for which there are multiple different method implementations. It is critical that you understand how Scala will determine which of the method implementations to use when the method is called on an object.

If the method is defined in the class or object the object was created from, that is the version that will be used. If it was not defined there, a version in one of the supertypes will be used. It will look at the supertypes beginning with the last one in the list. If it is not in the last type, it will try anything that type inherits from before going to the earlier elements of the list. This conversion from the full inheritance structure to a list of types to check through is called linearization. One caveat is that if the type appears multiple times, the last one by order of appearance in the resolution list is used.

Let us consider the type Father defined above. The linearization for the two approaches is actually the same. In the first case, if you list all the types from the end of the list back, ignoring repeats you get Father, Male, Person, Parent, and Person. The first instance of Person is removed leaving us with Father, Male, Parent, and Person. In the second approach, starting from the end goes directly to Father, Male, Parent, and Person.3

19.2.9 Inheriting from Function Types

We saw back in chapter 16 that when you treat an object like a function and pass it value arguments, Scala expands that to a call to the apply method on that object. When you enter the code o(i), Scala sees o.apply(i). As a result, you can easily make types that you treat like functions. In order for the type to really be a function type that you can use in places that expect functions, like calls to map, filter, foreach, etc., you need to have your type actually be a subtype of the function type.

To illustrate this, consider the simple example of a custom type that is a function that doubles integers. We could write such a type like this.

class G {def apply(i:Int) = 2∗i}

If we instantiate an object of this type we can use it like a function.

scala> val g = new G

g: G = G@28f2e328

scala> g(5)

res0: Int = 10

However, if we try to use this same object in a call to map, we get an error.

scala> List(1,2,3) map g

<console>:10: error: type mismatch;

 found : G

 required: (Int) => ?

   List(1,2,3) map g

     ^

As you can see from the error message, this does not work because the map method is expecting an argument that is a function of the form (Int) => ?. That is something that takes an Int as a single argument and outputs anything. We can make a type that fits this, but we need to use inheritance to do so.

scala> class F extends ((Int)=>Int) {def apply(i:Int) = 2∗i}

defined class F

scala> val f=new F

f: F = <function1>

scala> List(1,2,3) map f

res1: List[Int] = List(2, 4, 6)

The only difference between type F and type G is that F explicitly extends (Int)=>Int. The first impact of this can be seen in the creation of the object f where we get an different version of the toString method.

19.3 Inheritance in the Project

You now know enough about inheritance that we can see how to use it in our project code. The most obvious place inheritance will appear is the different Drawable types that we will want to include.

19.3.1 Drawables

Each different type of thing that we might want to draw will be a different subtype of Drawable. At the very least, we can start with some basic shapes like rectangles and ellipses. We will also include another type that will group together multiple elements in the drawing and represent a transformation. Back in chapter 12 we learned about the java.awt.geom.AffineTransform type and used it with our drawings on a Graphics2D object. We want a Drawable element that can include that type of functionality in our drawings.

There is another aspect to the Drawable type that relates to how it is included in the Graphical User Interface (GUI). We want the different things that are being drawn to appear in the JTree element in the GUI. The javax.swing.JTree displays objects that have to be subtypes of the javax.swing.tree.TreeNode type.4 To make this happen, we can just have the Drawable type extend TreeNode.

Given the description of Shape earlier in this chapter, you have probably also realized that the draw method in Drawable should be abstract because there really is not a good default implementation of how to draw. We will take the additional step of making Drawable into a trait. The resulting code looks like this.

/∗∗

 ∗ This represents the supertype for all the different types that can appear in

  our drawing.

 ∗/

trait Drawable extends TreeNode {

  /∗∗

 ∗ Causes this object to be drawn to g.

 ∗

 ∗ @param g a Graphics2D object to draw to.

 ∗/

  def draw(g : Graphics2D) : Unit

  /∗∗

 ∗ Gives back a GUI component that allows the user to change drawing properties.

 ∗

 ∗ @return A component that should be put in the GUI so the user can edit this

  object.

 ∗/

  def propertiesPanel() : scala.swing.Component

}

Note that one additional method has been added. This is a method that gives us back a GUI component that can be displayed when the user selects a particular Drawable. That GUI component should allow the user to change the settings for that object.

We are going to start with the three subtypes of Drawable mentioned above. One possible way to arrange this is as is shown in figure 19.5. Looking at this figure you might wonder where all the methods came from in the DrawTransform, DrawRectangle, and DrawEllipse classes. All of the methods listed in these classes, with the exception of draw, are abstract methods from TreeNode. Because they are abstract, they have to be implemented in any concrete subtype, which is why they appear in this figure.

It turns out that the implementations of all the methods other than draw will be exactly the same in both DrawRectangle and DrawEllipse. In fact, the implementations of these methods will be exactly the same for all the Drawable subtypes other than DrawTransform. For that reason, it makes sense to put another type in the hierarchy as shown in figure 19.6.

The new DrawLeaf type can implement the methods that come from TreeNode in a way that will work for nearly all of the subtypes of Drawable that we will create in this book. While right now having this type only prevents us from making two copies of the code, before we are done, it will have saved us from making many separate copies of these methods. We are not doing this on the DrawTransform side because we do not expect to have other classes that have Drawable children. Were that decision to change, we would probably want to pull those methods out from that side of the hierarchy as well.

With this design work done, we can now turn to implementations of these three new classes and one new trait. We will start with the DrawTransform class because it stands on its own and might help us to see what we can do on the other side of the hierarchy in figure 19.6. Here is code for that.

package scalabook.drawing

import java.awt.Graphics2D

import javax.swing.tree.TreeNode

import scala.collection.mutable

import swing._

import event._

import java.awt.geom.AffineTransform

/∗∗

 ∗ This class represents a transformation with children.

 ∗

 ∗ @param parent the DrawTransform that is the parent of this Drawable.

 ∗/

class DrawTransform(parent:DrawTransform) extends Drawable {

 private val subnodes = mutable.Buffer[Drawable]()

 private var propPanel:Component = null

 private object TransformType extends Enumeration {

 val Translate,Rotate,Scale,Shear = Value

 }

 import TransformType._

 private var transformType = Translate

 private val transformValue = Array.fill(3)(0.0)

 /∗∗

  ∗ This method applies a transform and draws all the subnodes.

  ∗

  ∗ @param g the Graphics2D object to draw to.

  ∗/

 def draw(g:Graphics2D) {

 val oldTrans = g.getTransform

 g.transform(buildTransform)

 subnodes.foreach(_.draw(g))

 g.setTransform(oldTrans)

 }

 private def buildTransform:AffineTransform = transformType match {

 case Translate =>

   AffineTransform.getTranslateInstance(transformValue(0),transformValue(1))

 case Rotate =>

   AffineTransform.getRotateInstance(transformValue(0),transformValue(1),transformValue(2))

 case Scale =>

   AffineTransform.getScaleInstance(transformValue(0),transformValue(1))

 case Shear =>

   AffineTransform.getShearInstance(transformValue(0),transformValue(1))

 }

 /∗∗

  ∗ Returns a GUI element for setting parameters.

  ∗ If this method is called multiple times, the same object will be returned.

  ∗

  ∗ @return a Component that can be added to a Swing GUI.

  ∗/

 def propertiesPanel() : Component = {

 if(propPanel == null) {

  propPanel = new BorderPanel {

   layout += new GridPanel(transformValue.length+1,1) {

  contents += new ComboBox(TransformType.values.toSeq) {

   listenTo(selection)

   reactions += {case e => if(selection.item!=null)

    transformType=selection.item}

  }

  for(i <- transformValue.indices) {

   val textField = new TextField(transformValue(i).toString) {

   listenTo(this)

   reactions += {case e:EditDone => transformValue(i)=text.toDouble}

   }

   contents += textField

  }

   } -> BorderPanel.Position.North

  }

 }

 propPanel

 }

 /∗∗

  ∗ Returns an object that can be used to run through the children.

  ∗

  ∗ @return a java.util.Enumeration object for the subnodes.

  ∗/

 def children : java.util.Enumeration[Drawable] = new

  java.util.Enumeration[Drawable] {

 val iter = subnodes.iterator

 def hasMoreElements() = iter.hasNext

 def nextElement() = iter.next

 }

 /∗∗

  ∗ Tells whether this can have children.

  ∗

  ∗ @return always true for this type.

  ∗/

 def getAllowsChildren : Boolean = true

 /∗∗

  ∗ Returns the child at a specified index.

  ∗

  ∗ @param childIndex the index in the sequence of children.

  ∗ @return the child at that index.

  ∗/

 def getChildAt(childIndex : Int) : Drawable = subnodes(childIndex)

 /∗∗

  ∗ Returns how many children this node has.

  ∗

  ∗ @return the number of children currently under this node.

  ∗/

 def getChildCount : Int = subnodes.length

 /∗∗

  ∗ Returns the index of a particular object.

  ∗

  ∗ @param node a TreeNode to search for in the sequence of children.

  ∗ @return the index of that child of -1 if it isn’t a child.

  ∗/

 def getIndex(node : TreeNode) : Int = subnodes.indexOf(node)

 /∗∗

  ∗ Returns the parent of this node.

  ∗

  ∗ @return the parent of this node. Will be null if this is the root.

  ∗/

 def getParent : DrawTransform = parent

 /∗∗

  ∗ Tells is this node is a leaf in the tree.

  ∗

  ∗ @return true if there are currently no children, otherwise false.

  ∗/

 def isLeaf : Boolean = subnodes.isEmpty

 /∗∗

  ∗ Adds a child to this node.

  ∗

  ∗ @param c the node to add.

  ∗/

 def addChild(c : Drawable) {subnodes += c}

 /∗∗

  ∗ Removes the specified drawable from the sequence of children.

  ∗

  ∗ @param c the node to remove.

  ∗/

 def removeChild(c : Drawable) {subnodes -= c}

 override def toString() = "Transform"

}

This class has four private data members. The first, called subnodes, that is a Buffer which stores all of the children of the transform.5 Those children are the things that the transform will be applied to. The next chapter will go into the details of the Buffer type. The second is a Component that keeps a reference to the properties panel. This starts off as null for reasons we will see below. The other two member data are an enumeration for the type of transform and an array of numeric values associated with the transform. The enumeration type is defined in the private object. See the aside for details on enumerations.

After the members are the various methods, beginning with those that were in Drawable. First is the draw method. This method stores the current transformation from g in a temporary variable, then applies whatever transform it will use to g. The buildTransform method matches on the enumeration value and produces the appropriate type of transform passing it 2 or 3 of the values in the array. After this, each of the elements of subnodes is told to draw itself. After they are done, the transform on g is set back to what it had been originally.

After draw is the propertiesPanel method. As the scaladoc comment describes, this method should return the same object if it is called multiple times. For that reason, it always returns propPanel. However, if propPanel is null, it changes it to refer to a newly built panel that has a ComboBox with three TextFields with appropriate event handling to change transformType when the ComboBox selection is altered or the values in the transformValue array when a text field is edited.6

Next in the file are seven methods that are required by TreeNode. Most of these have straightforward implementations based on the contents of subnodes. There are two that are worth discussing further. The first of these is the children method. This method is notable because it has to return an object of the type java.util.Enumeration. This type is not like the Enumerations we saw just above. This type is basically an iterator that was included in the Java libraries early on. Later versions of Java created their own Iterator type, also in java.util, but any library classes, like TreeNode, which already used Enumeration were stuck with that.

The Scala collections do not normally produce a java.util.Enumeration so we have to make our own. We do this by making an anonymous class that inherits from java.util.Enumeration. Fortunately, Enumeration only has two abstract methods that we have to implement: hasMoreElements and newElement. The implementations of these methods are very straightforward using an iterator that we get from subnodes.

The other method of interest is getParent. The implementation of this method is very simple, but it forces us to put a parameter at the top of the class so that when a DrawTransform is created, a parent has to be provided. The other point of interest on getParent is the return type. The getParent method in the TreeNode type specifies a return type of TreeNode. However, when you override a method, you are allowed to change the return type to a more specific subtype. In this case, we know that all parents will be of the type DrawTransform, which is a subtype of TreeNode so we are not violating what the supertype specifies. The getChild method is also returning a more specific type than required by TreeNode.

The next two methods in DrawTransform are addChild and removeChild. These methods were not inherited from any supertype. They exist here so that the Drawing type can do what it needs with the children without completely breaking the encapsulation on subnodes. At the very end is an override of the toString method so that transform objects will display nicely in GUIs.

With DrawTransform completed we can now turn to the other side of the Drawable hierarchy. We’ll start with DrawLeaf. It is a trait that will only implement the methods that are required for TreeNode.

package scalabook.drawing

import javax.swing.tree.TreeNode

import java.util.Enumeration

/∗∗

 ∗ A supertype for Drawables that don’t allow children.

 ∗/

trait DrawLeaf extends Drawable {

 val parent:DrawTransform

 /∗∗

  ∗ Returns an empty enumeration.

  ∗/

 def children : Enumeration[Drawable] = new Enumeration[Drawable] {

 def hasMoreElements() = false

 def nextElement() = null

 }

 /∗∗

  ∗ Returns false.

  ∗/

 def getAllowsChildren : Boolean = false

 /∗∗

  ∗ Returns null for any input.

  ∗/

 def getChildAt(childIndex : Int) : Drawable = null

 /∗∗

  ∗ Returns 0.

  ∗/

 def getChildCount : Int = 0

 /∗∗

  ∗ Returns -1 for any input.

  ∗/

 def getIndex(node : TreeNode) : Int = -1

 /∗∗

  ∗ Returns the parent of the current node.

  ∗/

 def getParent : DrawTransform = parent

 /∗∗

  ∗ Returns true.

  ∗/

 def isLeaf : Boolean = true

}

The methods are fairly straightforward. The only thing that might stand out in this code as being interesting is the abstract declaration of parent. The getParent method is defined here and has to be able to return something. However, a trait can not take arguments, so the way we can make sure a value is provided by the subtypes is to put in an abstract val. We can see how this plays out by looking at DrawRectangle.

package scalabook.drawing

import java.awt.Graphics2D

import java.awt.Color

import java.awt.geom.Rectangle2D

import swing._

import event._

/∗∗

 ∗ A Drawable that displays a filled colored rectangle.

 ∗/

class DrawRectangle(p:DrawTransform) extends DrawLeaf {

 val parent = p

 private var propPanel:Component = null

 private var color = Color.black

 private var width = 100.0

 private var height = 100.0

 /∗∗

  ∗ Draws a rectangle.

  ∗

  ∗ @param g the Graphics2D object that is drawn to.

  ∗/

 def draw(g:Graphics2D) {

 g.setPaint(color)

 g.fill(new Rectangle2D.Double(0,0,width,height))

 }

 /∗∗

  ∗ Returns a Component for editing the settings of this object.

  ∗

  ∗ @return a GUI component for editing the settings of the rectangle.

  ∗/

 def propertiesPanel() : Component = {

 if(propPanel == null) {

  propPanel = new BorderPanel {

   layout += new BorderPanel {

  layout += new GridPanel(2,1) {

   contents += new Label("Width")

   contents += new Label("Height")

  } -> BorderPanel.Position.West

  layout += new GridPanel(2,1) {

   contents += new TextField(width.toString) {

   listenTo(this)

   reactions += {case e:EditDone => width = text.toDouble}

   }

   contents += new TextField(height.toString) {

   listenTo(this)

   reactions += {case e:EditDone => height = text.toDouble}

   }

  } -> BorderPanel.Position.Center

   } -> BorderPanel.Position.North

   layout += Button("Select Color") {

  val newColor = javax.swing.JColorChooser.showDialog(peer,"Select

   Color",color)

  if(newColor!=null) color=newColor

   } -> BorderPanel.Position.South

  }

 }

 propPanel

 }

 override def toString() = "Rectangle"

}

The fact that DrawRectangle is a class means that it can take an argument of the parent object. The first thing it does in the class is to define the abstract parent member and give it the value of what was passed in. After this are some member data declarations and the methods. First is a simple draw method, followed by propertiesPanel which is similar to what we saw in DrawTransform only it is build for the settings of the rectangle. At the end we override toString for the purposes of the GUI.

The DrawEllipse type is basically identical to the DrawRectangle type except the draw method calls fill on an Ellipse2D. With so much code in common, you might expect that it should be possible to abstract over this difference and use a single class for both DrawRectangle and DrawEllipse. Indeed this is possible. It was not done here because we want to illustrate inheritance. Doing this better is left as an exercise for the student.

19.3.2 Integration with Drawing

The code for these different types does not do anything for us until they have been used in the code for a Drawing. To do a simple test, you can change the declarations of root and tree and add a line after them in Drawing like this.

 private val root = new DrawTransform(null)

 private val tree = new javax.swing.JTree(root)

 root.addChild(new DrawRectangle(root))

With this code you will get a DrawTransform with one rectangle under it for the drawing. If you run the program and make a new drawing, the tree should also display this instead of having the default and the drawing section should display the 100 by 100 pixel black rectangle. This still does not display the properties panel or let us change anything in the drawing. For that we need to add more code.

The following is a complete version of Drawing that includes buttons for adding and removing new Drawable objects as well as a reaction to clicking on the tree to that the properties panel for what is clicked on will be displayed.

package scalabook.drawing

import swing._

import javax.swing.event._

/∗∗

 ∗ This type represents a Drawing that you can have open in the program.

 ∗/

class Drawing {

 private val drawPanel = new DrawPanel

 private var propPanel:Component = null

 private val root = new DrawTransform(null)

 private val tree = new javax.swing.JTree(root)

 /∗∗

  ∗ Returns a panel that displays the properties for this drawing.

  ∗

  ∗ @return a Component that can be put into a GUI.

  ∗/

 def propertiesPanel = {

 if(propPanel == null) {

  val commandArea = new TextArea()

  commandArea.editable = false

  val commandField = new TextField()

  val commandPanel = new BorderPanel {

   layout += commandField -> BorderPanel.Position.North

   layout += new ScrollPane(commandArea) -> BorderPanel.Position.Center

   preferredSize = new Dimension(500,200)

  }

  val drawProps = new GridPanel(1,1)

  propPanel = new SplitPane(Orientation.Vertical,

   new GridPanel(2,1) {

  contents += new BorderPanel {

   layout += new GridPanel(1,2) {

   contents += Button("Add"){

    executeOnSelection(d => addTo(d),addTo(root))

   }

   contents += Button("Remove"){

    executeOnSelection(d => remove(d))

   }

   } -> BorderPanel.Position.North

   layout+= new ScrollPane(new Component {

   override lazy val peer = tree

   tree.addTreeSelectionListener(new TreeSelectionListener {

    def valueChanged(e:TreeSelectionEvent) {

     executeOnSelection(d => {

     drawProps.contents.clear()

     drawProps.contents += d.propertiesPanel

     drawProps.revalidate

     drawProps.repaint

    })

    }

   })

   }) -> BorderPanel.Position.Center

  }

  contents += new ScrollPane(drawProps)

   },new SplitPane(Orientation.Horizontal,

  new ScrollPane(drawPanel),

  commandPanel))

 }

 propPanel

 }

 private def executeOnSelection(f: Drawable=>Unit,default: =>Unit = {}) {

 val path = tree.getSelectionPath

 if(path!=null) {

  val last = path.getLastPathComponent match {

   case drawable:Drawable if(drawable!=null)=>

  f(drawable)

   case _ =>

  }

 } else default

 }

 private def addTo(d:Drawable) = {

 assert(d!=null)

 val parent = d match {

  case dt:DrawTransform => dt

  case _ => d.getParent

 }

 val options = Seq("Ellipse","Rectangle","Transform")

 val choice = Dialog.showInput(propPanel,

  "What do you want to add?","Draw Type",Dialog.Message.Question,

   null,options,options(0))

 if(choice.nonEmpty) {

  parent.addChild(options.indexOf(choice.get) match {

   case 0 => new DrawEllipse(parent)

   case 1 => new DrawRectangle(parent)

   case _ => new DrawTransform(parent)

  })

  drawPanel.repaint

  tree.getModel match {

   case m:javax.swing.tree.DefaultTreeModel => m.reload

   case _ =>

  }

 }

 }

 private def remove(d:Drawable) {

 assert(d!=null)

 if(d.getParent!=null) {

  d.getParent.removeChild(d)

  drawPanel.repaint

  tree.getModel match {

   case m:javax.swing.tree.DefaultTreeModel => m.reload

   case _ =>

  }

 }

 }

 private class DrawPanel extends Panel {

 override def paint(g:Graphics2D) {

  g.setPaint(java.awt.Color.white)

  g.fillRect(0,0,size.width,size.height)

  root.draw(g)

 }

 }

}

The executeOnSelection method was added because adding, removing, and selecting all require finding the current selection and acting upon it. It was moved to a method to prevent duplication. The addTo and remove methods were added because they are longer and it improves the code structure to not have them nested deeply in function literals. In addition, addTo is called in two places so having the method prevents code duplication.

If you put this code into Eclipse or try to compile it, you will find that there are errors in both addTo and remove. These errors occur because the getParent method returns the type TreeNode, which does not have removeChild or addChild methods. This error might confuse you given that the DrawRectangle and DrawLeaf types both say they return DrawTransform from getParent and it does have those methods. The root of the problem is that the value passed into both of these methods is declared to be a Drawable and the getParent method has not been defined in Drawable so it automatically gets what was in TreeNode. To fix this, we need to add the following line of code to Drawable.

 override def getParent : DrawTransform

Note that just because every subtype of Drawable that we had made returned a DrawTransform does not make it safe to assume that all subtypes will. Without this line of code, we could easily have created some other class that inherits directly from Drawable that returns some other type of TreeNode from getParent. This line of code is required to make it so that any attempt to do that results in a syntax error.

Enter the code that has been built to this point, or pull it down from the book’s website, and run it. Play with it to see what it does and go through it closely to see how it works. There are things that are missing and behaviors that we probably do not want. This project will continue to grow through the rest of the book and you want to be certain you understand what is going on with it.

 object MyApp extends App {

  println(args mkString (" "))

 }

19.4 Parametric Polymorphism

The inclusion polymorphism we get from inheritance and subtyping is not the only form of universal polymorphism. There is a second type called parametric polymorphism. This type of polymorphism was briefly discussed in section 7.5.2. It is also something that we have been using extensively since chapter 7. You use it every time you deal with a List or an Array. This is what we get when we write code that has type parameters.

You have become familiar with using parentheses to pass values to methods when you call them or classes when you construct a new object. In the same way, you can use square brackets to pass type parameters. Consider these two declarations.

scala> val lst1 = Array(1,2,3)

lst1: Array[Int] = Array(1, 2, 3)

scala> val lst2 = Array[Any](1,2,3)

lst2: Array[Any] = Array(1, 2, 3)

They both declare arrays that store the values 1, 2, and 3. Those values are all Ints so if we let Scala infer a type, as in the first case, we get Array [Int]. In the second case we explicitly pass in a parameter type of Any and we get back that type. The syntax here is to pass any type arguments in square brackets before the parentheses with the value arguments. You might feel like there is not any difference between these two lists, but the type parameter changes what you can do with them.

scala> lst1.sum

res0: Int = 6

scala> lst2.sum

<console>:9: error: could not find implicit value for parameter num: Numeric[Any]

  lst2.sum

  ^

You are not able to do sums with type Any. You might question why you can not sum the elements of lst2, but consider what happens here.

scala> lst2(1)=true

scala> lst2(2)=List(‘a’,’b’,’c’)

scala> lst2

res3: Array[Any] = Array(1, true, List(a, b, c))

Type Any really does mean anything in Scala. Hopefully it is clear why trying to take the sum of this list should fail.

19.4.1 Parametric Types

What about using type parameters in our code to make it more flexible? You use a type parameter when you have code that you want to have work with a very broad set of types that possibly have nothing in relation to one another. The most common example of this is collections. Things like lists and arrays that should be able to hold anything you want, but where you do care about what they are holding because you need to know the type when you take things out. This is a usage that we will see a lot in chapters 20, 24, 25, 26, 29, 31, and 32. For now, we can provide some simple examples to give you a flavor for this use of parametric polymorphism.

We’ll go back to the theme park example for this. As you write code for running the different aspects of the park, you realize that a lot of different things are recorded by time of day. This might be sales numbers, passenger counts, resource usage, or employees on duty. Without parametric polymorphism, you wind up duplicating a lot of code because while the code for the times aspect is the same, the types can be very different. Here is a first draft implementation of a class you might use to deal with this.

package scalabook.themepark

/∗∗

 ∗ This is a Time of Day Values collection to help reduce code usage

 ∗ when dealing with values that are associated with the time of day.

 ∗

 ∗ @tparam A the type of data being stored.

 ∗/

 class ToDValues[A] {

 private val values:Array[Option[A]] = Array.fill(24)(None:Option[A])

 /∗∗

  ∗ This allows you to get a value for a particular hour. If there isn’t

  ∗ a value, it will throw an exception.

  ∗

  ∗ @param hour the hour of the day to get. Should be between 0 and 23 inclusive.

  ∗ @return the value stored for that hour.

  ∗/

 def apply(hour:Int) : A = values(hour).get

 /∗∗

  ∗ This allows you to get a value for a particular hour. If there isn’t

  ∗ a value, it will return None.

  ∗

  ∗ @param hour the hour of the day to get. Should be between 0 and 23 inclusive.

  ∗ @return an Option of the value stored for that hour.

  ∗/

 def get(hour:Int) : Option[A] = values(hour)

 /∗∗

  ∗ Allows you to set the value in a particular hour.

  ∗

  ∗ @param hour the hour of the day. Should be between 0 and 23 inclusive.

  ∗ @param v the new value to set.

  ∗/

 def update(hour:Int, v:A) = values(hour) = Some(v)

 /∗∗

  ∗ Allows you to set the value in a particular hour using a String for time.

  ∗

  ∗ @param hour the hour of the day. Should be between 0 and 23 inclusive.

  ∗ @param v the new value to set.

  ∗/

 def update(time:String, v:A) = {

 val hour = hourFromTime(time)

 values(hour) = Some(v)

 }

 /∗∗

  ∗ This method clears the value at a particular time.

  ∗

  ∗ @param hour the hour to clear.

  ∗/

 def clear(hour:Int) {values(hour) = None}

 /∗∗

  ∗ This method clears the value at a particular time.

  ∗

  ∗ @param hour the hour to clear.

  ∗/

 def clear(time:String) {

 val hour = hourFromTime(time)

 values(hour) = None

 }

 /∗∗

  ∗ Allows you to combine two sets of data using a specified function.

  ∗

  ∗ @param o the other set of data.

  ∗ @param f The function to apply to the two data types.

  ∗/

 def combine(o:ToDValues[A],f:(Option[A],Option[A])=>Option[A]) : ToDValues[A] = {

 val ret = new ToDValues[A]

 for((v,i) <- (values,o.values).zipped.map((v1,v2) => f(v1,v2)).zipWithIndex) {

  ret.values(i)=v

 }

 ret

 }

 override def toString() : String = "ToD :
"+

 (for((o,i) <- values.zipWithIndex) yield i+" : "+o).mkString("
")

 private def hourFromTime(time:String) : Int = {

 time.substring(0,time.indexOf(‘:’)).toInt +

  (if(time.endsWith("PM") && !time.startsWith("12")) 12 else 0)

 }

}

This class is parametric. The name, ToDValues is followed by a type argument [A]. The square brackets distinguish this from a value argument. It is customary to use single, uppercase letters, beginning with "A" for the names of type parameters. This code could be used like this.

 val riders1 = new ToDValues[Int]

 val riders2 = new ToDValues[Int]

 val worker1 = new ToDValues[String]

 val worker2 = new ToDValues[String]

 riders1(12) = 5

 riders1("8:24AM") = 10

 riders1(14) = 7

 riders2("2:13PM") = 8

 worker1(12) = "Jason"

 val totalRiders = riders1.combine(riders2,(o1,o2) => (o1,o2) match {

  case (None,None) => None

  case (Some(a),None) => Some(a)

  case (None,Some(b)) => Some(b)

  case (Some(a),Some(b)) => Some(a+b)

 })

 println(riders1)

 println(totalRiders)

This code creates four different instances of the class, two that store Ints type and two that store Strings. It then adds some values into three of them and uses combine to add up the riders.

Having parametric polymorphism means that we can write one class and have it work with Int, String, or any other type we desire. This class still has some significant limitations. For one thing, it is hard to set up. If you had the data you want in some other sequence and you wanted to get it into here, you could not without writing code to manually copy it element by element. The combine method is also a bit limited because we can only combine data of the same type and get back that type. We can not, for example, combine workers with riders. That type of functionality could be useful, but it requires we put type parameters on methods.

19.4.2 Parametric Functions and Methods

The standard approach in Scala to letting user create object of a type in different ways is to create a companion object with versions of apply that take the different arguments you want. We then make it so that the class itself takes the proper data as an argument. Here is an example of what that might look like.

object ToDValues {

 // First attempt that lacks type parameter and does not compile.

 def apply() : ToDValues = new ToDValues(Array.fill(24)(None))

}

As the comment implies, this does not work. The reason is that ToDValues is not a valid type by itself. It has to have a type parameter to be fully specified. In order to get a type to use there, we need to give the method a type parameter. The syntax for this is straightforward. We simply put type parameters in square brackets between the name and the value parameters. Doing this, we can make two apply methods that look like the following.

object ToDValues {

 def apply[A]() = new ToDValues[A](Array.fill(24)(None))

 def apply[A](a:A∗) = {

 val d = a.map(Option(_)).toArray

 new ToDValues[A](if(d.length<24) d.padTo(24,None) else

  if(d.length>24) d.take(24) else d)

 }

}

The second apply method allows us to have code that constructs a ToDValues object in the following ways.

 val riders1 = ToDValues[Int]()

 val riders2 = ToDValues(0,0,0,6,7,3,9)

What should jump out at you here is that the second usage does not specify the type parameter. This is because when they are used with methods, type parameters are generally inferred. As long at the type appears in the arguments to the method, you do not have to tell Scala what to use, it will figure it out. The line that creates riders1 requires that we tell it [Int] because there are no arguments, but the second one can figure out that it is working with the Int type.

This code works because the class has been set up to take an argument. That means the declaration would have changed from what was shown above to something like this.

class ToDValues[A](private val values:Array[Option[A]]){

There is one very big problem with this, it is possible to make a ToDValues object with an array that does not have 24 elements. This is clearly bad behavior and we need to prevent it. One way to prevent it is to make it so that the class has a private constructor. This means that only code associated with the class or its companion object can make a call to new for this object. Syntactically this is done by putting the private keyword before the value arguments like this.

class ToDValues[A] private(private val values:Array[Option[A]]){

Now the only way that outside code can instantiate a ToDValues object is through the apply methods of the companion object and it is easy for us to make sure those always create instances using arrays with 24 elements.

The other addition we would like to make is to enhance the combine method so that it can work with different types. Ideally, we’d like to have the ability to make it so that the input types could be two distinct types and the output type is a third type. We can accomplish this by introducing two type parameters on the method like this.

 def combine[B,C](o:ToDValues[B])(f:(Option[A],Option[B])=>Option[C]) :

  ToDValues[C] = {

 new ToDValues((values,o.values).zipped.map((v1,v2) => f(v1,v2)))

 }

Now we could do things like combine workers with riders to keep track of correlations that might be used for bonuses.

If you look closely you will see that something other than the addition of the type parameters changed here. Instead of a single value parameter list with two parameters, there are two lists with one parameter each. You should recall this is a technique called currying. This is not required, but it makes using the method easier. Here is an example of usage.

 val totalRiders = riders1.combine(riders2)((o1,o2) => (o1,o2) match {

  case (None,None) => None

  case (Some(a),None) => Some(a)

  case (None,Some(b)) => Some(b)

  case (Some(a),Some(b)) => Some(a+b)

 })

If we do not curry this method, the local type inference in Scala will not automatically figure out the type of o2 and we would have to specify it in the function declaration with (o1,o2:Int).

There is another pair of tasks that we have done which could benefit from type parameters, sorting and searching. The sorts and searches we wrote in chapter 13 only worked on one type. We had to copy them and make changes when we wanted to work with a different type. Now we know that we’d like to have a method like sort[A] that could sort any type we want. A simple attempt at doing this will show us a detail of type parameters that we have not discussed that causes problems.

object Sorts {

 def bubbleSort[A](a:Array[A]) {

 for(i <- 0 until a.length) {

  for(j <- 0 until a.length-1-i) {

   if(a(j)>a(j+1)) {// Error: > undefined for Any

  val tmp = a(j)

  a(j) = a(j+1)

  a(j+1) = tmp

   }

  }

 }

 }

}

The comment in this code describes the error that we get if we try to compile this code. This might give you pause considering that the code does not use the type Any explicitly. However, when we say that code must work with a type parameter, such as A, Scala has to make sure that it would work for any allowable A. Since there are no restrictions on this, that means that it must comply to the requirements of type Any.

One way to get around this is to put bounds on what we allow for type A. We’ll see how to do that in the next section. For now we will look at an alternate approach. Instead of assuming the type will work with a particular method, like <, we will pass in an extra argument that is a function that plays the role of <. We’ll call this function lt, short for less than.

object Sorts {

 def bubbleSort[A](a:Array[A])(lt:(A,A)=>Boolean) {

 for(i <- 0 until a.length) {

  for(j <- 0 until a.length-1-i) {

   if(lt(a(j+1),a(j))) {

  val tmp = a(j)

  a(j) = a(j+1)

  a(j+1) = tmp

   }

  }

 }

 }

}

This now provides us with a sort that can work for any type that we want, as long as we can define a function that represents less than for that type. As with the combine method, this works best if we curry the call to take two separate argument lists. If you load that into the REPL we can see it work like this.

scala> val rints = Array.fill(10)(util.Random.nextInt(30))

rints: Array[Int] = Array(29, 19, 15, 6, 14, 25, 1, 18, 10, 22)

scala> Sorts.bubbleSort(rints)(_<_)

scala> rints

res2: Array[Int] = Array(1, 6, 10, 14, 15, 18, 19, 22, 25, 29)

scala> val dints = Array.fill(10)(math.random)

dints: Array[Double] = Array(0.10388467739932095, 0.21220415385228875,

 0.8450116758102296, 0.5919780357660742, 0.9652457489710996,

 0.9401962629233398, 0.08314463374943748, 0.1502193866199757,

 0.7017577117339538, 0.9599077921736453)

scala> Sorts.bubbleSort(dints)(_<_)

scala> dints

res4: Array[Double] = Array(0.08314463374943748, 0.10388467739932095,

 0.1502193866199757, 0.21220415385228875, 0.5919780357660742,

 0.7017577117339538, 0.8450116758102296, 0.9401962629233398,

 0.9599077921736453, 0.9652457489710996)

Here the same method has been used to sort both Ints and Doubles. Note that the Array.fill method is also curried. We first learned about that technique when we were learning about fill and tabulate.

You will often see this type of sorting done using a function that returns an Int instead of a Boolean. When you need to know if two values are possibly equal in addition to being less than or greater than, this approach is beneficial. If the values are equal the function will return 0. If the first one is less, it will return a negative value. If the first one is greater it will return a positive value. We will see this type of usage of comparison functions in later chapters.

The strength of this approach using a second function argument for comparison is that is makes the sort more flexible. For example, in either of the above examples we could have sorted the numbers from greatest to least instead of least to greatest by simply passing in _>_ instead of _<_. In addition, it truly places no limitations on the type A. This allows you to sort things according to any sort order you want. For example, if you had a type for students you might want to sort by last name in some contexts or by grade in others. This approach would allow you to do that because the sort order is not attached to the object type. The downside of this approach is that the person calling the sort method has to write a comparison function each time they want to use it. In the examples above that was not a big deal because we had simply comparisons. However, there are times when that will not be the case.

19.4.3 Type Bounds

As we just saw, a normal type parameter, like [A], is treated like Any when we use objects of that type in code. While this is a very common usage, there are certainly times when you want to limit what types can be used in a type parameter so that you can safely call methods other than the small set that are available with Any. The way you do this is to put bounds on the type.

The most common form of this is putting an upper bounds on a type. This is done with the <: symbol. To understand why you might want to do this, let’s consider an example using code that we had before with fruit. The function, makeBreakfastShake that we wrote at the beginning of the chapter only used a single piece of fruit. This is not how it normally works. You would want to be able to include multiple pieces of fruit, perhaps of different types. A common example would be a shake with both bananas and strawberries. To do that, you might consider having code like this where you pass in an Array[Fruit].

def makeBreakfastShake(fruits:Array[Fruit]) {

 for(fruit <- fruits) {

 if(!fruit.canEatSkin) {

  fruit.peel

 }

 blender += fruit

 }

 blender += juice

 blender += ice

 blender.blend

}

This code probably looks fine to you and in many situations it will work. However, it is not perfect. Here is an example of where it runs into problems.

scala> val berries = Array(new Strawberry,new Strawberry)

berries: Array[Strawberry] = Array(Strawberry@51d36f77, Strawberry@103b1799)

scala> makeBreakfastShake(berries)

<console>:16: error: type mismatch;

 found : Array[Strawberry]

 required: Array[Fruit]

Note: Strawberry <: Fruit, but class Array is invariant in type T.

You may wish to investigate a wildcard type such as ‘_ <: Fruit’. (SLS 3.2.10)

   makeBreakfastShake(berries)

      ^

The variable berries here has the type Array[Strawberry] and that does work. The way makeBreakfastShake is written here, the argument passed in has to actually be an Array[Fruit]. The type Array[Strawberry] is not a subtype of Array[Fruit]. To understand why this is the case, simply imagine what would happen if you if such a call were allowed in this code.

def subCherries(bowl:Array[Fruit]) {

 if(!bowl.isEmpty) bowl(0)=new Cherry

}

This is fine if you call it with an Array[Fruit], but if you were allowed to call this function with an Array[Strawberry], you would wind up with a Cherry in an array that is not allowed to hold one.

The solution to this problem is implied in the error message above. The makeBreakfastShake function needs to say that it can take an array of any type that is a subtype of Fruit. This is done by specifying a type bound using <: as seen here.

def makeBreakfastShake[A <: Fruit](fruits:Array[A]) {

 for(fruit <- fruits) {

 if(!fruit.canEatSkin) {

  fruit.peel

 }

 blender += fruit

 }

 blender += juice

 blender += ice

 blender.blend

}

Using the <: symbol lets you put a constraint on the type parameter A. In this way, we can say that it is safe to assume that objects of type A are something more specific than Any. This is required in this example because Any does not have methods for canEatSkin or peel.

You can also specify a lower bound on a type using >:. We will see uses of this type constraint in chapter 25 when we are building immutable data types.

def makeBreakfastShake(fruits:List[Fruit]) {

 for(fruit <- fruits) {

 if(!fruit.canEatSkin) {

  fruit.peel

 }

 blender += fruit

 }

 blender += juice

 blender += ice

 blender.blend

}

One of the uses of traits is as mixins that add specific functionality to types. An example of this is the trait Ordered[A]. This trait has one abstract method, compare(that:A):Int. This method does a comparison to type A and returns a negative values if this comes before that in the ordering, a positive value if this comes after that in the ordering, and zero if they are equal. It has concrete methods to define the normal comparison operators based on the results of compare.

Any object that is a subtype of Ordered should work well in a sorting or searching algorithm. That fact that it is a subtype of Ordered means that it has a natural ordering that we want to use for the sort. This natural ordering means that we do not have to pass in a comparison function, it is built into the type. We simply have to limit what types can be used to subtypes of Ordered. A version of our bubble sort that takes this approach is shown here.

object Sorts {

 def bubbleSort[A <: Ordered[A]](a:Array[A]) {

 for(i <- 0 until a.length) {

  for(j <- 0 until a.length-1-i) {

   if(a(j)>a(j+1)) {

  val tmp = a(j)

  a(j) = a(j+1)

  a(j+1) = tmp

   }

  }

 }

 }

}

You should take special note of the type bound on this example: [A <: Ordered[A]]. This is a recursive type bound where the bound refers back to the type that it is constraining. In this context we require the ability to build a recursive type bound because inside the sort the code is doing a comparison between two objects of type A.

object Sorts {

 def bubbleSort[A <% Ordered[A]](a:Array[A]) {

 for(i <- 0 until a.length) {

  for(j <- 0 until a.length-1-i) {

   if(a(j)>a(j+1)) {

  val tmp = a(j)

  a(j) = a(j+1)

  a(j+1) = tmp

   }

  }

 }

 }

}

def structRead[A <: {def hasNextInt():Boolean; def nextInt():Int

 }](source:A):mutable.Buffer[Int] = {

 val buf = mutable.Buffer[Int]()

 while(source.hasNextInt) buf += source.nextInt

 buf

}

19.5 End of Chapter Material

19.5.1 Summary of Concepts

• Polymorphic code is code that can work with many types. Universal polymorphism implies that it can work with an infinite number of types.
• Inclusion polymorphism is a form of universal polymorphism that comes from subtyping. Scala, like most class based object-oriented languages, gets this through inheritance.
  • Subtypes can not get direct access to private members of the supertype. The protected visibility is meant to address this, but it is not as secure as private because you have little control over what code might inherit from any class you write.
  • The super keyword refers to the part of the current object that holds the supertype and can be used to make calls on on methods in the supertype that have been overridden in the current class.
  • Anonymous classes are created when a call to new on a type is followed by a block of code. This was done earlier in the book to make Panels and Frames without explicitly stating that is what you were doing.
  • Members and methods of a class can be left undefined. Such members are called abstract. If you have abstract members in a class the class itself must be declared abstract. You can not instantiate abstract classes.
  • A class can only inherit from one other class. There is a similar construct called a trait that allows for multiple inheritance. A trait is much like an abstract class.
  • Members and methods that should not be overridden can be declared final. You can also make whole classes final to prevent any other classes from extending them.
• Scala allows methods/functions, classes, and traits to type type parameters. These are passed in square brackets that come before any normal parameters in parentheses. This ability leads to parametric polymorphism, another form of universal polymorphism.
  • When a class takes a type parameter, the type must be specified at the point of instantiation with new. This is in contrast to parametric functions/methods which can typically infer the proper types of parameters.
  • You can place bounds on type parameters. Without bounds, the type parameters must be broadly assumed to be of the type Any.

19.5.2 Exercises

1. The code for the properties panels in the Drawable subtypes did not do a good job of handling exceptions if the user typed in something that was not a number. Edit the code to fix this.
2. The DrawRectangle and DrawEllipse classes shared a significant amount of code. Indeed, the two files only differed in that "Rectangle" was replaced by "Ellipse" in a few locations. Edit the code so that you have a single class called DrawBoundedShape that keeps the same member data as these classes, but abstracts over the exact shape that is created. There are several ways of doing this. One uses a function of (Double,Double) => Shape.
3. The hourFromTime method in the ToDValues class is not particularly robust. What are some situations where it could fail? Write a better replacement for it.
4. Draw out the inheritance hierarchies that you might design to represent the following types of objects.
   • Animal Life
   • School/University organization
   • Accounts for a large bank (savings, checking, etc.)
   • Types of Facebook friends
   • Types of students at your school
   • Whatever else you can think of that makes a good example of an "is-a" relationship.
5. Implement one of your hierarchies from above with a few simple methods.

19.5.3 Projects

There are several different options here that you could pick from based on which of the projects you started in the last chapter. The general idea though is that you will build a hierarchy of types for things that are related to your project. You can also put in parametric polymorphism if it fits your project.

When you do this, there is something very significant to keep in mind. Just because two things fit the "is-a" requirement does not mean they should be modeled with inheritance. One alternative is to use a single type and have the differences be data-driven. Whether you should use inheritance or just store values that provide the difference is best answered by whether the difference is truly a functional difference or a difference of magnitude. For example, in a game with different types of enemies or units, most of the different types should not be different subtypes because the only difference is one of things like strength or speed. However, when the difference would require one to use a very different implementation of a particular method, that is a reason to invoke inheritance.

1. In the first project on the MUD it was recommended that you create some character other than your player that wanders around the map. These other characters might play various roles in the final game. In a standard MUD, these would be the things that players do combat with. In many ways, these computer-controlled characters are just like players except that their movements and other actions are controlled by the computer instead of a human. This is a great potential use of inheritance. You might be able to come up with other uses as well.
2. For the two game projects, the possibilities depend a lot on what you are doing. As with the MUD, it is possible that you will have computer-controlled entities that mirror functionality of the player. Even if that does not fit, it is likely that there are other types of entities, active or not, which go into the game that share functionality in many ways, but not completely. (Note that for networked games the behavior of the local player and the remote player will be distinct, but that is something you do not need to deal with until chapter 23.)
3. One potential location for using inheritance in the web spider is with the types of data that you collect. You can make a supertype that represents data in general with abstract display capabilities. The details of this will depend on exactly what you are planning to do for your data collection.
4. If you are doing the mathematics workbench project, you will have a worksheet that can have multiple different types of things in it. That makes a great possibility for an inheritance hierarchy. At the very least, you should have commands and plots. However, you might have a lot more possibilities when you think about it more.
   Another element you could add to this project that uses inheritance is to implement the command pattern to provide undo and perhaps redo capabilities [6]. This works by creating a top-level command type that has two methods that might be called something like execute and undo. The the user does something that should change the worksheet in some way, instead of directly changing the worksheet, you build a subtype of the command type with an execute method that does the action and an undo method that undoes it. You pass that object to a main control object and it executes the command. You can keep track of the commands to provide undo and redo capabilities.
5. If you are working on the photoshop-like project, an obvious use of an inheritance hierarchy is the different things that can be drawn. Other elements that are options for the user to choose from can probably go into this as well. What is more, you can also implement the command pattern, described in the project above, to help make this work and to provide the undo and redo capabilities.
6. The simulation workbench project will be dealing with many different types of simulations. Each one will be a bit different, but they will all need to have the ability to run, draw, provide analysis data, and perhaps be paused and restarted. Create a supertype that can provide this type of functionality, then write a simple N-body gravity simulation with the ability to draw itself. This is what was done for project 1 and the projects leading into it. Through inheritance, you will make that whole sequence of projects into a small piece of this project.

1The term overridden is put in quotes here because technically something that is abstract is not over- ridden because it did not have a definition to start with.

2We will also see in chapter 21 that such objects can be used safely across multiple threads.

3In both of these cases, AnyRef and Any appear at the end of the list as every object implicitly inherits from AnyRef, which inherits from Any

4The TreeNode type is what is called an interface in Java. This is like a Scala trait where all methods are left abstract and no member data is defined.

5The Buffer type will described in detail in the next chapter. The short version is that it is like an Array that has the ability to grow and shrink.

6This code does not do proper exception handling if the user types in a value that is not a valid Double. Fixing this is left as an exercise for the reader.