How to determine type parameter's variance?

Question

Inspired by Real-world examples of co- and contravariance in Scala I thought a better question would be:

When designing a library, are there a specific set of questions you should ask yourself when determining whether a type parameter should be covariant or contravariant? Or should you make everything invariant and then change as needed?

Answer 1

Well, simple, does it make sense? Think of Liskov substitution.

Co-variance

If A <: B, does it make sense to pass a C[A] where a C[B] is expected? If so, make it C[+T]. The classic example is the immutable List, where a List[A] can be passed to anything expecting a List[B], assuming A is a subtype of B.

Two counter examples:

Mutable sequences are invariant, because it is possible to have type safety violations otherwise (in fact, Java's co-variant Array is vulnerable to just such things, which is why it is invariant in Scala).

Immutable Set is invariant, even though its methods are very similar to those of an immutable Seq. The difference lies with contains, which is typed on sets and untyped (ie, accept Any) on sequences. So, even though it would otherwise be possible to make it co-variant, the desire for an increased type safety on a particular method led to a choice of invariance over co-variance.

Contra-variance

If A <: B, does it make sense to pass a C[B] where a C[A] is expected? If so, make it C[-T]. The classic would-be example is Ordering. While some unrelated technical problems prevent Ordering from being contra-variant, it is intuitive that anything that can order a super-class of A can also order A. It follows that Ordering[B], which orders all elements of type B, a supertype of A, can be passed to something expecting an Ordering[A].

While Scala's Ordering is not contra-variant, Scalaz's Order is contra-variant as expected. Another example from Scalaz is its Equal trait.

Mixed Variance?

The most visible example of mixed variance in Scala is Function1 (and 2, 3, etc). It is contra-variant in the parameter it receives, and co-variant in what it returns. Note, though, that Function1 is what is used for a lot of closures, and closures are used in a lot of places, and these places are usually where Java uses (or would use) Single Abstract Method classes.

So, if you have a situation where a SAM class applies, that's likely a place for mixed contra-variance and co-variance.