Intuitively explain why `List` is covariant but `Array` is invariant?

Question

From List[+T] I understand a list of dogs is also a list of animals which aligns perfectly with the intuition. From def :: [B >: A](elem: B): List[B] I understand I can add an animal (B, less specific) to a list of dogs (A, more specific) and will get back a list of animals. This aligns with the intuition as well. So basically List is good.

From Array[T] I understand an array of dogs is not (could not be used in place of a) an array of animals which is rather counterintuitive. An array of dogs is indeed an array of animals as well but obviously Scala disagrees.

I was hoping someone intuitively explain why Array in invariant, preferably in terms of dogs (or cats).

There is Why are Arrays invariant, but Lists covariant? but I'm looking for a more intuitive explanation that doesn't (heavily) involve the type system.

Related to Why is Scala's immutable Set not covariant in its type?

My own hunch is that "An `Array` of dogs in indeed an `Array` on animals" might not hold for all circumstances, specially when it is not used in a read-only position but I can't put it intuitively. — Ashkan Kh. Nazary, Dec 07 '20 at 14:51
AFAIK the reasons are pretty much historic ones - when Java introduced generics with covariant arrays, people realized that they could explode (remember, they are mutable). E.g. you could simply take an array of apples, assign it to a variable of type Array[Fruit], and then put bananas in it. This throws at runtime. That's why mutable stuff like arrays is better kept invariant, and immutable collections like scala List are okay (and indeed useful) to be covariant. — slouc, Dec 07 '20 at 14:57
@slouc: " when Java introduced generics with covariant arrays, people realized that they could explode" – 1) Covariant arrays in Java are broken independent of generics.They were already broken in Java 1, long before generics in Java 5. 2) The rules about safe co- and contravariance were known long before Java introduced covariant arrays. If people only realized they could explode when Java introduced them, then they were either ignorant or stupid. If you look at the names of the people who designed Java, it should be pretty clear they were neither of those things, instead they made a … — Jörg W Mittag, Dec 07 '20 at 20:32
… design decision to sacrifice safety for programmer convenience, *knowing full well covariant arrays are unsafe*. — Jörg W Mittag, Dec 07 '20 at 20:33

Luis Miguel Mejía Suárez · Answer 1 · 2020-12-07T15:15:18.863

The reason is pretty simple. Is because Array is a mutable collection. Remember there is a very easy rule of thumb about variance.
If it produces something it can be covariant.
If it consumes something it can be contravariant.
That is why Functions are contravariant on input and covariant on output.

Because Arrays are mutable they are in fact both producers and consumers of something, so they have to be invariant.

Let me show why it has to be like that with a simple example.

// Assume this compiles, it doesn't.
final class CovariantArray[+A] (arr: Array[A]) {
  def length: Int = arr.length
  def apply(i: Int): A = arr(i)
  def update(i: Int, a: A): Unit = {
    arr(i) = a
  }
}

sealed trait Pet
final case class Dog(name: String) extends Pet
final case class Cat(name: String) extends Pet

val myDogs: CovariantArray[Dog] = CovariantArray(Dog("Luna"), Dog("Lucas"))
val myPets: CovariantArray[Pet] = myDogs // Valid due covariance.
val myCat: Cat = Cat("Milton")
myPets(1) = myCat // Valid because Liskov.
val myDog: Dog = myDogs(1) // Runtime error Cat is not Dog.

You can reproduce this error in Java using normal Arrays, Scala will simply not let you compile.

Intuitively explain why `List` is covariant but `Array` is invariant?

1 Answers1