Overriding variance in subtype

Question

Can someone explain to me why example 1 compiles but example 2 does not?

Example 1:

trait Foo[+A]
trait Bar[A] extends Foo[A]

Example 2:

trait Foo[A[+_]]
trait Bar[A[_]] extends Foo[A]

Example 2 does not compile with the following error message: "kinds of the type arguments (A) do not conform to the expected kinds of the type parameters (type A) in trait Foo. A's type parameters do not match type A's expected parameters: type _ (in trait Bar) is invariant, but type _ (in trait Foo) is declared covariant"

Answer 1

In Example 1, the +A is not constraint on A. Any type can be a parameter of Foo. It is a constraint on Foo. It means in the interface of Foo, A can appear only in covariant position (shortly, it may be a method result, but not a method parameter).

Having Bar not covariant means that the interface of Bar does not satisfy the same constraint (or at least does not advertise it), so maybe in Bar, a method with an A parameter was added. This is quite common. For instance there is collection.Seq[+A], and it is extended by collection.mutable.Seq[A]. This poses no soundess problem. If Y <: X, a Bar[Y] is not a Bar[X], but it is still a Foo[X].

On the other hand, in example 2, the A[+_] is a constraint on A. Only types with a covariant type parameter may be parameters of Foo. The code of Foo is likely to make use of that constraint, e.g an assignement of an A[String] to a A[Any] somewhere in the code of Foo.

Then allowing Bar to be instanciated with a not-covariant type would be unsound. The code inherited from Foo could still be called and assign the A[String] to the A[Any], when A is no longer covariant.

A very similar soundness problem would happen anytime you allow lifting a constraint on a generic parameter. Suppose you have Foo[X <: Ordered[X]] (or Foo[X : ordering]) and you have a method sort in Foo. Suppose then that Bar[X] extends Foo is allowed. Maybe nothing in the code of Bar requires X to be ordered, but still, sort would be callable, and would certainly misbehave with items that cannot be ordered.

---

Regarding your question in the comment with Traversable[+Elem, +Col[+_]], and extending that into make a mutable class :

technically, yes, you can extend it and put some var youCanMutateThat : Elem = _ inside. I guess this is not what you are looking for. But I suppose your plan is to allow using the extension with mutable Col, and I don't think you can do that, for the reason stated above. But then, why did you have the Col[+_] constraint in the first place?

Answer 2

In Example 2 need to add covarince for A[_]

trait Bar[A[+_]] extends Foo[A]

Because Foo expect covariant type as parameter (+_ is a part of constraint for substituted type) and inherited type need guarantee that parameter will be covariant (limitation of substituted type).

In Example 1 you define that Foo (like container) is covariant by parameter and inherited container can be invariant (no limitation for substituted type)

more details in Martin-Löf type theory (predicative parametric polymorphism)