浅谈covariance和contravariance

一些定义

考虑类型A和C，以及泛型构造器F<T>：

如果我们在一个需要A的地方，总能使用C，我们就可以说C是A的子类型（subtype）^[1]，记作C <: A。
如果F是协变的（covariant），且C <: A，则有F<C> <: F<A>。
如果F是逆变的（contravariant），且C <: A，则有F<A> <: F<C>。
如果F是不变的（invariant），无论A与C是什么关系，F<C> 与 F<A>都没有关系。

Collection视角

先举用例子来看看Collection的型变规则。

Duck是Bird的子类，Bird是Animal的子类，记作Duck <: Bird <: Animal。

TypeScript中的Array是协变的（covariant）：

interface Animal { name: String }
interface Bird extends Animal {
    // not all animals can fly
    fly: () => String 
}
interface Duck extends Bird {
    // not all birds can swim
    swim: () => String 
}
const aDog: Animal = {
    name: ""
}
const aBird: Bird = {
    name: "Owl",
    fly: () => name + " is flying!"
}
const aDuck: Duck = {
    name: "Donald", 
    fly: () => name + " is flying!",
    swim: () => name + " is swiming!"
}

// Legal; Array is covariant, expecting an Array<Animal>, given an Array<Bird> 
const animals: Array<Animal> = [aDuck, aBird]; 
// Illegal; expecting an Array<Bird>, given an Array<Animal>
const birds: Array<Bird> = [aDuck, aDog];

函数传入参数同样遵循这个规则：

function birdsFly(birds: Array<Bird>) {
    birds.forEach(b => b.fly())
}
birdsFly(animals) // Illegal
birdsFly(birds) // Legal, type matches
birdsFly(ducks) // Legal, Array<Duck> <: Array<Bird>

默认情况下，Java的List是不变的（invariant）：

List<Bird> birds = new ArrayList<Duck>(); // Illegal
List<Bird> birds = new ArrayList<Bird>(); // Legal

void birdsFly(List<Bird> birds) {...}

birdsFly(animals); // Illegal
birdsFly(birds); // Legal
birdsFly(ducks); // Illegal

当然，我们可以用bounded wildcards在使用时去除不变性：

1 2	List<? extends Bird> coList = new ArrayList<Duck>(); // Legal; covariant List<? super Bird> contraList = new ArrayList<Animal>(); // Legal; contravariant

Effective Java中提到的PECS（producer extends，consumer super），就是说，如果你接收一个Collection：

只读其中的元素（Collection是producer），那么你最好接受一个协变的Collection；
反之，如果你只写入List（Collection是consumer），那么你最好接受一个逆变的Collection。

void namesOfBirds(List<? extends Bird> birds) {
  birds.forEach(bird -> System.out.println(bird.getName()));
}
namesOfBird(ducks); // Legal; covariant

void addAOwl(List<? super Bird> birds) {
  Bird aOwl = new Bird("owl");
  birds.add(aOwl);
}
// It is natural to add a owl into a List<Animal>
addAOwl(animals) // Legal; contravariant

Function Type

容器类型的型变其实是比较符合直觉的，函数类型就很反直觉了。

1	trait Function1[-T1, +R]

这是Scala标准库定义的单参函数的trait（可以理解为interface），类型为T1 -> R，其中T1是逆变的，R是协变的^[2]。

But why？？？

回想一下，型变规则决定了我们能使用什么样的子类型，子类型决定了我们能在一个期望X的地方，安全地使用另一个类型Y（X的子类型）。

So，既然函数类型也是一种类型，我们当然也要知道函数类型的子类型咯，对吧？

那么对于函数类型Bird -> Bird，根据trait定义，Animal -> Duck就是它的子类型。

Weird, right?

假设我们有高阶函数f: (Bird -> Bird) -> String（返回什么我们并不关心）。

将传入的函数记作g，尝试在g的参数上用子（超）类型进行替代:

1. 如果g: Duck -> Bird，f(g)会怎样？

f已知g接受Bird，于是f调用g的时候，传给g一个Bird。

然而，g只能处理Bird的一个子类型Duck，如果接收到一个Swan，g会崩溃。

所以参数类型不可以用子类型替代。

2. 如果g: Bird -> Animal，f(g)会怎样？

f已知g返回Bird，于是f会将g的返回值当作Bird来使用。

但是现在g会返回一个不是Bird的Animal，比如Dog，那么f会崩溃。

所以返回类型不可以用超类型替代。

3. 如果g: Animal -> Duck，f(g)又如何呢？

f已知g接收Bird，所以传给g一个Bird，g可以正常处理Bird并返回Duck，没有问题。

f已知g返回Bird，所以将g返回的Duck当作Bird来用，所有Duck都是Bird，也没问题。

所以，在一个期望(Bird -> Bird)的地方，我们总是可以使用(Animal -> Duck)。

即(Animal -> Duck)是(Bird -> Bird)的子类型。

也就是说，参数类型可以用超类型替代，返回类型可以用子类型替代。

形式化一点，就是对于函数类型构造器->，接收参数逆变且返回参数协变时，仍然可以保证类型安全。

或者说：对于函数p和q，当p的参数更general，返回值更specific时，p可以安全地替代q。

其实，Java8的Function接口的型变规则也是这样的，compose和andThen都是接收了一个Function<? super V, ? extends T>，恰恰正是参数逆变，返回值协变。

// see http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/function/Function.java
@FunctionalInterface
public interface Function<T, R> {
    default <V> Function<V, R> compose(Function<? super V, ? extends T> before) {
        Objects.requireNonNull(before);
        return (V v) -> apply(before.apply(v));
    }
    default <V> Function<T, V> andThen(Function<? super R, ? extends V> after) {
        Objects.requireNonNull(after);
        return (T t) -> after.apply(apply(t));
    }
}

References

需要注意的是，子类（subclass）和子类型（subtype）不是一回事。 ↩
Scala中，F[+A]代表协变，F[-A]代表逆变，F[A]代表不变。 ↩