Never have I had a clearer take on the concept of variance until this presentation: Typing the Untyped: Soundness in Gradual Type Systems This post tries to condense that into a 1-min reading.

In the context of subtyping, variance refers to how subtyping between more complex types relates to subtyping between their components. For example, the relation between using FA = IA -> OA and using Fa = Ia -> Oa vs the relation between IA vs Ia and OA vs Oa.

Assuming FA > Fa, Fa is a subtype of FA, then we should have IA < Ia and OA > Oa. The key idea is to view types from a producer-consumer perspective: as the child type, it needs to be able to consume more types and produce fewer types. Think of this as a pipe; as the next generation (child type), it needs to handle more complex scenarios (more types) without introducing any extra dependency for the next stage. Therefore, functions are contra-variant in the input type and co-variant in the output type.

1
2
3
4
5
6
7
8
using FA = IA -> OA
using Fa = Ia -> Oa

FA > Fa

IA < Ia # order flipped; contra-variance

OA > Oa # order preserved; co-variance

For container-like types, the only sensible way is to make them invariant, since we can add to (new values are consumed by the container) and read from (new values are produced by the container) containers. However, due to other factors, array is co-variant in Java, while other collection types (with generics) are invariant. Note that different languages make different choices here.