Covariance, Contravariance, Invariance

Defining covariance, contravariance and invariance, declaration site variance vs. use site variance (type projections) and the in and out keywords

— — — — — — — — — — — — — — —

THE CURRENT VERSION OF THIS ARTICLE IS PUBLISHED HERE.

— — — — — — — — — — — — — — —

Tags: #FYI #KOTLIN FEATURE

This article is part of the Kotlin Primer, an opinionated guide to the Kotlin language, which is indented to help facilitate Kotlin adoption inside Java-centric organizations. It was originally written as an organizational learning resource for Etnetera a.s. and I would like to express my sincere gratitude for their support.

It is recommended to read the Introduction before moving on. Check out the Table of Contents for all articles.

Let’s recap what we found out in the previous chapters:

• Variance deals with the ability to transfer sub-/super-type relationships between types to sub-/super-type relationships between generic constructs involving those types. In practice, this means asking questions like “If Int is a subclass of Number, can I, for instance, use SomeConstruct<Number> when a SomeConstruct<Int> is expected?” and we demonstrated a simple business problem where this is useful. In other words, variance describes when and how subtyping of generic constructs works.
• Studying variance, i.e. when these substitutions are possible, is equivalent to studying the same question with functions — if Int is a subclass of Number, can we, for instance, use (Int) -> String instead of a (Number) -> String? Keep in mind, this is the same as asking if (Int) -> String is a subtype of (Number) -> String!
• There are only two situations when this is possible — when the argument is more general, or when the return value is more specific. (Any) -> Boolean can be used in place of (is a subtype of) (Double) -> Boolean, and (String) -> Int can be used in place of (is a subtype of) (String) -> Number, and that’s all. In other words, we can vary the types of the argument and return value in opposite directions — types that go in can be any super-type, while types that come out can be any subtype.

This means that, in order to find out if, and how, subtyping works with a generic construct SomeConstruct<T>, it is necessary to look at the positions T appears in. There are really only three things that can happen:

• T appears only in in positions, i.e. only as method arguments
• T appears only in out positions, i.e. only in return values
• T appears in both

Each of these situations has their own name.

Contravariance

If a type T occurs in a generic construct (function, class = group of functions, ...) only in in positions (function arguments), that construct is called contravariant in T.

• Using a different construct is permissible if all other types are compatible, and T is replaced by any super-type of T. This why it is contra-variant — transforming T to a super-type causes the construct to become a subtype. Subtyping works in the opposite direction.
• That is the same as saying a construct can be replaced by a different one if it computes the same amount of information from a less or equal amount of information

For example, Comparable<T> is contravariant in T, because T appears only in method arguments (specifically, in arguments to the compareTo method). Whenever we need a Comparable<Int>, we can use Comparable<Number> — if we have an algorithm that compares instances of Number, we can be sure it can compare instances of Int as well.

Covariance

If a type T occurs in a generic construct (function, class = group of functions, ...) only in out positions (function return types) that construct is called covariant in T.

• Using a different construct is permissible if all other types are compatible, and T is replaced by any subtype of T. This why it is co-variant — transforming T to a subtype causes the construct to become a subtype. Subtyping works in the same direction.
• That is the same as saying a construct can be replaced by a different one if it computes the same or more information from the same amount of information

For example, List<T> is covariant in T, because T only appears in return values — don’t forget, this is an immutable list, so elements can’t be added! Whenever we need a List<Number>, we can use List<Int>. Any computation that’s valid for a List<Number> also works for a List<Int> (and List<Double>, List<Long> etc.) same as any computation that’s valid for a Number is also valid for an Int (and Double, Long etc.).

Invariance

If a type T occurs in a generic construct (function, class = group of functions, ...) in both in and out positions, that construct is called invariant in T.

• A different construct can be used only if it uses the exact same types. No other replacements are permissible.

For example, MutableList<T> is invariant in T, because it both returns T’s (via various getters) and accepts them (via various setters).

The above is actually only partially true. Since you explicitly have to tell the compiler to make a construct variant (see bellow), it is possible to write a data structure that could be variant, but isn’t marked as such. Such a construct is also called invariant — it doesn’t vary with super-/sub-typing, even though it could.

Declaration site variance

Tags: #KOTLIN FEATURE

Declaration site variance is something Java does not have — it refers to the ability of specifying co-/contra-variance in a class/function declaration. Java, naturally, allows defining generic constructs, but you cannot declare the generic variables as co-/contra-variant generally, and can only declare them as such at the use-site (see the following section).

Type variables in class/function definitions are invariant by default — even if they only appear in strictly co-/contra-variant positions, they must be explicitly marked by in (contravariance) or out (covariance):

In practice, the compiler will always let you know if you mark a generic variable as in/out, but it appears in a position that violates that contract. In the above, try changing the definition of contents in CovariantBlackbox to var instead of val. That adds a setter, which takes T as an input - a contravariant position. The compiler will let you know that's a problem.

You might be wondering if the Function interface is defined with variance modifiers, given all that we have said, and indeed that is the case, exactly as you would expect.

Note that none of the above is possible in Java, as Java does not have the concept of declaration-site variance, but only use-site variance, which we will discuss bellow. In other words, to make the above work in Java, the variant lines would have to be declared with a wildcard, e.g.

CovariantBlackbox<? extends Number> numberCovariantBlackBox = 
  intCovariantBlackbox

// ...

ContravariantComparator<? super Int> intContravariantComparator = 
  numberContravariantComparator

This approach is still possible in Kotlin, as we will see bellow.

Use-site variance

Tags: #FYI

To mark a generic construct as being variant in a type parameter T, we must guarantee that that type is only used in certain positions (in or out). Declaration-site variance requires this guarantee by design - the class or function in question must be designed so that T only appears in in or out positions.

However, we may also guarantee this by the way we use the construct. If a type variable appears in both in and out positions, but we only ever call the code where it appears in an in position, we should be able to (in this context) treat it as being contravariant.

This is the basic idea behind use-site variance, also called type projections.

The example above won’t compile, because MutableBlackbox is invariant in T. However, we can clearly see that putPieInBox(numberMB) should be typesafe, because there is no harm in putting a Double wherever a Number is expected. Even though the class is invariant in general, this specific usage is contravariant. Again, we must explicitly mark the type as such.

This is exactly the equivalent of ? super Double in Java. The covariant counterpart, box: MutableBlackbox<out Double>, is equivalent to ? extends Double.

Go back to Generic Variance — Fundamental Principles, jump to the Table of Contents, or continue to Star Projections.