In Scala, why do I get this "polymorphic expression cannot be instantiated to expected type"?

Question

Why does the following occur in Scala 2.9.0.1?

scala> def f(xs: Seq[Either[Int,String]]) = 0
f: (xs: Seq[Either[Int,String]])Int

scala> val xs = List(Left(0), Right("a")).iterator.toArray
xs: Array[Product with Serializable with Either[Int,java.lang.String]] = Array(Left(0), Right(a))

scala> f(xs)
res39: Int = 0

scala> f(List(Left(0), Right("a")).iterator.toArray)
<console>:9: error: polymorphic expression cannot be instantiated to expected type;
 found   : [B >: Product with Serializable with Either[Int,java.lang.String]]Array[B]
 required: Seq[Either[Int,String]]
       f(List(Left(0), Right("a")).iterator.toArray)
                                            ^

Update: Debilski suggests a better example (not 100% sure this is demonstrating the same underlying phenomenon):

Seq(0).toArray : Seq[Int] // compiles
Seq(Some(0)).toArray : Seq[Option[Int]] // doesn't

Answer 1

The best person to explain this is Adriaan Moors, and he already did that here on Stack Overflow -- lookup answers from him and you'll find it.

Anyway, the problem is that the type of List(Left(0), Right("a")).iterator.toArray cannot be inferred within the boundaries expected by f. It does not conform to Seq[Either[Int, String]] without an implicit conversion, and no implicit conversion can be applied because it (the type) cannot be determined. It's like an egg&chicken problem.

If you use <% or assign it to a val, you break the cycle in the inference.

Answer 2

This has nothing to do with Either but rather with Array handling. If you convert it manually to a Seq it works:

scala> f(xs.toSeq)
res4: Int = 0

A Scala Array is not a Seq (because it is in fact a Java array). But a WappedArray is. You could also redefine your function f has:

scala> def f[A <% Seq[Either[Int,String]]](xs: A) = 0
f: [A](xs: A)(implicit evidence$1: (A) => Seq[Either[Int,String]])Int

scala> f(xs)
res5: Int = 0

BTW, no need to get an iterator before calling toArray.