Why are arrays covariant but generics are invariant?

Question

From Effective Java by Joshua Bloch,

1. Arrays differ from generic type in two important ways. First arrays are covariant. Generics are invariant.

2. Covariant simply means if X is subtype of Y then X[] will also be sub type of Y[]. Arrays are covariant As string is subtype of Object So

   String[] is subtype of Object[]

   Invariant simply means irrespective of X being subtype of Y or not ,

    List<X> will not be subType of List<Y>.
   

My question is why the decision to make arrays covariant in Java? There are other SO posts such as Why are Arrays invariant, but Lists covariant?, but they seem to be focussed on Scala and I am not able to follow.

Arabel

Isn't this because generics were added later? – Bifacial

i think comparing between arrays and collections is unfair, Collections use arrays in the background !! – Unconditional

@EL-conteDe-monteTereBentikh Not all collections, for example LinkedList. – Inboard

@PaulBellora i know that Maps are different than Collection implementers, but i read in the SCPJ6 that Collections generally relied on arrays !! – Unconditional

Because there is no ArrayStoreException; when inserting wrong element in Collection where as array has it. So Collection can find this only at retrieval time and that too because of casting. So generics will ensure solving this issue. – Entero

I read somewhere that even this decision with arrays was a bad decision, regretted later. – Divisible

Answer 1

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);

Inboard

yes, Arrays allows for polymorphic behavior, however, it does introduce runtime excpetions (unlike compile-time exceptions with generics). eg : Object[] num = new Number[4]; num[1]= 5; num[2] = 5.0f; num[3]=43.4; System.out.println(Arrays.toString(num)); num[0]="hello"; – Arabel

That's correct. Arrays have reifiable types and throw ArrayStoreExceptions as needed. Clearly this was considered a worthy compromise at the time. Contrast that with today: many regard array covariance as a mistake, in retrospect. – Inboard

Why do "many" regard it a mistake? It's far more useful than not having array covariance. How often have you seen an ArrayStoreException; they are quite rare. The irony here is unforgivable imo... among the very worst mistakes ever made in Java is use-site variance aka wildcards. – Cristalcristate

@ScottMcKinney: "Why do "many" regard it a mistake?" AIUI, this is because array covariance requires dynamic type tests on all array assignment operations (although compiler optimizations can perhaps help?) which can cause a significant runtime overhead. – Algolagnia

Thanks, Dominique, but from my observation it appears the reason "many" regard it a mistake is more along the lines of parroting what a few others have said. Again, taking a fresh look at array covariance, it's far more useful than damaging. Again, the actual BIG mistake Java made was use-site generic variance via wildcards. That has caused more problems than I think "many" want to admit. – Cristalcristate

Arrays are reified, Generics are erased(Generic are compile-time only). Basically, invariance is preferable to covariance for generics. – Walhalla

Answer 2

The reason is that every array knows its element type during runtime, while generic collection doesn't because of type erasure.

For example:

String[] strings = new String[2];
Object[] objects = strings;  // valid, String[] is Object[]
objects[0] = 12; // error, would cause java.lang.ArrayStoreException: java.lang.Integer during runtime

If this was allowed with generic collections:

List<String> strings = new ArrayList<String>();
List<Object> objects = strings;  // let's say it is valid
objects.add(12);  // invalid, Integer should not be put into List<String> but there is no information during runtime to catch this

But this would cause problems later when someone would try to access the list:

String first = strings.get(0); // would cause ClassCastException, trying to assign 12 to String

Associate

I think Paul Bellora answer is more appropriate as he comments on WHY Arrays are covariant. If arrays were made invariant, then its fine. you would have type erasure with it. The main reason for type Erasure property is for backward compatibility correct? – Arabel

@user2708477, yes, type erasure was introduced because of backward compatibility. And yes, my answer tries to answer the question in the title, why generics are invariant. – Associate

The fact that arrays know their type means that while covariance allows code to ask to store something into an array where it won't fit--it doesn't mean such a store will be allowed to take place. Consequently, the level of danger introduced by having arrays be covariant is much less than it would be if they didn't know their types. – Consignment

@supercat, correct, what I wanted to point out is that for generics with type erasure in place, covariance could not have been implemented with the minimal safety of runtime checks – Associate

I personally think this answer provides the right explanation as to why Arrays are covariant when Collections couldn't be. Thanks! – Rebellious

-1 because question was why this design decision was made ? but first line of your answer only states the design decision itself and never really answers why it was made. – Summitry

@Summitry I think the question is about why arrays and generics differ in terms of variance. In my opinion generics not being covariant is more suprising that's why I focused on them in my answer. – Associate

Answer 3

May be this help:-

Generics are not covariant

Arrays in the Java language are covariant -- which means that if Integer extends Number (which it does), then not only is an Integer also a Number, but an Integer[] is also a Number[], and you are free to pass or assign an Integer[] where a Number[] is called for. (More formally, if Number is a supertype of Integer, then Number[] is a supertype of Integer[].) You might think the same is true of generic types as well -- that List<Number> is a supertype of List<Integer>, and that you can pass a List<Integer> where a List<Number> is expected. Unfortunately, it doesn't work that way.

It turns out there's a good reason it doesn't work that way: It would break the type safety generics were supposed to provide. Imagine you could assign a List<Integer> to a List<Number>. Then the following code would allow you to put something that wasn't an Integer into a List<Integer>:

List<Integer> li = new ArrayList<Integer>();
List<Number> ln = li; // illegal
ln.add(new Float(3.1415));

Because ln is a List<Number>, adding a Float to it seems perfectly legal. But if ln were aliased with li, then it would break the type-safety promise implicit in the definition of li -- that it is a list of integers, which is why generic types cannot be covariant.

Izzo

For Arrays, you get an ArrayStoreException at runtime. – Bifacial

my question is WHY is Arrays made covariant. as Sotirios mentioned, with Arrays one would get ArrayStoreException at runtime, if Arrays were made invariant, then we could detect this error at compile time itself correct? – Arabel

@eagertoLearn: One major semantic weakness of Java is that it nothing in its type system can distinguish "Array which holds nothing but derivatives of Animal, which doesn't have to accept any items received from elsewhere" from "Array which must contain nothing but Animal, and must be willing to accept externally-supplied references to Animal. Code which needs the former should accept an array of Cat, but code which needs the latter shouldn't. If the compiler could distinguish the two types, it could provide compile-time checking. Unfortunately, the only thing distinguishing them... – Consignment

...is whether code actually tries to store anything into them, and there's no way to know that until runtime. – Consignment

Answer 4

An important feature of parametric types is the ability to write polymorphic algorithms, i.e. algorithms that operate on a data structure regardless of its parameter value, such as Arrays.sort().

With generics, that's done with wildcard types:

<E extends Comparable<E>> void sort(E[]);

To be truly useful, wildcard types require wildcard capture, and that requires the notion of a type parameter. None of that was available at the time arrays were added to Java, and makings arrays of reference type covariant permitted a far simpler way to permit polymorphic algorithms:

void sort(Comparable[]);

However, that simplicity opened a loophole in the static type system:

String[] strings = {"hello"};
Object[] objects = strings;
objects[0] = 1; // throws ArrayStoreException

requiring a runtime check of every write access to an array of reference type.

In a nutshell, the newer approach embodied by generics makes the type system more complex, but also more statically type safe, while the older approach was simpler, and less statically type safe. The designers of the language opted for the simpler approach, having more important things to do than closing a small loophole in the type system that rarely causes problems. Later, when Java was established, and the pressing needs taken care of, they had the resources to do it right for generics (but changing it for arrays would have broken existing Java programs).

Befool

Answer 5

Arrays are covariant for at least two reasons:

• It is useful for collections that hold information which will never change to be covariant. For a collection of T to be covariant, its backing store must also be covariant. While one could design an immutable T collection which did not use a T[] as its backing store (e.g. using a tree or linked list), such a collection would be unlikely to perform as well as one backed by an array. One might argue that a better way to provide for covariant immutable collections would have been to define a "covariant immutable array" type they could use a backing store, but simply allowing array covariance was probably easier.

• Arrays will frequently be mutated by code which doesn't know what type of thing is going to be in them, but won't put into the array anything which wasn't read out of that same array. A prime example of this is sorting code. Conceptually it might have been possible for array types to include methods to swap or permute elements (such methods could be equally applicable to any array type), or define an "array manipulator" object which hold a reference to an array and one or more things that had been read from it, and could include methods to store previously-read items into the array from which they had come. If arrays were not covariant, user code would not be able to define such a type, but the runtime could have included some specialized methods.

The fact that arrays are covariant may be viewed as an ugly hack, but in most cases it facilitates the creation of working code.

Consignment

The fact that arrays are covariant may be viewed as an ugly hack, but in most cases it facilitates the creation of working code. -- good point – Arabel

Answer 6

I think they made a wrong decision at the first place that made array covariant. It breaks the type safety as it described here and they got stuck with that because of backward compatibility and after that they tried to not make the same mistake for generic. And that's one of the reasons that Joshua Bloch prefers lists to arra ys in Item 25 of book "Effective Java(second edition)"

Gramineous

Josh Block was the author of Java's collections framework (1.2), and the author of Java's generics (1.5). So the guy who built the generics that everyone complains about is also coincidentally the guy who wrote the book saying that they are the better way to go? Not a huge surprise! – Icebound

Answer 7

Generics are invariant: from JSL 4.10:

...Subtyping does not extend through generic types: T <: U does not imply that C<T> <: C<U> ...

and a few lines further, JLS also explains that
Arrays are covariant (first bullet):

4.10.3 Subtyping among Array Types

Mole

Answer 8

My take: When code is expecting an array A[] and you give it B[] where B is a subclass of A, there's only two things to worry about: what happens when you read an array element, and what happens if you write it. So it's not hard to write language rules to ensure that type safety is preserved in all cases (the main rule being that an ArrayStoreException could be thrown if you try to stick an A into a B[]). For a generic, though, when you declare a class SomeClass<T>, there can be any number of ways T is used in the body of the class, and I'm guessing it's just way too complicated to work out all the possible combinations to write rules about when things are allowed and when they aren't.

Lebna