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

Question

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

例如，merge(Set(1,2), Set(2,3))should returnSet(1,2,3)和 merge(List(1,2), List(2,3))should return List(1, 2, 2, 3)。我做了以下幼稚的尝试，但编译器抱怨res: It isIterable[Any]而不是A.

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

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

Answer 1

让我们从为什么您的代码不起作用开始。首先，您不小心使用了存在类型的缩写语法，而不是实际使用绑定在更高级类型上的类型。

// 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覆盖's++为我们的任意S，我们正在使用它的Iterable's 实现，它恰好采用了CanBuildFrom从Iterable's 到我们的构建的隐式S.

顺便说一句，这是@ChrisMartin 遇到的问题（这整件事确实是对他的回答的冗长评论）。

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

所以在兔子洞里我们走...

让我们首先注意到它++实际上最初是在 in 中定义的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“General”不同，因为它保证顺序访问。

*** TraversableLike解决此获得通过强制调用seq在GenTraversableOnce内部，但我觉得这样的欺骗人了并行时，他们可能原本预期它。强制调用者决定是否要放弃并行性；不要在无形中为他们做这件事。