Friday, April 23, 2010

Covariance and Contravariance

On occasion I've mixed these terms up. Taking X : T to mean "X has/is compatible with type T", then:

X : T is covariant if X can also take on a subtype of T;

X : T is contravariant if X can also take on a supertype of T.

Consider the expression Ys = map(F, Xs) where
Xs : list(Tx),
Ys : list(Ty), and
F : U -> V.

Clearly F must accept values of type Tx (or some supertype thereof), therefore U must be of type Tx (or some supertype thereof), hence F is contravariant in its argument.

On the other hand, F must return values of type Ty (or some subtype thereof), therefore V must be of type Ty (or some subtype thereof), hence F is covariant in its return type.

No comments: