Covariant containers

[subtyping] [variance]

If there is a subtyping between two types, say that every Car\n{Car} is a Vehicle\n{Vehicle}, then it is natural to extend this subtyping to container types, to say that a List[Car]\n{List}[\n{Car}] is also a List[Vehicle]\n{List}[\n{Vehicle}].

However, this is only sound for immutable List\n{List} types. If List\n{List} is mutable, then a List[Vehicle]\n{List}[\n{Vehicle}] is something into which I can insert a Bus\n{Bus}. If every List[Car]\n{List}[\n{Car}] is automatically a List[Vehicle]\n{List}[\n{Vehicle}], then you can end up with buses in your list of cars.

This problem occurs with arrays in Java:

class Vehicle {}
class Car extends Vehicle {}
class Bus extends Vehicle {}
public class App {
  public static void main(String[] args) {
    Car[] c = { new Car() };
    Vehicle[] v = c;
    v[0] = new Bus(); // crashes with ArrayStoreException

The solution is to keep track of variance (how subtyping of type parameters affects subtyping of the whole type). There are two approaches:

  • Use-site variance is used in Java (for types other than arrays): a List<Car> can never be converted to a List<Vehicle>, but can be converted to a List<? extends Vehicle>. The elements of a List<? extends Vehicle> are known to be Vehicles, but an arbitrary Vehicle cannot be inserted into such a list. Each use of List specifies how the parameter is allowed to vary.

  • Declaration-site variance is used in Scala (although use-site variance is also available). This means that the List type can be defined as List[+T] if immutable, making every List[Car] automatically a List[Vehicle]. However, if List is mutable, it must be defined as List[T], which disables these conversions.