Scala generics - Why scala returns an instance of supertype instead of the subtype when type constraint is used?

Question

I'm trying to transform y into something which can be appended to x, where x is a sequence of some sorts.

scala> def foo[U <: Seq[T], T](x: U, y: T): U = x :+ y
<console>:7: error: type mismatch;
 found   : Seq[T]
 required: U
       def foo[U <: Seq[T], T](x: U, y: T): U = x :+ y
                                                  ^

I have the following solutions:

def foo[T]( x : Seq[T], y:T) = x :+ y
def foo[T]( x : Seq[T], y:T) : Seq[T] = x :+ y
def foo[U <: Seq[T], T](x: U, y: T): U = (x :+ y).asInstanceOf[U]

But my doubt is why the original one didn't work. It looks like if I apply an operator (:+ in this case) defined in the super class then it returns the super class? i.e if U is a Vector, foo returns Seq, so I'm getting error required "U" but found "Seq[T]".

Can anyone enlighten me why this behavior is seen?

Answer 1

When coming across type problems, I usually adopt the "if it passes the compilation, what will happen" logic to find the unreasonable part.

In your case, assuming the original one is Okay.

 def foo[U <: Seq[T], T](x: U, y: T): U = x :+ y

cause Seq[T] is covariant on T, so the following case stands.

 for type A, T, if A <: T, List[A] <: Seq[T]

Then we can do the following operation:

 class Parent 
 class Child extends Parent

 // List(new Child) :+ (new Parent) => List[Parent]
val result = foo(List(new Child), new Parent)

U is actually List[Child] in the foo method, but when List operates with a different type from its element type, it will try to find the common parent, in this case result is typed with List[Parent], but the required type is List[Child]. Obviously, List[Parent] is not a subtype of List[Child].

So, the thing is the final type is elevated but the required type is a subtype of the elevated type. If you look at the definition of Scala SeqLike, this may be clearer.

trait SeqLike[+A, +Repr] extends ... {
    def :+[B >: A, That](elem: B)(...): That = {
       ...
    }
}