Why Are Arrays Covariant But Generics Are Invariant

Why are arrays covariant but generics are invariant?

Via wikipedia:

Early versions of Java and C# did not include generics (a.k.a. parametric polymorphism).

In such a setting, making arrays invariant rules out useful polymorphic programs.
For example, consider writing a function to shuffle an array, or a function that tests two arrays for equality using the Object.equals method on the elements. The implementation does not depend on the exact type of element stored in the array, so it should be possible to write a single function that works on all types of arrays. It is easy to implement functions of type

boolean equalArrays (Object[] a1, Object[] a2);
void shuffleArray(Object[] a);

However, if array types were treated as invariant, it would only be possible to call these functions on an array of exactly the type Object[]. One could not, for example, shuffle an array of strings.

Therefore, both Java and C# treat array types covariantly. For instance, in C# string[] is a subtype of object[], and in Java String[] is a subtype of Object[].

This answers the question "Why are arrays covariant?", or more accurately, "Why were arrays made covariant at the time?"

When generics were introduced, they were purposefully not made covariant for reasons pointed out in this answer by Jon Skeet:

No, a List<Dog> is not a List<Animal>. Consider what you can do with a List<Animal> - you can add any animal to it... including a cat. Now, can you logically add a cat to a litter of puppies? Absolutely not.

// Illegal code - because otherwise life would be Bad
List<Dog> dogs = new List<Dog>();
List<Animal> animals = dogs; // Awooga awooga
animals.add(new Cat());
Dog dog = dogs.get(0); // This should be safe, right?

Suddenly you have a very confused cat.

The original motivation for making arrays covariant described in the wikipedia article didn't apply to generics because wildcards made the expression of covariance (and contravariance) possible, for example:

boolean equalLists(List<?> l1, List<?> l2);
void shuffleList(List<?> l);

Why are Arrays invariant, but Lists covariant?

Because it would break type-safety otherwise.
If not, you would be able to do something like this:

val arr:Array[Int] = Array[Int](1,2,3)
val arr2:Array[Any] = arr
arr2(0) = 2.54

and the compiler can't catch it.

On the other hand, lists are immutable, so you can't add something that is not Int

Java covariant array bad?

Very simple.

String strings[] = {"Broken","Type", "system"};
Object objects[] = strings;

objects[0] = 5; // compiles fine, but throws ArrayStoreException at runtime

Covariant types are not bad as long as you as you take things out, but the moment you put things in, the whole thing breaks.
Imagine you have a method takes an Object[] as a parameter.

fn(Object[]a){
...   
}

wouldn't it be nice to be able to call it with a String[]?

 String[] s = {"I","didn't","know","that","this","was","broken"}
 fn(s);

Well, it sounds natural to be able to do so, especially in the early days when we didn't have generics in the language. And all this works fine as long as nothing get mutated, and Java doesn't provide any mechanism to guarantee that.

You should always favour Lists over arrays, because Lists use generics which are invariant.

Why are generics said to be invariant when ? extends Klass is allowed?

List<? extends Exception> k = new ArrayList<NumberFormatException>();

this means that the list can take the subtype of Exception

Not quite. You can assign to k a List -- or any of its subtype, as you have ArrayList -- in this case, of any subtype of Exception.

But you cannot add to k any subtype of Exception, or anything for that matter, because k is a List of some unknown subtype of Exception. For example,

k.add(new NumberFormatException());

would give an error.

Retrieval is also restricted to the known type:

NumberFormatException e1 = k.get(0); // error
Exception e2 = k.get(0); // ok, anything in k must be an Exception
NumberFormatException e3 = (NumberFormatException) k.get(0); // ok, but the usual downcast issues exist

Does Java array covariance violate Liskov Substitution Principle?

Did it violate the LSP in any way?

Yes.

There doesn't seem to be a clear violation.

Your own example is a violation. The following code works fine:

Animal[] animals = new Animal[1];
animals[0] = new Cat();

But if now replace the Animal[] with its subtype Dog[], the code no longer works (that is, it causes an exception when it didn't previously). So the type Dog[] can't be used everywhere where its supertype Animal[] can be used and that violates the LSP.

To put this in the LSP's wording: If we consider the property "new Cat() can be assigned as an element", the type Animal[] fulfils this property, but its subtype Dog[] does not.

---

Related Topics