Why are Arrays invariant, but Lists covariant?

The normal answer to give is that mutability combined with covariance would break type safety. For collections, this can be taken as a fundamental truth. But the theory actually applies to any generic type, not just collections like List and Array, and we don't have to try and reason about mutability at all.

The real answer has to do with the way function types interact with subtyping. The short story is if a type parameter is used as a return type, it is covariant. On the other hand, if a type parameter is used as an argument type, it is contravariant. If it is used both as a return type and as an argument type, it is invariant.

Let's look at the documentation for Array[T]. The two obvious methods to look at are for the ones for lookup and update:

def apply(i: Int): T
def update(i: Int, x: T): Unit

In the first method T is a return type, while in the second T is an argument type. The rules of variance dictate that T must therefore be invariant.

We can compare the documentation for List[A] to see why it is covariant. Confusingly, we would find these methods, which are analogous to the methods for Array[T]:

def apply(n: Int): A
def ::(x: A): List[A]

Since A is used as both a return type and as an argument type, we would expect A to be invariant just like T is for Array[T]. However, unlike with Array[T], the documentation is lying to us about the type of ::. The lie is good enough for most calls to this method, but isn't good enough to decide the variance of A. If we expand the documentation for this method and click on "Full Signature", we are shown the truth:

def ::[B >: A](x: B): List[B]

So A does not actually appear as an argument type. Instead, B (which can be any supertype of A) is the argument type. This does not place any restriction on A, so it really can be covariant. Any method on List[A] which has A as an argument type is a similar lie (we can tell because these methods are marked as [use case]).

This is because lists are immutable and arrays are mutable.

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