在Scala中对Traversable视图执行foldLeft操作时，键入variance错误

Question

我试图在Scala中使用foldLeft运算符连接一系列Traversable视图，但遇到了我不理解的类型方差错误。

我可以使用reduce来连接Traversable视图的列表，就像这样

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)

(注意，我必须在reduce参数上写类型注释：reduce(_ ++ _)不编译。我不明白为什么，也很感激对此的解释。)

我还可以将列表分解为头部和尾部，并将它们连接起来。

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)

但如果我尝试对foldLeft做同样的事情，我会得到类型方差错误。

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)

我怀疑这个问题与Traversable[_]中的存在类型有关，但我不知道我到底做错了什么。我在上面的表达式中尝试了各种类型的签名，但都没有成功。从Stackoverflow上的其他问题来看，foldLeft的键入有些棘手，但我找不到解决这个问题的方法。

相比之下，与Stream相同的算法可以顺利工作。

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

以上是我想做的，只是我想使用视图而不是Stream，因为我不需要记住所有的结果。

这似乎是一个奇怪的请求。我想用这种方式做事情的原因是，在Traversable视图上执行foldLeft提供了一种实现延迟深度优先搜索的有效方法。

Answer 1

这里有一个解决方法(在2.9.2和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(_ ++ _)

它既编译又做我们想要的事情：

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

即使使用(_ ++ _)语法，左折叠版本也可以使用。

问题是++方法需要一个隐式的CanBuildFrom实例，但实际上并没有使用它。TraversableView对象提供了一个伪实例，但它的类型很奇怪(或者至少我觉得这个类型很奇怪——也许对此有合理的解释)。

在任何情况下，将您自己的适当类型的伪实例放入作用域都是可行的，至少目前是这样。

Answer 2

视图不维护++操作中所包含元素的标识。我确信这是一个错误。你可以通过铸造来修复它

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

在折叠情况下：

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

不过要小心！一旦您开始显式强制转换，您的类型安全性就会大大降低(即，由您决定是否不犯错误)。

我想这是观点没有被大量使用的症状。如果可能的话，我通常会尝试使用Iterator，而不是各种不同的观点。