Does variance make sense in a fully immutable language?

Question

In many OOP programming languages, types can be made co-, contra- or in- variant. Most (if not all of these languages) are able to let variables be mutated in place, i.e. they are not fully immutable languages.

I've seen in this SO answer that, in Scala at least, neither a covariant type can appear in a contravariant position nor a contravariant type can appear in a covariant position.

The problem I have with this answer (and in fact with all similar examples I ever found on the internet) is that it relies on mutability to show evidence of the above fact.

So my questions are:

• does even the concept of variance make sense in an immutable environment?
• if so, then could every type of a speculative fully immutable OOP language (like, all of them) be made covariant, regardless of where they are used (i.e. as function input types / function output types)?

Answer 1

does even the concept of variance make sense in an immutable environment?

Yes; presence of subtyping is independent of immutability.

could every type of a speculative fully immutable OOP language (like, all of them) be made covariant, regardless of where they are used (i.e. as function input types / function output types)?

As a simple demonstration why function input types can't be covariant, with no mutability involved (using Scala syntax):

val f: Int => Int = x => 2 * x
val g: Any => Int = f  // allowed by covariance
g("")  // what should this do?

The rule is still the same: "producer extends (covariant), consumer super (contravariant)". And a function is a consumer of its input type.

Answer 2

Variance has nothing to do with mutability. It appears at the intersection of parametric polymorphism and subtyping.

The oldest example of variance is actually an example that comes out of functional programming, namely the question: when is a function type a subtype of another function type?

And it turns out that a function type is a subtype of another function type if its inputs are at least as general and its outputs at least as specific as the supertype.

In other words, functions are contravariant in their inputs and covariant in their outputs.

Answer 3

Suppose you have a function that takes a list/array and a comparison function and returns a new one with the items sorted. If I have a list of Integers objects, I need a function that can sort integers: compare(a,b). With variance-free typing, I either have to specify that the function must take integers compare(a: Integer, a:Integer) or that it must take a specific super-type of integer e.g. compare(a: Object, a:Object). But what if I have a comparison defined as compare(a: Number, b: Number)? It should work fine but I can't use it in either case. So we need to be able to specify that the comparison function needs to be able to handle Integer or any superclass of Integer i.e. contra-variance.