So, by now it is pretty obvious what horrible mistake it was that arrays in Java are covariant. Maybe this design flaw is even the reason why many developers still struggle with the fact that, against common intuition,
List<Thread> is not a subtype of
A lot of this has to do with
Lists (and other collections) being mutable, so to keep the type system sane, their type parameters necessarily have to be invariant.
Now, on the other hand, if a programming language were purely functional and only supported immutable types, couldn’t one go back to a type system where type parameters were either covariant or contravariant (but never invariant)? In other words, to use Scala’s way of expressing variance, one would have
Map[-K, +V], etc.
I know that there are some older languages (e.g., GNU Sather) that seem to get away with supporting just co-/contravariant parameter types.
My general question is: in a world of completely immutable data types, is there a case where one would specifically need an invariant parameter type (as opposed to either co- or contravariant)? Are there some examples for data structures that would only be correct with an invariant type parameter?