Covariance Vs Contravariance Types


#1

Hi,

Going through Scala tutorial, I got stuck at the Variance topic.
While I was trying to improve the content, I found myself might not have been able to grasp the difference between thee two. So I was adviced by SethTisue to post my questions/understanding here before proceeding with pull request.

So here is my understanding:

As far as the Covariance & Contravariance go, I’ve always looked at them as being analogous to UpperBound & LowerBound, respectively.

So, I understand that:

  • Covariance : allows assigning an instance to a variable whose type is one of the instance’s generic type; i.e. supertype .
  • Contravariance : allows assigning an instance to a variable whose type is one of the instance’s derived type; i.e. subtype .

The same rule applies when passing to a method parameter.

For Covariance

List[+A] was used as an example. Replacing the type with a concrete example:

List[Animal] // So here A = Animal

The Covariant of A must be a subtype of A say B . A is an UpperBound.
So I understand that the following must hold true:

List[Animal] :> List[Cat] \\ where A = Animal & B = Cat

List[Animal] :> List[Dog] \\ where A = Animal & B = Dog

So, this brings me to the conclusion that A is a supertype of B , or in other words B is a subtype of A . Therefore,

val animals:List[Animal] = List[Cat]() \\ holds true!

From the tutorial, I get stuck when I read the description:

“making A covariant implies that for two types A and B where A is a subtype of B …” <=
If A is a covariance, why would it be assumed as a subtype of B ? Shouldn’t it be the way around?
And if the wording of “subtype” is more natural, Would saying B is a subtype of A make sense?

For Contravariance

I’m not sure if it’s the verbiage that’s confusing me, but looking at it for a while I see why you insisted my correction was wrong.

I wonder if having a verbiage like the following would make it less confusing:

Let’s take List[-A] as an example. Replacing the type with a concrete example:

List[Cat] // So here A = Cat

The Contravariant of A must be a supertype of A say B . A is a LowerBound.
So I understand that the following must hold true:

List[Cat] :< List[Animal] \\ where A = Cat & B = Animal

List[Dog] :< List[Animal] \\ where A = Dog & B = Animal

So, this brings me to the conclusion that A is a subtype of B , or in other words, B is a supertype of A . Therefore (via printer example),

val catPrinter: Printer[Cat] = new Printer[Animal]{...} \\ holds true!

Could anyone advice on whether I’m on the right path in understanding the differences?

Thanks
Husain


#2
  • Firstly, a much better analogy (actually a definition) is between increasing and decreasing functions (more precisely order preserving and order reversing) - think of List[A] as a function of the type A giving the type List[A], with types ordered by inclusion (as sets of objects), i.e., “being a subtype of”.
  • So as Dogs are Animals, Dog :< Animal and hence List[Dog] :< List[Animal], which makes perfect sense as a list of Dogs is a list of Animals.
  • On the other hand, Contravariance corresponds to decreasing, i.e., order reversing functions. This is natural for domains of a function Map etc., as functions restrict but do not extend
    • So given weight : Function[Animal, Double] we can obviously restrict to get weight : Function[Dog, Double] by weighing only dogs, so Function1[Animal, Double] :< Function1[Dog, Animal]
    • but there is no way to extend earsAreFloppy: Function1[Dog, Boolean] to all animals, since this is meaningless for snakes, and even if it was meaningful knowing which dogs have floppy ears says nothing about which cats have floppy ears.

regards,
Siddhartha


#4

Hi Siddhartha,
Thank you for the elaborate reply and sorry for not
coming back to you right away.

I had to spend some time trying to wrap my head around it. It appears
the source of my confusion was mixing the the inheritance within the
types; say Animal and Dog, and the variance over the inheritance; which
provides a subtyping relationship between the parameterized types; say
List[Animal] and List[Dog].

I lost you at “increasing and decreasing functions (more precisely order
preserving and order reversing)”. I understood “increasing” as from the
top down the hierarchy and “decreasing” as from the bottom up the
hierarchy of the types. Correct me if this is not what you were trying
to say.

Assuming this hierarchy:

class LivingBeing
class Animal extends LivingBeing
class Dog extends Animal

The following is what I could collect:

Variance Notation Description T = Animal

Covariance

+T

"+" is inclusive of the subtypes

List[Dog] is a subtype of List[Animal]

Contrvariance

-T

"-" is exclusive of the subtypes

List[LivingBeing] is a subtype of List[Animal]

Invariance

T

"+" is neither inclusive nor exclusive of the subtypes

List[Animal] is only and only List[Animal]


#5

(fwiw, the increasing/decreasing function thing wasn’t clear to me either, I don’t think I’ve ever heard it described that way before)


#6

Here is an expanded, and hopefully clearer version. I’ll mention the category notions in the end (they are more complicated than necessary in this case).

  1. Firstly, to clarify order-preserving and order-reversing, we can consider functions of real numbers. The function f(x) = 2 * x is order-preserving as if a < b then f(a) < f(b). On the other hand the function g(x) = -x is order-reversing as _if a < b then g(b) < g(a).
  2. These definitions make sense for any partial order.
  3. Types have a partial order by sub-typing, so for example Dog <: Animalas Dog is a sub-type of Animal. We can read this as Dog <: Animal means a Dog is an Animal.
  4. Now, we can think of parametrized types such as List[_] as functions from types to types. So List is a function that given input a type A has output a type List[A]. In this sense Map[A, B] is a function of two variables, analogous to f(x, y) = 2x + y over real numbers, for example.
  5. Covariance: A parametrized type (e.g. List[A]) is covariant just means that it is order-preserving as a function from types to types, i.e., _if A <: B then List[A] <: List[B].
  6. Collections are naturally covariant, since Dog <: Animal means a Dog is an animal, so a pack of Dogs is also a pack of animals.
  7. Contravariant: A parametrized type P[A] is contravariant if it is order reversing as function from types to types, i.e. if A <: B then P[B] <: P[A].
  8. An example is P[A] = A => Boolean This is because we can restrict functions, so a function such as isBlack: Animal => Boolean restricts to isBlack: Dog => Boolean, i.e., from Dog <: Animal we get P[Animal] <: P[Dog]. On the other hand, we have earsAreFloppy: Dog => Boolean but this does not give an object earsAreFloppy: Animal => Boolean (what about snakes?)
  9. For example, Map[A, B] is a function from two types A and B to the type Map[A, B]. It is covariant in B and contravariant in A, since if AA <: A we can consider only those keys that have type AA to get Map[AA, B] from a Map[A, B]. On thlye other hand, if B <: BB, then values of type B are automatically have type BB, so a Map[A, B] is a Map[A, BB]
  10. Finally, the relation to categories (not needed in this case). We have a category whose objects are types and morphisms are only inclusions between sub-types. From this view, covariance and contravariance are being covariant/contravariant Functors (in general any partially ordered set gives a category, and functors are order-preserving maps).

regards,
Siddhartha


#7

Should be P[B] <: P[A].


#8

Consider these classes:

class store[+A] {
  def buy(): A = ???
}

class Park[-A] {
  def play(x: A) = ()
}

All you know about a Store[A] is that it sells some A. Any Store[Dog] is a Store[Animal] because it sells animals (namely, dogs). Any code that expects a Store[Animal] value will work with a Store[Dog]. So, it makes sense for the type Store[_] to be covariant.

On the other hand, all you know about a Park[A] is that it can take an A to play. Any Park[Animal] is a Park[Dog] because it accepts dogs to play. Any code that expects a Park[Dog] value will work with a Park[Animal]. So, it makes sense for the Park[_] type to be contravariant.


#9

Thanks. Corrected.