Covariance, contravariance, and subtyping in functional programming

A tutorial about covariance, contravariance, and subtyping as used in functional programming (FP).

- Subtyping in FP can be defined via conversion functions. P is a subtype of Q if there is a conversion function of type P → Q.
- In FP there are 3 constructions of subtyping: co-product subtyping, product subtyping, and function subtyping. OOP uses only the "product subtyping".
- Covariance and contravariance are properties of type constructors. Those properties are not defined via subtyping. (And subtyping is not defined via covariance or contravariance.)
- Covariant and contravariant type constructors naturally support specific subtyping features via their fmap and cmap functions. The type annotations in Scala, such as F[+A] or G[-A], will activate the compiler's support for those features (making F[A] a subtype of F[B] whenever A is a subtype of B).
- The type annotations F[+A] or G[-A] do not *define* covariance or contravariance, beacuse the type constructors F and G must be already covariant / contravariant in order for the type annotations to be valid.
- Covariance and contravariance can be detected via positive and negative positions of type parameters.
- A presence of a `var` in a type definition will prevent subtyping because `var` is translated into a getter and a setter, which puts the type parameter both into negative and into positive positions.
- Type constructors that are neither covariant nor contravariant can still have an xmap function that transforms F[A] → F[B].
- The correct code of fmap, cmap, and xmap can be generated mechanically.

[pmcgee]

I don't know if it gets a mention, but I was kind of intrigued to realise that in Rust, lifetimes have a subtyping relationship.