Generics

In this chapter we’ll look at generics or type parameterisation or generic programming in Scala. We’ll look at:

• Syntax for generics: defining types and methods
• Bounded types, extends and super
• Wildcards in both Java and Scala
• Covariance and contravariance

Parametric Polymorphism

We talked briefly about subtype or inclusion polymorphism; the idea that subtypes can be substituted to stand in for their super-types. These stand-ins can provide different behaviour without changing the structure of your code. The types of polymorphism include:

• Inclusion polymorphism (see the chapter)
• Ad hoc polymorphism (which is basically method overloading)
• Parametric polymorphism

Parametric polymorphism allows us to write code generically without depending on specific types, yet still maintain type safety. We use it all the time when we work with classes that work against multiple types. For example:

  List<Customer> customers = new ArrayList<>();         // java 

Parametric polymorphism will be familiar if you’ve ever created a list of something in Java. It’s more commonly referred to as generics; by giving a generic type (like List) a parameterised type, we can treat it as a list yet still refer to its contents in a type-safe way. Generics are at play even if you don’t specify the parameterised type in Java. So although you can write the following:

  List collection = new ArrayList();                    // java 

You’re actually creating a generic List of type Object.

  List<Object> collection = new ArrayList<>();          // java 

  List<Object> collection = new ArrayList<>(); 

Class Generics

When you create a list of a specific type, Java will give you type safety on List methods that take parameters and return things of that type. For example, creating a list of customers but then trying to add an object that isn’t a customer will result in a compiler failure.

  List<Customer> customers = new ArrayList<>();   customers.add(new HockeyPuck());               // compiler failure 

The basic syntax for Scala will look familiar to Java developers; we just replace the chevrons with square brackets.

  List<Customer> customers = new ArrayList<>();     // java 

versus

  val customers: List[Customer] = List()            // scala 

Creating a list in Scala like this also shows that it has the equivalent of the diamond operator. Scala’s type inference can work out that customers is of type Customer without repeating the generics on the right-hand side.

  val customers: List[Customer] = List[Customer]()                                            ^                             // no need to repeat the type 

Method Generics

You can define generic parameters for methods in a similar way. To define a generic parameter to a method without defining a generic type for the whole class, you’d do something like this in Java, where the generic type is defined straight after the public keyword and used as the type of the parameter a:

  public <A> void add(A a)      // java 

versus this in Scala:

  def add[A](a: A)              // scala 

Stack Example

As a slightly more expanded example, in Java, we could generalise a Stack class. We could create an interface Stack with a generic type T and ensure that the push method takes a T and the pop method returns a T.

  // java   public interface Stack<T> {       void push(T t);       T pop();   } 

In Scala:

  // scala   trait Stack[T] {     def push(t: T)     def pop: T   } 

For demonstration purposes, we could implement Stack using a list in Java like this:

  // java   public class ListStack<T> implements Stack<T> {        private final List<T> elements = new ArrayList<>();        @Override       public void push(T t) {           elements.add(0, t);       }        @Override       public T pop() {           if (elements.isEmpty())               throw new IndexOutOfBoundsException();           return elements.remove(0);       }   } 

We “bind” a concrete type to the generic type when we supply the compiler with a concrete type. Adding String to the declaration below (on line 3) “binds” what was the generic type T to String. The compiler knows to replace T with String and we can start using strings as arguments and return types. If we try to add a number to the stack in our example, we’d get a compiler error.

1   // java 2   public static void main(String... args) { 3       Stack<String> stack = new ListStack<>(); 4       stack.push("C"); 5       stack.push("B"); 6       stack.push("A"); 7       stack.push(12);                           // compilation failure 8       String element = stack.pop()); 9   } 

Creating the ListStack in Scala is straightforward. It would look something like this:

  // scala   class ListStack[T] extends Stack[T] {      private var elements: List[T] = List()      override def push(t: T): Unit = {       elements = t +: elements     }      override def pop: T = {       if (elements.isEmpty) throw new IndexOutOfBoundsException       val head = elements.head       elements = elements.tail       head     }   } 

We still use a List to store the elements but because Scala’s List is immutable, in the push method, we replace the instance with a new list with the element prepended.

Similarly, when we pop, we have to replace the elements with all but the first element using the tail method. We get and return the first element using the head method. You’ll come across the idea of head (the first) and tail (the remainder) a lot in Scala and functional programming.

Binding to a concrete type is just the same. In the example below, I’m not declaring the stack variable with a type, so we need to give the compiler a hint about what kind of List it will be by adding the parameterised type on line 3.

1   // scala 2   def main(args: String*) { 3       val stack = new ListStack[String] 4       stack.push("C") 5       stack.push("B") 6       stack.push("A") 7       val element: String = stack.pop 8   } 

To demonstrate method-level generics, we could add a method to convert a Stack to an array. The thing to note here is that the generic is defined solely in terms of the method. A isn’t related to the generic type on the class definition.

  // java   public interface Stack<T> {       static <A> A[] toArray(Stack<A> stack) {           throw new UnsupportedOperationException();       }   } 

You define method-level generics in Scala in just the same way. Below, A is defined purely in scope for the method.

  // scala   object Stack {     def toArray[A](a: Stack[A]): Array[A] = {       ???     }   } 

Bounded Classes

Let’s go back to the list example with a generic type of Customer.

  List<Customer> customers = new ArrayList<>();         // java 

The contents of the list can be any Customer or subtype of Customer, so we can add a DiscountedCustomer to the list.

  List<Customer> customers = new ArrayList<>();   customers.add(new Customer("Bob Crispin", "15 Fleetwood Mack Road"));   customers.add(new DiscountedCustomer("Derick Jonar", "23 Woodfield Way")); 

Type erasure sees the collection as containing only Objects. The compiler will ensure that only things of the correct type go into the collection and use a cast on the way out. That means that anything you take out of our example can only be treated as a Customer.

If all you’ve done is override Customer behaviour in the DiscountedCustomer, you can treat the objects polymorphically and you wouldn’t see a problem. If you’ve added methods to DiscountedCustomer, however, you can’t call them without an unchecked cast.

  for (Customer customer : customers) {   // some may be DiscountedCustomers       // total will be the discounted total for any DiscountedCustomers       System.out.println(customer.getName() + " : " + customer.total());   }    DiscountedCustomer customer = (DiscountedCustomer) customers.get(0);   System.out.println(customer.getDiscountAmount()); 

To get round this limitation, you can force generic types to be bound to specific types within a class hierarchy. These are called bounded types.

Upper Bounds (<U extends T>)

You can restrict a generic type using extends or super in Java. These set the bounds of that type to either be a subtype or super-type. You use extends to set the upper bounds and super, the lower bounds. They can refer to a class or an interface.

We’ve actually already seen an example of setting an upper bound in the Sortable interface we wrote back in the . We created an interface describing generically that things can be sortable.

  // java   public interface Sortable<A extends Comparable<A>> extends Iterable<A> {       default public List<A> sort() {         List<A> list = new ArrayList<>();         for (A elements: this)             list.add(elements);         list.sort((first, second) -> first.compareTo(second));         return list;       }       // etc   } 

This does a couple of things with generics. It both defines a generic type A which must be a subclass of Comparable, and also says that implementing classes must be able to iterate over A. Comparable is the upper bound of A.

This is a good example of why bounded types are useful; because we want to define a general-purpose algorithm yet constrain the types enough that we can call known methods in that algorithm. In the example, we can’t implement the sort method unless the class has the compareTo method from Comparable and also is iterable.

We bind the type parameter when we implement the interface.

  public class Customers implements Sortable<Customer> { ... }      // java 

It’s at this point that the compiler can start treating A as a Customer and check that Customer implements Comparable and that Customers implements Iterable.

In Scala, it would look like this:

  // scala   trait Sortable[A <: Ordered[A]] extends Iterable[A] {     def sort: Seq[A] = {       this.toList.sorted     }   }    class Customers extends Sortable[Customer] { ... } 

The upper bound tells you what you can get out of a data structure. In our example, the sorting algorithm needed to get something out and use it as a Comparable; it enforces type safety. It’s set using extends in Java and <: in Scala.

Lower Bounds (<U super T>)

Setting a lower bound means using the super keyword in Java, something like the following:

  public class Example<T, U super T> { }            // java 

It’s saying that U has to be a super-type of T. It’s useful when we want to be flexible in our API design; you’ll see it a lot in Java library code or in libraries like Hamcrest. For example, suppose we have a class hierarchy to represent animals.

  // java   static class Animal {}   static class Lion extends Animal {}   static class Zebra extends Animal {} 

We might want collect the lions together in an enclosure.

  // java   List<Lion> enclosure = new ArrayList<>();   enclosure.add(new Lion());   enclosure.add(new Lion()); 

Let’s say that we want to sort the lions, and that we already have a helper method, similar to the Sortable interface, that sorts anything that is Comparable.

  // java   public static <A extends Comparable<A>> void sort(List<A> list) {       Collections.sort(list);   } 

To sort our lions, we just make them comparable and call the sort method.

  // java   static class Lion extends Animal implements Comparable<Lion> {       @Override       public int compareTo(Lion other) {           return this.age.compareTo(other.age);       }   }   sort(enclosure); 

Great, but what if we expand our enclosure and create a zoo?

  // java   List<Animal> zoo = new ArrayList<>();   zoo.add(new Lion());   zoo.add(new Lion());   zoo.add(new Zebra());   sort(zoo); 

It won’t compile, as we can’t compare zebras and lions.

It would make sense to implement Comparable in terms of Animals rather than the subtypes. That way, we can compare zebras to lions and presumably keep them away from each other.

If we make the Lion and Zebra Comparable with Animal, in theory we should be able to compare them with each other and themselves. However, if we move the comparable implementation up to the super-type (i.e., Animal implements Comparable and remove it from Lion), like this:

  // java   static class Animal implements Comparable<Animal> {       @Override       public int compareTo(Animal o) {           return 0;       }   }   static class Lion extends Animal { }   static class Zebra extends Animal { } 

…we get a compiler error when trying to sort the Lion enclosure (a List<Lion>).

  java: method sort in class Zoo cannot be applied to given types;     required: java.util.List<A>     found: java.util.List<Lion>     reason: inferred type does not conform to equality constraint(s)       inferred: Animal       equality constraints(s): Lion 

Otherwise known as:

  Inferred type 'Lion' for type parameter 'A' is not within its bounds;     should implement 'Lion' 

This is because the sort method (public static <A extends Comparable<A>> void sort(List<A> list)) expects a type that is comparable to itself, and we’re trying to compare it to something higher up the class hierarchy. When A is bound to a concrete type, for example Lion, Lion must also be Comparable against Lion. The problem is that we’ve just made it comparable to Animal.

  static class Lion extends Animal implements Comparable<Animal> { }                                                           ^ 

The zoo (a List<Animal>) can be sorted because the generic type of the collection is Animal.

We can fix it by adding ? super A to the signature of sort. This means that whilst A is still bound to a concrete type, say Lion, we’re now saying that it needs to be comparable to some super-type of Lion. As Animal is a super-type of Lion, it conforms and the whole thing compiles again.

  public static <A extends Comparable<? super A>> void sort(List<A> list) { } 

The upshot to all this is that our API method sort is much more flexible with a lower bound; without it, we wouldn’t be able to sort different types of animal.

In Scala, we can go through the same steps and create the Animal hierarchy.

  // scala   class Animal extends Comparable[Animal] {     def compareTo(o: Animal): Int = 0   }   class Lion extends Animal   class Zebra extends Animal 

Then we can create our sort method again and recreate our enclosure.

  // scala   def sort[A <: Comparable[A]](list: List[A]) = { } 

  // scala   def main(args: String*) {     var enclosure = List[Lion]()     enclosure = new Lion +: enclosure     enclosure = new Lion +: enclosure     sort(enclosure)                                  // compiler failure     var lion: Lion = enclosure(1)      var zoo = List[Animal]()     zoo = new Zebra +: zoo     zoo = new Lion +: zoo     zoo = new Lion +: zoo     sort(zoo)                                        // compiles OK     var animal: Animal = zoo(1)   } 

Like before, we get a compilation failure.

  Error:(30, 5) inferred type arguments [Lion] do not conform to method     sort's type parameter bounds [A <: Comparable[A]] sort(enclosure)                                                       ^ 

It correctly enforces that A must be of the same type but we’re treating A as both Lion and Animal. So just like before, we need to constrain the generic type with a lower bound.

You might be tempted to try a direct equivalent: using an underscore with >: A:

  def sort[A <: Comparable[_ >: A]](a: List[A]) = { }  // compiler failure 

But unfortunately, this would cause a compilation failure:

  failure: illegal cyclic reference involving type A 

It can’t cope with the reference to A; it sees it as cyclic. So you have to try and keep the relationship with the bounds but remove the cyclic reference. The answer is to define a new generic type U and write something like this:

  def sort[A <: Comparable[U], U >: A](list: List[A]) = { } 

So A must extend Comparable where the Comparable’s generic type U must itself be a super-type of A. This gets rid of the cyclic problem, but the compiler would still complain.

  inferred type arguments [Lion,Lion] do not conform to method sort's     type parameter bounds [A <: Comparable[U], U >: A] sort(enclosure)                                                        ^ 

It’s saying that the inferred types for the enclosure don’t match the constraints we’ve set. It has inferred the two types to both be Lion because the inference engine just doesn’t have enough to go on. We can give it a hint if we specify the types we know to be true. So just like a type witness in Java, we can clarify that we want the types to be Lion and Animal.

  var enclosure = List[Lion]()   enclosure = new Lion +: enclosure   enclosure = new Lion +: enclosure   sort[Lion, Animal](enclosure)         // add a type hint 

When you round-trip the byte code, the final version looks like this:

  // java   public <T extends Comparable<U>, U> void sort(List<U> a) { } 

Which is pretty much equivalent to the following:

  // java   public <T extends Comparable<?>> void sort(List<T> a) { } 

Which is pretty much the same as the Scala version:

  def sort[A <: Comparable[_]](list: List[A]) { }         // scala 

So it treats it like an unbounded type under the covers. That’s not quite true, in the sense that the Scala compiler is doing all the hard work here and leaves U unbounded because it’s doing all the type checking. In this example, it doesn’t make complete sense to round-trip from byte code to Java, as it’s not like-for-like, but it’s interesting to see what’s going on behind the scenes.

A lower bound tells you what you can put in a data structure. In our Lion example, using a lower bound means you can put more than just lions in the zoo. You use super in Java and greater than colon (>:) in Scala.

Wildcard Bounds (<? extends T, <? super T>)

We’ve already seen some examples of wildcards: the ? in Java and the _ in Scala.

Wildcards with an upper bound look like this:

  // java   void printAnimals(List<? extends Animal> animals) {       for (Animal animal : animals) {           System.out.println(animal);       }   } 

  // scala   def printAnimals(animals: List[_ <: Animal]) {     for (animal <- animals) {       println(animal)     }   } 

Wildcards with a lower bound look like this:

  // java   static void addNumbers(List<? super Integer> numbers) {       for (int i = 0; i < 100; i++) {           numbers.add(i);       }   } 

  // scala   def addNumbers(numbers: List[_ >: Int]) {     for (i <- 0 to 99) {       // ...     }   } 

Unbounded wildcards look like this in Java:

  List<?> list          // java 

…and like this in Scala:

  List[_]               // scala 

An unbounded wildcard refers to an unknown generic type. For example, printing elements of a list of unknown type will work with all lists. Just add upper- or lower-bound constraints to limit the options.

  // java   void printUnknown(List<?> list) {       for (Object element : list) {           System.out.println(element);       }   } 

  // scala   def printUnknown(list: List[_]) {     for (e <- list) {       val f: Any = e       println(f)     }   } 

Although the implementation can treat the elements as Object because everything is an object, you can’t add anything to a list of unknown type.

  // java   List<?> list = new ArrayList<String>();   list.add(new Object()); // compiler error 

The one exception is null.

  list.add(null); 

You get the same effect in Scala, where you can’t even create a list without a valid type:

  scala> val list = mutable.MutableList[_]()   <console>:7: error: unbound wildcard type          val list = mutable.MutableList[_]()                                   ^ 

You mainly use wildcards when you really don’t care about the type parameter, just any constraints on an upper or lower bounding, or when you can treat the type as an instance of Object or Any.

Multiple Bounds

Types can also have multiple bounds in both Java and Scala.

• Java is limited to multiple upper bounds.
• Java can’t set a lower and upper bound on types (so you can’t have a generic type extend one thing and also be a super-type to another).
• Scala can set a single lower and an upper bound, unlike Java.
• However, it can’t set multiple upper or lower bounds. Instead it can constrain bounds by also forcing you to extend traits.

Using multiple bounds, another way to express the constraints on the Animal sorting method would be to explicitly state that A must extend Animal and be comparable to Animal, using the & symbol in Java.

  // java   public static <A extends Animal & Comparable<Animal>> void sort(List<A> l) 

This sets two upper bounds to the generic type A in Java. You can’t set two upper bounds on A in Scala, but you can achieve the same effect by specifying that your bound must also extend certain traits.

  // scala   def sort[A <: Animal with Comparable[Animal]](list: List[A]) = { } 

Because we’re being more explicit, we can remove the type hints when calling the sort method.

  var enclosure = List[Lion]()   enclosure = new Lion +: enclosure   enclosure = new Lion +: enclosure   sort(enclosure) 

In Scala, you can also set both a lower and upper bound using >: and <:, like this:

  def example[A >: Lion <: Animal](a: A) = ()               // scala                     ^         ^                   lower     upper 

…where A must be a super-type of Lion and a subtype of Animal.

Variance

Without involving generics, a simple class B that extends A can be assigned to an instance of A; it is after all, an A as well as a B. Obviously, subtyping is only in one direction; the other way round, and you get a compiler failure.

Fig. 2.9. B extends A.

  // java   A a = new A();   B b = new B();   a = b;   b = a;                // compiler failure 

Generic classes, however, are not subclasses themselves just because their parameterised type may be. So, if B is a subclass of A, should List<B> be a subclass of List<A>? In Java List of B is not a subtype of List of A even though their parameterised types are.

Fig. 2.10. List<B> cannot extend List<A> in Java.

  // java   List<B> a = new ArrayList<>();   List<A> b = new ArrayList<>();    a = b;  // compiler failure 

This is where variance comes in. Variance describes how subtyping generic types (like lists or “container” types) relates to subtyping their parameterised type.

There are three types of subtype relationship described by variance:

1. Invariant
2. Covariant
3. Contravariant

Invariance

Java only supports one of the three for its generic types: all generic types in Java are invariant which is why we can’t assign a List<B> to a List<A> above. Invariant generic types don’t preserve the subtype relationship of their parameterised types.

However, you can vary the parameterised types when you use wildcards with methods and variables.

The invariant relationship between generic types says that there is no relationship even if their contents have a subtype relationship. You can’t substitute one for another. Java and Scala share syntax here, as defining any generic type in chevrons (Java) or square brackets (Scala) describes the type as invariant.

  public class List<T> { }          // java   class List[T] { }                 // scala 

Covariance

Covariant generic types preserve the relationship between two generic types as subtypes when their parameterised types are subtypes. So List<B> is a subtype of List<A> when a generic type is set up as covariant. Java doesn’t support covariance. Scala supports covariant generic types by using a + when you define a generic class.

  class List[+T] { } 

Contravariance

Contravariance reverses a subtype relationship. So if A is contravariant, List<A> is also a List<B>; it’s a subtype. The relationship of the parameterised types are reversed for their generic types. Java doesn’t support contravariant but in Scala you just add a - to the generic type definition.

  class List[-T] 

Variance Summary

In summary, invariant generic types are not related, regardless of the relationship of their parameterised types. Covariant types maintain the subtype relationship of their parameterised types, and contravariant types reverse it.

The syntax for each is summarised below.