scala - 在 Scala 中合并两个可迭代对象

Question

我想写一个merge采用两个可迭代对象并将它们合并在一起的方法。 (也许合并不是描述我想要的最好的词，但为了这个问题，它是无关紧要的)。我希望这种方法可以通用以处理不同的具体迭代。

例如，merge(Set(1,2), Set(2,3))应该返回 Set(1,2,3)和merge(List(1,2), List(2,3))应该返回 List(1, 2, 2, 3) .我做了以下天真的尝试，但编译器提示 res 的类型: 是Iterable[Any]而不是 A .

def merge[A <: Iterable[_]](first: A, second: A): A = {
    val res = first ++ second
    res
}

如何修复此编译错误？ (我更感兴趣的是了解如何实现这样的功能，而不是为我完成它的库，因此非常感谢解释为什么我的代码不起作用。)

Answer 1

让我们从您的代码不起作用的原因开始。首先，您不小心使用了 existential type 的缩写语法。 ，而不是实际使用绑定(bind)在更高种类类型上的类型。

// What you wrote is equivalent to this
def merge[A <: Iterable[T] forSome {type T}](first: A, second: A): A

即使修复它也不能完全得到你想要的。

def merge[A, S[T] <: Iterable[T]](first: S[A], second: S[A]): S[A] = {
  first ++ second // CanBuildFrom errors :(
}

这是因为 ++不使用类型边界来实现其多态性，它使用隐式 CanBuildFrom[From, Elem, To] . CanBuildFrom负责给予适当的 Builder[Elem, To] ，这是一个可变缓冲区，我们用它来构建所需类型的集合。

所以这意味着我们将不得不给它 CanBuildFrom它如此渴望，一切都会正常吗？

import collection.generic.CanBuildFrom

// Cannot construct a collection of type S[A] with elements of type A 
// based on a collection of type Iterable[A]
merge0[A, S[T] <: Iterable[T], That](x: S[A], y: S[A])
  (implicit bf: CanBuildFrom[S[A], A, S[A]]): S[A] = x.++[A, S[A]](y)

没有 :(。

我已将额外的类型注释添加到 ++使编译器错误更相关。这告诉我们的是，因为我们没有专门覆盖 Iterable的++用我们自己的任意S , 我们使用 Iterable的实现，恰好采用隐式 CanBuildFrom从 Iterable 构建给我们的S .

顺便说一句，@ChrisMartin 遇到了这个问题(整个事情真的是对他的回答的冗长评论)。

不幸的是，Scala 不提供这样的 CanBuildFrom , 所以看起来我们将不得不使用 CanBuildFrom手动。

所以我们去兔子洞……

让我们首先注意到 ++实际上实际上最初是在 TraversableLike 中定义的所以我们可以定制merge更一般一点。

def merge[A, S[T] <: TraversableLike[T, S[T]], That](it: S[A], that: TraversableOnce[A])
  (implicit bf: CanBuildFrom[S[A], A, That]): That = ???

现在让我们实际实现该签名。

 import collection.mutable.Builder

 def merge[A, S[T] <: TraversableLike[T, S[T]], That](it: S[A], that: TraversableOnce[A])
  (implicit bf: CanBuildFrom[S[A], A, That]): That= {
    // Getting our mutable buffer from CanBuildFrom
    val builder: Builder[A, That] = bf()
    builder ++= it
    builder ++= that
    builder.result()
  }

请注意，我已更改 GenTraversableOnce[B] * 至 TraversableOnce[B] **。这是因为只有这样才能使 Builder的++=工作是有顺序访问***。这就是 CanBuildFrom 的全部内容。 .它为您提供了一个可变缓冲区，您可以在其中填充所需的所有值，然后使用 result 将缓冲区转换为所需的输出集合。 .

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

scala> merge(Set(1, 2, 3), Set(2, 3, 4))
res1: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)

scala> merge(List(1, 2, 3), Set(1, 2, 3))
res2: List[Int] = List(1, 2, 3, 1, 2, 3)

scala> merge(Set(1, 2, 3), List(1, 2, 3)) // Not the same behavior :(
res3: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

简而言之，CanBuildFrom机器可以让你构建代码来处理我们经常希望在 Scala 集合的继承图的不同分支之间自动转换的事实，但这是以一些复杂性和偶尔不直观的行为为代价的。相应地权衡取舍。

脚注 :

*我们可以“遍历”至少“一次”的“通用”集合，但可能不会更多，以某种顺序可能是顺序的，也可能不是顺序的，例如也许是平行的。

** 与 GenTraversableOnce 相同除了不是“通用”，因为它保证顺序访问。

*** TraversableLike通过强行调用 seq 来解决这个问题在 GenTraversableOnce在内部，但我觉得这在人们可能期望的情况下欺骗了他们的并行性。强制调用者决定是否要放弃并行性；不要为他们做隐形。