Covariance, Contravariants, Invariants, Help!

The other day, I made a really dumb Tweet about Java collections. I tried to come up with an excuse for it, but there really was none. This was, um, inspired by a proposal to simplify bounded wildcard syntax in Java. Perhaps my mistake is proof that such a simplification is needed, but probably not. To make amends for my mistake, and in the hope that others will be wiser than I, here is another way of looking at this issue.

Collections in Java are invariant, by default. That means that if you define a method to take a List of X, then you have to provide a List of X. List of Y, where Y is a subclass of X, will not work. Here is an example:

public static void invariance(List<Number> nums){
    nums.add(1.1D);                              
    for (Number n : nums){                       
        System.out.println(n.doubleValue());     
    }                                            
}                                                

Invariance implies implies problems with the following code:

List<Integer> ints = Arrays.asList(1,2,3);
invariance(objs); // won't compile
List<Object> objs = new ArrayList<Object>(ints);
invariance(ints); // won't compile

You have go to match things exactly if you want to call an invariant method. Sometimes this is too restrictive, but not in this case. In the example above, you both read and write from the collection. If we could pass in the List of Integers, then adding a double to it would be invalid. If we could pass in a List of Objects, then calling the doubleValue method would be invalid. The only option here is invariance.
If you only need to read from the collection, then you can have covariance:

public static void covariance(List<? extends Number> nums){
    for (Number n : nums){
        System.out.println(n.doubleValue());
    }
}

Now you can pass in anything that adheres to the API of Number, i.e. anything that is a subclass of Number.

List<Integer> ints = Arrays.asList(1,2,3);
covariance(ints); // compiles!
List<Object> objs = new ArrayList<Object>(ints);
covariance(objs); // won't compile

Not that you still cannot pass in the List of Objects. They don't have a doubleValue method, so it would be trouble if the compiler let them in. Now in the covariant method, if you tried to add a double to the list, the compile will not let you. You might protest and say "a Double is a subclass of Number, so I should be able to add it to a collection of objects that are a subclass of Number." This is shortsighted. You don't know exactly what kind of collection was passed in, just that everything in the collection should implement a particular interface. It could be a List of Integer or a List of Double or a List of Byte. So you cannot just add to the collection. For covariance, you want methods that do not mutate the state of the collection. Now technically, you could remove objects from the collection and the compiler will let you get away with it. Still it might helpful to think of covariance as read-only.

What if you want to add things to the collection? That is where contravariance comes in. Here is an example:

public static void contravariance(List<? super Number> nums){
    nums.add(1.1D);
}

Here I say that want anything that is a superclass of Number. In other words, I am willing to say that I cannot be anymore specific about the elements in the collection than they are Numbers.

List<Object> objs = new ArrayList<Object>(ints);
contravariance(objs); // compiles!
List<Integer> ints = Arrays.asList(1,2,3);
contravariance(ints); // won't compile

Now I can send in a List of Objects, and since Object is a superclass of Number, the compiler is happy. If I send in a List of Integer, the compiler will stop me. I could try a List of Double too, and it will still stop me. My collection needs to very permissive, so that my contravariant method can add to it.

Neal Gafter's proposal to simplify some of this, looks like:

public static void covariance(List<out Number> nums){
    for (Number n : nums){
        System.out.println(n.doubleValue());
    }
}

public static void contravariance(List<in Number> nums){
    nums.add(1.1D);
}

I think this is intuitive. If I only want to take things out, I want covariance. If I want to put things in, I want contravariance. One of the things that made me re-think (and maybe confuse me) this subject was how things work in Scala. There you use + and - for covariance and contravariance, respectively. By default, a List in Scala is covariant. However, Lists are immutable. Adding to a Scala List produces a new List, it does not mutate the original List. The mutable cousin of List, like ArrayBuffer, is invariant, just like a List in Java.