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

Question

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

3

我想编写一个“merge”方法，它接受两个可迭代对象并将它们合并在一起。（也许“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
}

我该如何解决这个编译错误？（我更想了解如何实现这样的功能，而不是使用一个为我完成所有工作的库，因此非常感谢对于代码错误原因的解释。）

- Wickoo

2个回答

0

首先，以下是本答案中所有代码所需的导入：

import collection.GenTraversableOnce
import collection.generic.CanBuildFrom

首先查看API文档，以查看Iterable.++的方法签名（请注意，大多数集合的API文档是错误的，您需要单击“完整签名”才能查看真实类型）：

def ++[B >: A, That](that: GenTraversableOnce[B])
  (implicit bf: CanBuildFrom[Iterable[A], B, That]): That

从那里，你可以直接将实例方法翻译成函数：

def merge[A, B >: A, That](it: Iterable[A], that: GenTraversableOnce[B])
  (implicit bf: CanBuildFrom[Iterable[A], B, That]): That = it ++ that

分解如下：

[A, B >: A, That] — Iterable 有一个类型参数 A，而 ++ 有两个类型参数 B 和 That，因此结果函数具有所有三个类型参数 A、B 和 That
it: Iterable[A] — 该方法属于 Iterable[A]，因此我们将其作为第一个值参数
that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Iterable[A], B, That]): That — 剩余的参数和类型约束直接从 ++ 的签名中复制而来

- Chris Martin

如果我运行您的合并定义在 val x = merge(Set(1, 2, 3), Set(1, 2, 3, 4)) 中，x 的类型是 Iterable[Int]，但我想要 Set[Int]。有没有办法获得最具体的类型？ - Wickoo

哎呀，我以为它可以。肯定是有可能的，我会再多做一些工作。 - Chris Martin

1

抱歉，我已经走投无路了，无能为力。 - Chris Martin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- badcook · Accepted Answer

首先，让我们从为什么你的代码无法工作开始。首先，你不小心使用了存在类型的缩写语法，而不是实际上使用高级类型约束的类型。

// 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)

没有 :(。

我已经为++添加了额外的类型注释，以使编译器错误更加相关。这告诉我们，因为我们没有针对我们任意的S具体覆盖Iterable的++，所以我们正在使用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来解决这个问题，但我觉得这是欺骗人们并行性的方式，因为他们本来可能期望它。强制调用者决定是否放弃并行性；不要为他们隐式地这样做。