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

``````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.

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.

• 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. – Florian F Aug 28 '20 at 9:03
• @FlorianF Thanks, I like your more intuitive explanation, so I overcomplicated it and added it to the answer :-) – trentcl Aug 28 '20 at 14:19