Variance

Variance #

Subtype #

Notation. If $A$ and $B$ are types, we will use $A \sqsubseteq B$ to denote the fact that $A$ is a subtype of $B$.

Subtype and substitution #

The Liskov substitution principle intuitively states that If $A \sqsubseteq B$, then it should be possible to replace $B$ by $A$ in a program, without affecting the correctness of type checks.

Examples.

  • If Integer $\sqsubseteq$ Number, then a method that takes a Number as input should also accept an Integer.
  • If Butterfly $\sqsubseteq$ Unit, then a method that returns a Unit can also return a Butterfly.

Type parameters and subtyping #

A natural question is whether subtyping between parameterized types should be determined by subtyping between their parameters.

Covariance #

Example. Consider the generic type Set<T> (where T is a type variable).

  • Should Set<Integer> be treated as a subtype of Set<Number>?
  • Should Set<Butterfly> be treated as a subtype of Set<Unit>?

More generally, if A $\sqsubseteq$ B, then should Set<A> be considered a subtype of Set<B>?

In this example, the intuitively answer to this question seems to be positive.

When this holds, the generic type (i.e. Set<T> in this example) is said to be covariant.

Definition. Let Gen<T> be a generic type (where T is a type variable).

Gen<T> is covariant if for any types A and B,

$\qquad$ A $\sqsubseteq$ B implies Gen<A> $\sqsubseteq$ Gen<B>

Contravariance #

What intuitively holds above for sets does not seem to hold for all generic types.

Example. Consider the Java functional interface Predicate<T> (where T is a type variable), which stands for all functions that return a Boolean value, i.e. all functions with type

$\qquad$ T $\to$ Boolean

As we saw in the dedicated section, if A $\sqsubseteq$ B, then

$\qquad$ B $\to$ Boolean

should intuitively be considered a subtype of

$\qquad$ A $\to$ Boolean

Therefore in this case, we would like to treat Predicate<B> as a subtype of Predicate<A>.

Definition. Let Gen<T> be a generic type, where T is a type variable.

Gen<T> is contravariant if for any types A and B,

$\qquad$ A $\sqsubseteq$ B implies Gen<B> $\sqsubseteq$ Gen<A>

Invariance #

Definition. A generic type is invariant if it is neither covariant nor contravariant.

Variance in several type variables #

If a generic type has several type variables, then it can be independently covariant, contravariant or invariant in each of them.

Example. Consider the Java functional interface Function<T,R> (where T and R are type variables), which stands for all functions with type

$\qquad$ T $\to$ R

As we saw in the dedicated section, if X1 $\sqsubseteq$ X2 and Y1 $\sqsubseteq$ Y2, then

$\qquad$ X2 $\to$ Y1

should intuitively be considered a subtype of

$\qquad$ X1 $\to$ Y2

Therefore in this case, we would like to treat Function<T,R> as:

  • contravariant in T, and
  • covariant in R.

Implementation #

As we just saw with the previous examples, some generic types are naturally covariant and/or contravariant in (some of) their type variables.

Some languages (like C#) provide a syntax to declare that a generic type should always be treated by the compiler as covariant, contravariant, invariant or a combination of them. However, Java does not offer this possibility.

in Java #

Arrays #

Java arrays predate (by almost 10 years) the introduction of generics. Technically, in Java, “array” is not a generic type. But conceptually, it can be thought of as a “generic-like” type.

Warning. Java arrays are covariant.

Example. The following Java program compiles:

Number[] anArray;
Integer[] anotherArray = new Integer[]{};
anArray = anotherArray;

Generic types #

Warning. Java generic types are invariant.

Example. The following Java program does not compile, because the generic type List<E> is invariant:

List<Number> aList;
List<Integer> anotherList = new ArrayList<>();
aList = anotherList;

So (unfortunately?) a Java generic type cannot be declared as covariant or contravariant. However, each time we use a generic type, we can specify that it should be interpreted by the compiler as covariant or contravariant.

Covariance #

We saw earlier that the keyword extends specifies an upper bound on the value of a type variable. We can also use it with a ? to allow covariance.

Example. The following Java program does compiles:

List<? extends Number> aList;
List<Integer> anotherList = new ArrayList<>();
aList = anotherList;
Contravariance #

The keyword super is symmetric to the keyword extends. It can be used to specify a lower bound on the value of a type variable, or to allow contravariance (in combination with ?).

Example. The Java interface Stream<T> is a generic type, where T is the type of the elements of the stream.

This interface has an instance method Stream.filter that takes as argument a callback function with type Predicate<T>.

As we saw above, Predicate<T> should intuitively be interpreted as contravariant. Accordingly, the signature of the method filter is

Stream<T> filter(Predicate<? super T> predicate)

It accepts as argument any method with type Predicate<V> such that T $\sqsubseteq$ V. So the following program compiles:

List<Integer> integers = getIntegers();
integers.stream()
          .filter(MyClass::myPredicate);

public class MyClass {

    static boolean myPredicate(Number number) {
        ...
    }
}
Combinations #

Example. The instance method Stream.map takes as argument a callback function with type Function<T,R>, where T is the type of the elements of the stream.

As we saw above, the generic type Function<T,R> should intuitively be interpreted as contravariant in T and covariant in R. Accordingly, the signature of the method map is:

<R> Stream<R> map(Function<? super T,? extends R> mapper)
When to use covariance or contravariance in Java? #

Let us assume a generic type Gen with a type variable T . As a rule of thumb:

  • if we use an instance method of Gen that does not take a T as argument, then we may allow Gen to be covariant in T,
  • if we use a method of Gen that does not return a T, then we may allow Gen to be contravariant in T.

Example.

public class Box<T> {

    T boxedValue;

    public Box(T boxedValue){
        this.boxedValue = boxedValue;
    }

    T getValue(){
          return boxedValue;
    }

    void setValue(T newValue){
          boxedValue = value;
    }
}

$\qquad$

// Covariance can be used, because the method Box.getValue() does not take a T as argument.
Number unbox(Box<? extends Number> box){
    return box.getValue();
}

// Contravariance can be used, because the method Box.setValue() does not return a T.
void replaceValue(Box<? super Integer> box, int integer){
    box.setValue(integer);
}