How do covariant parameterized types nested inside invariant parameterized types act?

Question

Here is a concrete example of what I'm asking about:

MutableList[ImmutableList[Object]]

Where ImmutableList is covariant wrt its first parameter, but MutableList is invariant wrt its first parameter. Object is our "root type" that all types are a subtype of.

Is the type MutableList[ImmutableList[String]] a subtype of MutableList[ImmutableList[Object]] (assuming String is a subtype of Object) or is the only subtype of MutableList[ImmutableList[Object]] another MutableList[ImmutableList[Object]]? Is this language specific?

Any insights or articles are very much appreciated.

Answer 1

TL;DR No, MutableList[ImmutableList[String]] is not a subtype of MutableList[ImmutableList[Object]].

You can approach the problem intuitively by thinking about what's possible to do with the type. If MutableList has a "push" operation, for instance:

1. You can push an ImmutableList[Object] into a MutableList[ImmutableList[Object]].
2. ImmutableList[Integer] is a subtype of ImmutableList[Object].
3. Therefore, you can push an ImmutableList[Integer] into a MutableList[ImmutableList[Object]].
4. However, you cannot push an ImmutableList[Integer] into a MutableList[ImmutableList[String]];
5. therefore, MutableList[ImmutableList[String]] is not a subtype of MutableList[ImmutableList[Object]].

This really is an explanation of why MutableList[T] is invariant in T: because it supports push.

It's also possible to work out the answer using the definitions of covariance and invariance.

ImmutableList[T] is covariant in T. This means that if A <: B, then ImmutableList[A] <: ImmutableList[B]. (I'm using the symbol <: for "is a subtype of")

• Take A = String and B = Object. String <: Object, so ImmutableList[String] <: ImmutableList[Object].

MutableList[T] is invariant in T. This means that even if A <: B, MutableList[A] and MutableList[B] do not participate in a subtype relationship; they are incompatible types.

• Take A = ImmutableList[String] and B = ImmutableList[Object]. Even though ImmutableList[String] <: ImmutableList[Object] (as we showed above), MutableList[ImmutableList[String]] and MutableList[ImmutableList[Object]] still do not participate in a subtype relationship.

Covariance and contravariance are two ways the subtype relationship can "leak out" of a type constructor. Invariance is what happens when the subtype relationship doesn't leak at all, so you can't cascade invariance with anything else and get anything other than invariance.

The meaning of different kinds of variance is not language specific, but there are some languages with mutable containers that are not considered invariant. Java is one example, and you can abuse this loophole in the type system to make programs that fail with runtime type errors despite compiling fine.

• Florian F: The point is that you can add an ImmutableList[Object] to a MutableList[ImmutableList[Object]] but not to a MutableList[ImmutableList[String]]. So the later doesn't comply with the contract of the former.
• trent: @FlorianF Thanks, I like your more intuitive explanation, so I overcomplicated it and added it to the answer :-)