Understanding List[+A] for Covariance

Question

Looking at the source for List.scala:

sealed abstract class List[+A] extends ... 

  ...

  def isEmpty: Boolean
  def head: A
  def tail: List[A]

List[+A] is covariant based on the +A. Does this mean that, it's possible to create a List[T] where T can be the type itself, or any of its sub-classes?

example:

scala> trait Kid
defined trait Kid

scala> case class Boy(name: String) extends Kid
defined class Boy

scala> case class Girl(name: String) extends Kid
defined class Girl

scala> val list: List[Kid] = List(Boy("kevin"), Girl("sally"))
list: List[Kid] = List(Boy(kevin), Girl(sally))

Observe that head and tail's types are A and List[A], respectively. Once we've defined List[+A], then head and tail's A is also covariant?

I've read this StackOverflow answer 3 or 4 times, but I don't understand yet.

Answer 1

Your example does not relate to variance. Moreover, head and tail have nothing to do with variance too.

scala> val list: List[Kid] = List(Boy("kevin"), Girl("sally"))
list: List[Kid] = List(Boy(kevin), Girl(sally))

This would work even if List weren't covariant, because Scala will automatically deduce common supertype of Boy and Girl, that is, Kid, and type of the expression on the right side will be List[Kid], exactly what you require on the left side.

The following, however, doesn't work because java.util.List is not covariant (it is invariant since it is Java type):

scala> import java.util.{List => JList, Arrays}
import java.util.{List=>JList, Arrays}

scala> trait Kid
defined trait Kid

scala> case class Boy(name: String) extends Kid
defined class Boy

scala> val list1 = Arrays.asList(Boy("kevin"), Boy("bob"))
list1: java.util.List[Boy] = [Boy(kevin), Boy(bob)]

scala> val list2: JList[Kid] = list1
<console>:12: error: type mismatch;
 found   : java.util.List[Boy]
 required: java.util.List[Kid]
Note: Boy <: Kid, but Java-defined trait List is invariant in type E.
You may wish to investigate a wildcard type such as `_ <: Kid`. (SLS 3.2.10)
       val list2: JList[Kid] = list1
                               ^

Arrays.asList method has signature like this:

def asList[T](args: T*): java.util.List[T]

As java.util.List[T] is invariant, it is impossible to assign JList[Boy] (list1) to JList[Kid] (list2). And there is a reason: if you could, then because JList is mutable, you could also add anything extending Kid (not only Boy) into the same list, breaking type safety.

On the other hand, scala.List will work in exactly the same situation:

scala> val list1 = List(Boy("kevin"), Boy("bob"))
list1: List[Boy] = List(Boy(kevin), Boy(bob))

scala> val list2: List[Kid] = list1
list2: List[Kid] = List(Boy(kevin), Boy(bob))

That is because scala.List is covariant in its type parameter. Note that covariant List type works as if List[Boy] were subtype of List[Kid], very similar to the case when you can assign everything to a variable of type Any because every other type is a subtype of Any. This is very helpful analogy.

Contravariance works in a very similar way, but in other direction. Consider this trait:

trait Predicate[-T] {
  def apply(obj: T): Boolean
}

object Predicate {
  // convenience method to convert functions to predicates
  def apply[T](f: (T) => Boolean) = new Predicate[T] {
    def apply(obj: T) = f(obj)
  }
}

Note the - before T parameter: it is a contravariance annotation, that is, Predicate[T] is defined to be contravariant in its only type parameter.

Recall that for covariant list List[Boy] was a subtype of List[Kid]. Well, for contravariant predicate it works in the opposite way: Predicate[Kid] is a subtype of Predicate[Boy], so you can assign a value of type Predicate[Kid] to a variable of type Predicate[Boy]:

scala> val pred1: Predicate[Kid] = Predicate { kid => kid.hashCode % 2 == 0 }
pred1: Predicate[Kid] = Predicate$$anon$1@3bccdcdd

scala> val pred2: Predicate[Boy] = pred1
pred2: Predicate[Boy] = Predicate$$anon$1@3bccdcdd

If Predicate[T] weren't contravariant, we wouldn't be able to assign pred1 to pred2, though it is completely legitimate and safe: obviously, predicates defined on supertypes can easily work on subtypes.

---

In short, variance affects type compatibility between parameterized types. List is covariant, so you can assign a value of type List[Boy] to a variable of type List[Kid] (in fact, for any T extending S, you can assign a value of type List[T] to a variable of type List[S]).

On the other hand, because, Predicate is contravariant, you can assign Predicate[Kid] to Predicate[Boy] (that is, for any T extending S, you can assign a value of type Predicate[S] to a variable of type Predicate[T]).

If a type is invariant in its type parameter, neither of the above can be done (as is demonstrated by JList).

Note the correspondence between parameterized types and their parameters:

T <: S   ===>   List     [T] <: List     [S]  (covariance)
T <: S   ===>   Predicate[S] <: Predicate[T]  (contravariance)

This is the reason why the first effect is called *co*variance (T <: S on the left, and
..T.. <: ..S.. on the right), and the second is *contra*variance (T <: S on the left, but ..S.. <: ..T.. on the right).

Whether to make your own parameterized types covariant or contravariant or invariant depends on your class responsibilities. If it may only return values of generic type, then it makes sense to use covariance. List[T], for example, only contains methods which return T, never accept T as a parameter, so it is safe to make it covariant in order to increase expressiveness. Such parameterized types can be called producers.

If your class only accepts values of the generic type as a parameter, not returns them (exactly like Predicate above which has single method def apply(obj: T): Boolean), then you can safely make it contravariant. Such parameterized types can be called consumers

If your class both accepts and returns values of the generic type, i.e. it is both a producer and a consumer, then you have no choice but to leave the class invariant in this generic type parameter.

This idiom is usually called "PECS" ("Producer extends, Consumer super") because variance annotations are written extends and super in Java.