Why are Arrays invariant, but Lists covariant?

Question

E.g. why does

val list:List[Any] = List[Int](1,2,3)

work, but

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

fails (because arrays are invariant). What is the desired effect behind this design decision?

Answer 1

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

Answer 2

This is because lists are immutable and arrays are mutable.

Answer 3

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]).

Answer 4

The difference is that Lists are immutable while Arrays are mutable.

To understand why mutability determines variance, consider making a mutable version of List - let's call it MutableList. We'll also make use of some example types: a base class Animal and 2 subclasses named Cat and Dog.

trait Animal {
  def makeSound: String
}

class Cat extends Animal {
  def makeSound = "meow"
  def jump = // ...
}

class Dog extends Animal {
  def makeSound = "bark"
}

Notice that Cat has one more method (jump) than Dog.

Then, define a function that accepts a mutable list of animals and modifies the list:

def mindlessFunc(xs: MutableList[Animal]) = {
  xs += new Dog()
}

Now, horrible things will happen if you pass a list of cats into the function:

val cats = MutableList[Cat](cat1, cat2)
val horror = mindlessFunc(cats)

If we were using a careless programming language, this will be ignored during compilation. Nevertheless, our world will not collapse if we only access the list of cats using the following code:

cats.foreach(c => c.makeSound)

But if we do this:

cats.foreach(c => c.jump)

A runtime error will occur. With Scala, writing such code is prevented, because the compiler will complain.