scala - 如何在Scala中为任何Traversable实现通用算法？

Question

我正在实现一种通用算法，以基于其他两个集合返回一个集合。
问题可以简化为

def add[Repr <: Traversable[_]](coll1: Repr, coll2: Repr) = coll1 ++ coll2

当我在定义为的集合A上应用算法时发生了问题

class A[T] extends Iterable[(Int,T)] with IterableLike[(Int,T), A[T]] { ... }

即A的类型参数与继承的Iterable不同。 map 使用类似的方法。

map 示例:

scala> val m1 = Map("a" -> 1, "b" -> 1, "c" -> 1)
m1: scala.collection.immutable.Map[java.lang.String,Int] = Map(a -> 1, b -> 1, c -> 1)

scala> val m2 = Map("a" -> 2, "c" -> 1)
m2: scala.collection.immutable.Map[java.lang.String,Int] = Map(a -> 2, c -> 1)

应用以m1和m2作为参数的add会得到一个List:

scala> add(m1,m2)
res3: Traversable[Any] = List((a,1), (b,1), (c,1), (a,2), (c,1))

...而所需的结果类似于直接使用++方法:

scala> m1 ++ m2
res0: scala.collection.immutable.Map[java.lang.String,Int] = Map(a -> 2, b -> 1, c -> 1)

使用定义为以下内容的集合B不会发生此问题:

class B[T] extends Iterable[T] with IterableLike[T, B[T]] { ... }

例如，队列以类似的方式实现。

队列示例:

scala> val q1 = Queue(9,2,5)
q1: scala.collection.immutable.Queue[Int] = Queue(9, 2, 5)

scala> val q2 = Queue(7,3,1)
q2: scala.collection.immutable.Queue[Int] = Queue(7, 3, 1)

在q1和q2上应用加法可得到所需的结果:

scala> add(q1,q2)
res4: Traversable[Any] = Queue(9, 2, 5, 7, 3, 1)

问题:
对于所有可交易对象(包括类似于Map实现的集合)，是否有一种实现加法的方法，以使结果与直接使用++方法时的结果相同？我一直在尝试在类A的伴随对象中实现一个隐式CanBuildFrom，但是没有运气。在我看来，问题出在算法上，而不是集合实现上，因为它也不适用于Map。

Answer 1

鉴于add只不过是TraversableLike.++的别名，所以第一步也要看看++的签名:

trait TraversableLike[+A, +Repr] extends ... {
  ...
  def ++:[B >: A, That](that: TraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That
  ...
}

然后，您要做的就是将 this转换为第一个参数，并将 that转换为第二个参数:

import collection.TraversableLike
import collection.generic.CanBuildFrom
def add[A, Repr, B >: A, That](coll1: TraversableLike[A, Repr], coll2: TraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  coll1 ++ coll2
}

更新:我还研究了要使 A相对于 add正常运行，您需要做些什么。就目前而言(不做任何特殊的事情)，在 A实例上应用add会返回 Iterable而不是 A:

import collection.{IterableLike, TraversableLike}
// Dummy `A` implementation, for illustration
class A[T]( val inner: Seq[(Int, T)] ) extends Iterable[(Int,T)] with IterableLike[(Int,T), A[T]] {
  def iterator: Iterator[(Int, T)] = inner.iterator
  override protected[this] def newBuilder: scala.collection.mutable.Builder[(Int, T),A[T]] = ???
  def :+(elem: (Int, T) ): A[T] = new A[T]( inner :+ elem )
}
object A  {
  def apply[T]( elems: (Int, T)* ) = new A( elems )
}
val a1 = A( 1-> "one", 2 -> "two" )
val a2 = A( 3-> "three", 4 -> "four", 5 -> "five" )
add(a1, a2)

结果是:

res0: Iterable[(Int, String)] = List((1,one), (2,two), (3,three), (4,four), (5,five))

这是我通过 CanBuildFrom摆弄的东西。我不能保证这是最好的示例，但它确实可以工作(这意味着我们在调用 A时得到 add作为结果):

import collection.IterableLike
import collection.generic.CanBuildFrom
import collection.mutable.Builder

class A[T]( val inner: Seq[(Int, T)] ) extends Iterable[(Int,T)] with IterableLike[(Int,T), A[T]] {
  def iterator: Iterator[(Int, T)] = inner.iterator
  override protected[this] def newBuilder: scala.collection.mutable.Builder[(Int, T),A[T]] = new A.ABuilder[T]
  def :+(elem: (Int, T) ): A[T] = new A[T]( inner :+ elem )
}
object A  {
  private val _empty = new A[Nothing]( Nil )
  def empty[T]: A[T] = _empty.asInstanceOf[A[T]]
  def apply[T]( elems: (Int, T)* ) = new A( elems )

  class ABuilder[T] extends Builder[(Int,T), A[T]] {
    protected var elems: A[T] = empty
    def +=(x: (Int, T)): this.type = { elems = elems :+ x; this }
    def clear() { elems = empty }
    def result: A[T] = elems
  }

  implicit def canBuildFrom[T]: CanBuildFrom[A[_], (Int,T), A[T]] = new CanBuildFrom[A[_], (Int,T), A[T]] {
    def apply(from: A[_]) = apply()
    def apply() = new ABuilder[T]
  }
}

现在的结果是:

res0: A[String] = ((1,one), (2,two), (3,three), (4,four), (5,five))