scala - 在可遍历 View 上执行 foldLeft 时在 Scala 中输入方差错误

Question

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

我可以像这样使用 reduce 连接 Traversable View 列表。

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)

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

这似乎是一个奇怪的请求。我想以这种方式做事的原因是因为在Traversable View 上执行foldLeft 提供了一种有效的方式来实现lazy depth first search .

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 对象提供 a dummy instance , 但它的类型很奇怪(或者至少这种类型对我来说很奇怪——也许对此有一个合理的解释)。

无论如何，将您自己的适当类型的虚拟实例放入作用域是可行的，至少现在是这样。