Scala: Type mismatch, returns BlockList[Any] instead of BlockList[R]

Question

Just to get more experience with Scala, and as an experiment, I'm implementing a class that has a List-like API, but is implemented as a list of IndexedSeq with an index to the first element; tail just returns a copy with the index incremented, and prepending Arrays is O(1), while appending Arrays is O(m), m = length of list <= number of elements.

I'm running into problems with my function return types. Pretty much every method has the type parameters [R >: T : ClassManifest, A <: R : ClassManifest], T being the type parameter of BlockList. Sometimes these methods just return others, but in those situations I get an error from Eclipse saying that it was looking for type BlockList[R] but found type BlockList[Any]. Shouldn't R be the lowest common super type of both T and A? In which case, the second method call should also return BlockList[R], right? What am I not getting? I reflect ClassManifest a lot to overcome the problems of type erasure, but I don't know if it's still a problem.

The errors are from the definitions of |: and :|.

import collection.immutable.List
import reflect.ClassManifest
import annotation.tailrec

sealed abstract
class BlockList [+T] extends Seq[T] with Product {
...
}

object EmptyBlock extends BlockList[Nothing] {
...
}

class Build [T: ClassManifest](
private val block: IndexedSeq[T],
private val next: BlockList[T] = EmptyBlock,
private val index: Int = 0
) extends BlockList[T] {
require(!block.isEmpty && index >= 0 && index < block.length)

override def |: [R >: T : ClassManifest, A <: R] (x: A): BlockList[R] =
    Array[R](x) |: this //Return type error here

override def |: [R >: T : ClassManifest, A <: R : ClassManifest]
(blk: IndexedSeq[A]): BlockList[R] =
    if (blk isEmpty) this
    else new Build[R](blk, this)

override def :| [R >: T : ClassManifest, A <: R] (x: A): BlockList[R] =
    this :| Array[R](x) //Return type error here

override def :| [R >: T : ClassManifest, A <: R : ClassManifest]
(blk: IndexedSeq[A]): BlockList[R] = 
    if (blk isEmpty) this
    else new Build[R](block, next :| blk, index) //Type error here

}

Answer 1

Shouldn't R be the lowest common super type of both T and A?

No, because R is an upper bound. R can be any super class of T, and the only class that satisfies that bound is Any.

Imagine, for instance, that R was AnyRef -- you could then call methods such as eq on it, which would break if an Int was passed.

So, while R can be something lower than Any (and probably will be most of the time), at the time you declare it one cannot assume it to be anything lower than Any.

However, I think the above has nothing whatsoever to do with your problem. The errors you report appear in these lines, right?

Array[R](x) |: this
this :| Array[R](x)

The other one also has an :| in it. You don't show any implicit conversion from Array to Build, and none of the :| methods take an Array as parameter (arrays are not IndexedSeq).

So, when you write

this :| Array[R](x)

This would call def |: [R1 >: T : ClassManifest, A <: R1] (x: A): BlockList[R1] (I've changed R to R1 nto to confuse with the R in the parameter), where the type of A is Array[R], and the only supertype of T and Array[R] is Any, so R1 has to be Any, but that Any is different than R.

Perhaps, if you called it this.:|[R, Array[R]](Array[R](x)), it would move things a little further. With the missing definitions that allowArray` to be passed, I can't predict much else.