covariance and variance flip in scala

Question

In Scala for the Impatient It is said that

functions are contra-variant in their arguments and covariant in their result type

This is straightforward and easy to understand ,however in the same topic it says

However inside a function parameter ,the variance flips- its parameters are covariant

and it takes the example of foldLeft method of Iterator as :

 def foldLeft[B](z : B)(op : (B, A) => B) : B 

I am not getting it clearly what it says.

I tried some of blogs as

1. http://www.artima.com/pins1ed/type-parameterization.html

2. http://blog.kamkor.me/Covariance-And-Contravariance-In-Scala/

3. http://blogs.atlassian.com/2013/01/covariance-and-contravariance-in-scala/

But didn't get clear understanding.

Answer 1

It comes down to what it means for one function to be a subtype of another. It sounds like you are comfortable with A->B is a subtype of C->D if C is subtype of A (contravariant in the input type) and B is a subtype of D (covariant in the return type).

Now consider functions that take other functions as arguments. For example, consider (A->B)->B. We just apply the same reasoning twice. The argument is a function of type A->B and the return type is B. What needs to be true to supply a function of type C->B as the input type? Since functions are contravariant in the input type C->B must be a subtype of A->B. But as we discussed in the first paragraph, that means that A must be a subtype of C. So after two applications of the reasoning in the first paragraph we find that (A->B)->B is covariant in the A position.

You can reason similarly with more complicated functions. In fact, you should convince yourself that a position is covariant if it is to the left of an even number of arrows applying to it.

Answer 2

A function is always contravariant in its argument type and covariant in its return type e.g.

trait Function1[-T1, +R] extends AnyRef 

trait Function2[-T1, -T2, +R] extends AnyRef 

Here, T1,T2, ..., Tn (where n <= 22) are arguments and R is the return type.

In higher order functions (functions that take function as argument), an argument can have the type parameter that is passed into the function e.g. foldLeft in trait Iterable

Iterable is declared as

trait Iterable[+A] extends AnyRef

and foldLeft is decalred as

def foldLeft[B](z : B)(op : (B, A) => B) : B 

Since A is declared covariant, it can be used as the return type. But here it is instead an argument type due to

trait Function2[-T1, -T2, +R] extends AnyRef 

because op : (B, A) => B is the literal type of Function2.

The key to this is trait Function2 is contravariant in its argument type.

Hence covariance type is appearing in method argument due to

trait Function2 is contravariant in its argument type

This is called variance flip:

1. Flip of covariance is contravariance.
2. Flip of contravariance is covariance.
3. Flip is invariant is invariant.

That's why invariant may appear at any position (covariance/contravariance)