Scala中的类型差异错误在遍历视图上执行foldLeft时

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，因为我并不需要memoize的我所有的结果。

这可能看起来像一个奇怪的要求。 原因我想这样做是因为执行foldLeft而不是Traversable视图提供了一种有效的方式来实现lazy depth first search。

Answer 1

视图不会在整个++操作中维护包含元素的标识。我很确定这是一个错误。您可以通过铸造修复：

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，而不是各种不同的意见。

Answer 2

这是一个解决方法（在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对象提供了a dummy instance，但它是奇怪的类型（或者至少对我来说这种类型看起来很奇怪 - 也许有一个合理的解释）。

在任何情况下，将您自己的适当类型的虚拟实例放入作用域中，至少现在是这样。