浅谈covariance和contravariance

一些定义

考虑类型AC,以及泛型构造器F<T>

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

Collection视角

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

DuckBird的子类,BirdAnimal的子类,记作Duck <: Bird <: Animal

TypeScript中的Array是协变的(covariant):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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];

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

1
2
3
4
5
6
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):

1
2
3
4
5
6
7
8
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。
1
2
3
4
5
6
7
8
9
10
11
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 -> Birdf(g)会怎样?

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

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

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

2. 如果g: Bird -> Animalf(g)会怎样?

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

但是现在g会返回一个不是BirdAnimal,比如Dog,那么f会崩溃。

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

3. 如果g: Animal -> Duckf(g)又如何呢?

f已知g接收Bird,所以传给g一个Birdg可以正常处理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接口的型变规则也是这样的,composeandThen都是接收了一个Function<? super V, ? extends T>,恰恰正是参数逆变,返回值协变

1
2
3
4
5
6
7
8
9
10
11
12
// 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

  1. What are covariance and contravariance?
  2. Covariance and contravariance (computer science)
  3. Covariance, contravariance and a little bit of TypeScript
  4. Covariance and contravariance rules in Java
  5. Variances - Tour of Scala
  6. Functoriality - Categories for Programmers

  1. 需要注意的是,子类(subclass)和子类型(subtype)不是一回事。

  2. Scala中,F[+A]代表协变,F[-A]代表逆变,F[A]代表不变。