Problem in understanding generic collections in Java

Question

Can someone please explain why the following code is not allowed:

List<Number> l = new ArrayList<Integer>();

But I can do this:

Number[] a = new Integer[10];

I am learning generics and don't understand this. Why does the type on the left be exactly the type from the right and child types are not allowed?

TIA!

Answer 1

The reasons for this are based on how Java implements generics.

An Arrays Example

With arrays you can do this (arrays are covariant as others have explained)

Integer[] myInts = {1,2,3,4};
Number[] myNumber = myInts;

But, what would happen if you try to do this?

Number[0] = 3.14; //attempt of heap pollution

This last line would compile just fine, but if you run this code, you could get an ArrayStoreException. Because you’re trying to put a double into an integer array (regardless of being accessed through a number reference).

This means that you can fool the compiler, but you cannot fool the runtime type system. And this is so because arrays are what we call reifiable types. This means that at runtime Java knows that this array was actually instantiated as an array of integers which simply happens to be accessed through a reference of type Number[].

So, as you can see, one thing is the actual type of the object, an another thing is the type of the reference that you use to access it, right?

The Problem with Java Generics

Now, the problem with Java generic types is that the type information is discarded by the compiler and it is not available at run time. This process is called type erasure. There are good reason for implementing generics like this in Java, but that's a long story, and it has to do with binary compatibility with pre-existing code.

But the important point here is that since, at runtime there is no type information, there is no way to ensure that we are not committing heap pollution.

For instance,

List<Integer> myInts = new ArrayList<Integer>();
myInts.add(1);
myInts.add(2);

List<Number> myNums = myInts; //compiler error
myNums.add(3.14); //heap polution

If the Java compiler does not stop you from doing this, the runtime type system cannot stop you either, because there is no way, at runtime, to determine that this list was supposed to be a list of integers only. The Java runtime would let you put whatever you want into this list, when it should only contain integers, because when it was created, it was declared as a list of integers.

As such, the designers of Java made sure that you cannot fool the compiler. If you cannot fool the compiler (as we can do with arrays) you cannot fool the runtime type system either.

As such, we say that generic types are non-reifiable.

Evidently, this would hamper polymorphism. Consider the following example:

static long sum(Number[] numbers) {
   long summation = 0;
   for(Number number : numbers) {
      summation += number.longValue();
   }
   return summation;
}

Now you could use it like this:

Integer[] myInts = {1,2,3,4,5};
Long[] myLongs = {1L, 2L, 3L, 4L, 5L};
Double[] myDoubles = {1.0, 2.0, 3.0, 4.0, 5.0};

System.out.println(sum(myInts));
System.out.println(sum(myLongs));
System.out.println(sum(myDoubles));

But if you attempt to implement the same code with generic collections, you will not succeed:

static long sum(List<Number> numbers) {
   long summation = 0;
   for(Number number : numbers) {
      summation += number.longValue();
   }
   return summation;
}

You would get compiler erros if you try to...

List<Integer> myInts = asList(1,2,3,4,5);
List<Long> myLongs = asList(1L, 2L, 3L, 4L, 5L);
List<Double> myDoubles = asList(1.0, 2.0, 3.0, 4.0, 5.0);

System.out.println(sum(myInts)); //compiler error
System.out.println(sum(myLongs)); //compiler error
System.out.println(sum(myDoubles)); //compiler error

The solution is to learn to use two powerful features of Java generics known as covariance and contravariance.

Covariance

With covariance you can read items from a structure, but you cannot write anything into it. All these are valid declarations.

List<? extends Number> myNums = new ArrayList<Integer>();
List<? extends Number> myNums = new ArrayList<Float>()
List<? extends Number> myNums = new ArrayList<Double>()

And you can read from myNums:

Number n = myNums.get(0); 

Because you can be sure that whatever the actual list contains, it can be upcasted to a Number (after all anything that extends Number is a Number, right?)

However, you are not allowed to put anything into a covariant structure.

myNumst.add(45L); //compiler error

This would not be allowed, because Java cannot guarantee what is the actual type of the object in the generic structure. It can be anything that extends Number, but the compiler cannot be sure. So you can read, but not write.

Contravariance

With contravariance you can do the opposite. You can put things into a generic structure, but you cannot read out from it.

List<Object> myObjs = new List<Object();
myObjs.add("Luke");
myObjs.add("Obi-wan");

List<? super Number> myNums = myObjs;
myNums.add(10);
myNums.add(3.14);

In this case, the actual nature of the object is a List of Objects, and through contravariance, you can put Numbers into it, basically because all numbers have Object as their common ancestor. As such, all Numbers are objects, and therefore this is valid.

However, you cannot safely read anything from this contravariant structure assuming that you will get a number.

Number myNum = myNums.get(0); //compiler-error

As you can see, if the compiler allowed you to write this line, you would get a ClassCastException at runtime.

Get/Put Principle

As such, use covariance when you only intend to take generic values out of a structure, use contravariance when you only intend to put generic values into a structure and use the exact generic type when you intend to do both.

The best example I have is the following that copies any kind of numbers from one list into another list. It only gets items from the source, and it only puts items in the destiny.

public static void copy(List<? extends Number> source, List<? super Number> destiny) {
    for(Number number : source) {
        destiny.add(number);
    }
}

Thanks to the powers of covariance and contravariance this works for a case like this:

List<Integer> myInts = asList(1,2,3,4);
List<Integer> myDoubles = asList(3.14, 6.28);
List<Object> myObjs = new ArrayList<Object>();

copy(myInts, myObjs);
copy(myDoubles, myObjs);

Answer 2

ArrayList<Integer> is a subclass of List<? extends Number> not a subclass of List<Number>. This is because generics are invariant in that for any two distinct types Type1 and Type2, List<Type1> is not a subtype neither a supertype of List<Type2>, therefore a bounded wildcard type is used, as in List<? extends Number>, to deal with these sort of situations.

Answer 3

This is a common problem for people trying to understand Generics in Java. For a detailed explanation, read the wiki article about covariance and contravariance. As your code sample demonstrates, Java's generic classes are neither covariant nor contravariant.

Here's a simpler, more intuitive explanation. Let's say

List<Number> l = new ArrayList<Integer>();

was a valid declaration. Then, through polymorphism, you could give l to a function declared as

public void foo(List<Number> list) {
    l.add(new Double(42.0));
}

According to polymorphism, foo(l) should be a perfectly valid call (Double is a Number, after all), but you'd be adding a Double to an ArrayList<Integer>, which understandable violates type safety.

Answer 4

It's because arrays support covariance in a simple but less type-safe way. You can use covariance in the first case by writing:

List<? extends Number> l = new ArrayList<Integer>();

Here's the reason it isn't allowed... suppose your original line worked. Then you could write:

ArrayList<Integer> integers = new ArrayList<Integer>();
// Invalid code - fortunately
List<Number> numbers = integers;
numbers.add(new BigDecimal(5.5));
Integer x = integer.get(0); // Bang!

Arrays "know" their real types, unlike generic collections - so the equivalent array example would fail differently:

// All valid code... just not as type-safe as it looks
Integer[] integers = new Integer[1];
Number[] numbers = integers;
numbers[0] = new BigDecimal(5.5);