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

我想编写一个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
}

如何解决此编译错误？ (我更想了解如何实现这种功能，而不是为我自己实现该功能的库，因此，非常感谢我解释为什么我的代码不起作用。)

最佳答案

让我们从代码为什么不起作用开始。首先，您不小心使用了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来解决此问题，但是我觉得这在人们原本期望的情况下欺骗了人们摆脱并行性。迫使 call 者决定是否要放弃并行性；不要对他们隐瞒。