Type variance error in Scala when doing a foldLeft

Question

I am trying concatenate a series of Traversable views in Scala using a foldLeft operator and am hitting type variance errors that I don't understand.

I can use reduce to concatenate a list of Traversable views like so.

val xs = List(1,2,3,4).map(Traversable(_).view).reduce((a: TraversableView[Int, Traversable[_]], b: TraversableView[Int, Traversable[_]]) => a ++ b) // TraversableView[Int,Traversable[_]]
// xs.force returns Traversable[Int] = List(1, 2, 3, 4)

(Note that I have to write the type annotation on the reduce arguments: reduce(_ ++ _) does not compile. I don't understand why and would be grateful for an explanation of this too.)

I can also break the list up into a head and a tail and concatenate them.

import collection.TraversableView
val ns = List(1,2,3,4)
val h = Traversable(ns.head).view
val t = ns.tail.map(Traversable(_).view).reduce((a: TraversableView[Int, Traversable[_]], b: TraversableView[Int, Traversable[_]]) => a ++ b)
val xs = h ++ t // TraversableView[Int,Traversable[_]]
// xs.force returns Traversable[Int] = List(1, 2, 3, 4)

But if I try to do the same thing with a foldLeft I get type variance errors.

import collection.TraversableView
val ns = List(1,2,3,4)
val h = Traversable(ns.head).view
val t = ns.tail.map(Traversable(_).view)
val xs = (h /: t)((a: TraversableView[Int, Traversable[_]], b: TraversableView[Int, Traversable[_]]) => a ++ b)
<console>:14: error: type mismatch;
 found   : scala.collection.TraversableView[Int,Traversable[_]]
 required: java.lang.Object with scala.collection.TraversableView[Int,Traversable[Int]]
              (h /: t)((a: TraversableView[Int, Traversable[_]], b: TraversableView[Int, Traversable[_]]) => a ++ b)

I suspect the issue has to do with the existential type in Traversable[_], but I can't figure out what exactly I'm doing wrong. I've tried various type signatures in the above expression to no avail. Judging from other questions on Stackoverflow, there is something tricky about the typing of foldLeft, but I couldn't find one that addresses this issue.

For comparison, the same algorithm with Stream works without a hitch.

val xs = (1 #:: Stream.empty /: List(2,3,4).map(_ #:: Stream.empty))(_ ++ _)
// xs.force returns Stream[Int] = Stream(1, 2, 3, 4)

The above is what I want to do, except I want to use a view instead of Stream because I don't need to memoize all my results.

This might seem like an odd request. The reason I want to do things this way is because performing foldLeft over Traversable views provides an efficient way to implement a lazy depth first search.

Answer 1

Here's a workaround (tested on 2.9.2 and 2.10.0-RC2):

import scala.collection.TraversableView

implicit def `I'm a lie!`[A]: collection.generic.CanBuildFrom[
  TraversableView[A, Traversable[A]], A, TraversableView[A, Traversable[A]]
] = null

val xs = List(1, 2, 3, 4).map(Traversable(_).view).reduce(_ ++ _)

Which both compiles and does what we want:

scala> xs.toList
res0: List[Int] = List(1, 2, 3, 4)

The left fold version will also work, even with the (_ ++ _) syntax.

The issue is that the ++ method expects an implicit CanBuildFrom instance, but it doesn't actually use it. The TraversableView object provides a dummy instance, but it's bizarrely typed (or at least the type seems odd to me—maybe there's a reasonable explanation for it).

In any case putting your own appropriately typed dummy instance into scope works, for now at least.

Answer 2

Views don't maintain the identity of the contained element across ++ operations. I'm pretty sure that this is a bug. You can fix it by casting:

val xs = List(1,2,3,4).map(Traversable(_).view).
  reduce((a,b) => (a ++ b).asInstanceOf[TraversableView[Int,Traversable[Int]]])

In the fold case also:

val xs = (Traversable(1).view /: List(2,3,4).map(x => Traversable(x).view)){ (l,r) =>
  (l ++ r).asInstanceOf[TraversableView[Int,Traversable[Int]]]
}

Be careful, though! Once you start explicitly casting, your type safety goes way down (i.e. it is up to you to not make a mistake).

I'd guess this is a symptom of views not being very heavily used. I generally try to use Iterator if at all possible rather than various different views.