2

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

我可以像这样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)

但是，如果我尝试对 a 做同样的事情，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因为我不需要记住我的所有结果。

这似乎是一个奇怪的要求。我想这样做的原因foldLeft是因为执行视图提供Traversable了一种有效的方法来实现惰性深度优先搜索。

4

2 回答 2

4

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

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

于 2012-11-21T19:31:34.380 回答
3

视图不会跨++操作维护所包含元素的身份。我很确定这是一个错误。您可以通过强制转换来修复它：

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，而不是使用各种不同的视图。

于 2012-11-21T19:08:28.960 回答