Scala covariant type error

Question

I tried to define a class

abstract class Sequence[+A] {
    def append (x: Sequence[A]): Sequence[A]
}

and got in the terminal

<console>:8: error: covariant type A occurs in contravariant position in type Sequence[A] of value x
           def append (x: Sequence[A]): Sequence[A]

Why isn't this definition OK and what would be the best way to fix this? I checked this covariant type T occurs in contravariant position but nothing helpful for me there.

Answer 1

As usual given his expertise in Scala, @vptheron is exactly right on the solution. But let me add a little to the "why" with an example inspired by Scala author Martin Odersky himself.

By defining Sequence[+A], you're saying if B is a subtype of A, then Sequence[B] is a subtype of Sequence[A].

I think type stuff makes a lot more sense when you take it out of the abstract (no pun intended) and use a concrete example.

Let's create a concrete implementation:

class IntSequence extends Sequence[Int] {
  override def append(x: Sequence[Int]) = {
    println(math.sqrt(x.head))
    //makes no sense but humor me
  }
}

Covariance in A means that because Int is a subtype of Any, Sequence[Int] is a subtype of Sequence[Any]. So far so good.

Now imagine a concrete class StringSequence defined in a similar way to IntSequence.

Then let's do this:

val x:Sequence[Any] = new IntSequence
val ss:Sequence[Any] = new StringSequence
//Let ss be populated somehow
x.append(ss)

The first line is valid of course. IntSequence is a subclass of Sequence[Int], and Sequence[Int] is a subtype of Sequence[Any] by covariance.

The second line is valid of course. For a similar reason.

The third line (the line after the comment) is valid of course. Sequence[String] is a subclass of Sequence[Any], so I can append a Sequence[String] to a Sequence[Any].

But when I try the two lines together, I have now said that I can take the square root of the first element of my Sequence[String] because x is really a IntSequence.

To borrow a line from the American movie Apollo 13, "Houston, we have a problem."

This is why you get that error. To generalize, as soon as a generic parameter appears as the type of a parameter to a method, the class that contains that method can't be covariant in that type because you get exactly that kind of weirdness.

To get around this, you need a lower bound for the type parameter in the method definition. In other words, the type in the method parameter must be a supertype of the covariant type in the class definition.

Or more simply, do what @vptheron does.

Hope that helps.

Answer 2

This works:

abstract class Sequence[+A]{
  def append[B >: A](x: Sequence[B]): Sequence[B]
}

When you define a covariant type you can't use it as an input parameter (you would have the same problem with a contravariant type used for a returned type). The workaround is to define a new type (here B) that is a super type of A.