9

他の2つのコレクションに基づいてコレクションを返す一般的なアルゴリズムを実装しています。問題は次のように簡略化できます

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の場合と同じではありません。マップは同様のアプローチを使用します。

マップの例：

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を適用すると、リストが作成されます。

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にaddを適用すると、目的の結果が得られます。

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

質問： すべての種類のトラベサブル（Mapと同様に実装されたコレクションを含む）に対して、++メソッドを直接使用した場合と同じ結果になるようにaddを実装する方法はありますか？私はクラスAのコンパニオンオブジェクトに暗黙のCanBuildFromを実装しようとしていましたが、運がありませんでした。Mapでも機能しないため、問題はコレクションの実装ではなく、アルゴリズムにあるように思われます。

4

1 に答える 1

9

addがのエイリアスにすぎないことを考えるとTraversableLike.++、最初のステップは++の署名を調べることです。

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

次にthis、最初のパラメーターとthat2 番目のパラメーターに変換するだけです。

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。現状では (特別なことは何もせずに) のインスタンスに適用される addは、 の代わりにをA返します。IterableA

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

これが私がtibkeringで思いついたものCanBuildFromです。これが最良の例であると保証することはできませんが、動作します (つまり、 をA呼び出したときに as resultが得られるということです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))
于 2013-01-30T10:47:18.900 に答える