Co-variance & Contra-variance

I have been working on Scala recently and it has been a pure pleasure. I am in love with the language. And Yes! it indeed is a beast.

Generics/Parametrization is something that has always kept me on the hook even after good amount of experience in it. Thanks to Scala and lectures by Martin Odersky, I am much better now. There have been some realizations on the go, but to explain that I will first have to explain some basics. Though theoretical and boring at many places, I promise this will improve your architect skills if understood well :)

I have planned the post in 4 parts:

  1. Brief overview of Co-variance & Contra-variance
  2. Above paradigm behavior in Java, Python, C#
  3. Overview and short-comings of Generics in Java. Design flaw with Arrays
  4. A detailed theoretical explanation with help of Scala

Before starting, there is one very important theorem called Liskov Substitution principle in object oriented world. This should always be behind your mind while designing API’s. It states-

Let q(x) be a property provable about objects x of type T. Then q(y) should be provable for objects y of type S where S is a subtype of T.

The above means- If “A” extends “B” (A <: B), then all the things that one can do with “B” should also be legal with “A”.

Co-variance & Contra-variance

 Wiki will give you a formal definition. Crudely:

  • Co-variance ( <: ) is converting type from wider type to narrow. In Java terms- ? extends E*
  • Contra-variance (>: )is converting type from narrow to wider. In Java terms- ? super E*
  • In-variant cannot be converted
* Where E is generic type declared and “?” is a wild card which crudely means “Anytype”
So for example:
class Animal { }

class Dog extends Animal{ }

class Example{

void run(){
 Dog dog = new Dog();
 getAnimal(dog);
 }

void getAnimal(Animal animal){
 .....
 }

}

In the above example, one is ultimately doing

Animal animal = dog

So you are converting a dog type (narrow) to Animal type (wider). This is contra-variance. The reverse of it is Co-variance. The above paradigm is also followed in C# and python.

For co-variance:

class A{
   Animal getCreature(){
    return new Dog();
   }
}
class B extends A{
   Dog getCreature(){
     return new Dog();
   }
 }

Check the return type of the getCreature function. getCreature() ultimately returns an Animal. But it returns type of Dog in class B. This is co-variance. The above is perfectly legal, because the code that invokes getCreature() of class A expects an Animal in return; which class B provides a Dog (ultimately dog is an animal. Vice-versa wont work, think!)

Invariance is when the type cannot be converted.

By default return types of functions in Java, C# and python are co-variant and argument types are invariant.

Points to Remember:

I will raise some points now and the explanation will be given by the end. The whole point of the post are the below points.

  1. Contravariant types can only appear in places, where you write something (i.e. parameter types) and covariant types can only appear in places, where you read something. [P1]
  2. Co-variance is only suitable when the data is immutable. More on it below. [P2]

I will first raise the issues caused in Java by not following [P1] i.e Arrays disaster for which Generics (type erasure) will be discussed. And then issues with [P2]. Finally improvements and how the issue was dealt successfully in Scala in the next post :)

Edit: Well some more examples to understand better:

</pre>
scala> class A[T](n:T)
 defined class A

scala> class B[+T1,-T2](n:T1, m:T2) //co-variant T1 and contra-variant T2
 defined class B

scala> class C[-T1, +T2](n:T1, m:T2) // contra-variant T1 and co-variant T2
 defined class C

scala>List(new B(1d,1), new B(2,"2"),new B("3",3d))
 res0: List[B[Any,Double with String with Int]] = List(B@67ef6bbf, B@178afde8, B@2623966b)

scala> List(new C(1d,1), new C(2,"2"),new C("3",3d))
 res1: List[C[String with Int with Double,Any]] = List(C@13f23e56, C@4da8a55, C@27afd4f0)

scala> List(new A(1d), new A(2),new A("3"))
 res2: List[A[_ >: String with Int with Double]] = List(A@6800bea8, A@8e53cf0, A@203b520)

For evaluating `res0`, compiler looks for a common super-type of all arguments.

  1. All arguments are of type B[something]. So type something has to be evaluated. type something has to satisfy variance bounds of B
  2. Since type T1 is co-variant, compiler needs to find a type such that “Int <: something & Double <: something & String <: something” and that can only be: Any
  3. Since type T2 is contra-variant, compiler needs to find a type such that “Int >: something & Double >: something & String >: something” and that can be: Int with Double with String

To confirm point-3, try doing below:

type Custom = String with Int with Double
def f[T](implicit ev: Custom <:< T){}

f[Int]
f[String]
f[Double] // all compile fine

Hence res0 is evaluated as type List[B[Any,Double with String with Int]]. res1 is evaluated in a similar procedure. Evaluating res2 is again interesting:

  1. All arguments are of type A[something].
  2. Since type T is in-variant, compiler needs to find a type such that it is the minimum-most possible in the hierarchy and satisfies “Int =:= something & Double =:= something & String =:= something“. This satisfies perfectly _ >: String with Int with Double Though such a list will be useless as you cannot do much with it. It is no better than Any