Search code examples
scalacollectionscovariancecontravariance

Scala collections: Why is Elem contravariant in Builder but covariant in TraversableLike?

Covariance is very intuitive to me, but my understanding of contra-variance is a little shaky. I understand the contra-variance in Function[-A, +B] because an Animal => Int function can be used wherever a Rabbit => Int function is used. I don't really understand how this same sort of contra-variant relationship applies to Builder's Elem term, and in particular, why Builder's Elem is contra-variant but TraversableLike's Elem is covariant.

Solution

  • There is a rule of thumb:

    contra-variance is for function parameters and variance is for function return type

    I am going to elaborate this. Generally if you have a function like:

    def f(a: A): B

    you can pass any instances of all sub-type of A to this function and assign the result to a value which is type of any super-type of B

    So imagine you have the following generic type:

    trait Builder[Elem, To]

    This means that you can add elements which are type of Elem to form an instance of type To. For example having the following types:

    class Animal
class Cat extends Animal
class Dog extends Animal
class Tiger extends Cat

val a: Builder[Cat, ArrayBuffer[Cat]]

    gives you a builder to build ArrayBuffer containing elements of type Cat. What we want is a more general constructs. Let's take a look at the following example:

    implicit val builder: Builder[Cat, ArrayBuffer[Cat]] = ...
def build(elements: Tiger*)(implicit b: Builder[Tiger, ArrayBuffer[Animal]]): ArrayBuffer[Animal] = { ... }

    We have a build function which needs an implicit in the scope with which it could make an ArrayBuffer[Animal] out of array of Tigerinstances. Let's back to some logic.

    • It is logical to assign ArrayBuffer[Cat] to a value with type ArrayBuffer[Animal].
    • It is logical to add a Tiger to a ArrayBuffer[Cat] because Tiger is kind of cat.

    So our build function logically should be able to use builder implicit val to form ArrayBuffer[Cat] or more generally to form ArrayBufer[Animal] out of given collection of Tiger instances. This only possible if the following relation is held:

    Builder[Cat, ArrayBuffer[Cat]] <: Builder[Tiger, ArrayBuffer[Animal]]

    In this case builder can be picked as b parameter upon invocation of build function.

    The only way to make this relation happen is to change Builder trait to following:

    trait Builder[-Elem, +To]

    So since Tiger <: Cat and Cat <: Animal, according to contra-variance on Elem and variance on To, Builder[Cat, ArrayBuffer[Cat]] <: Builder[Tiger, ArrayBuffer[Animal]].

    Back to the introductory rule of thumb: you want to use elements of type Elem to form a collection of type To. imagine it as a function where Elem is the parameter type and To is the return type. So contra-variance on the parameter type and variance on return type, make it a logically correct generic function.