1

この質問に触発されて、Scalaにマルチセットを実装したいと思います。私はしたいMultiSet[A]：

  • 追加、削除、和集合、共通部分、および差異のサポート
  • でありA => Int、各要素の数を提供します

これが1つのアプローチであり、拡張しSetます。

import scala.collection.immutable.Map
import scala.collection.immutable.Set
import scala.collection.SetLike
import scala.collection.mutable.Builder

class MultiSet[A](private val counts: Map[A, Int] = Map.empty[A, Int])
extends SetLike[A, MultiSet[A]] with Set[A] {
  override def +(elem: A): MultiSet[A] = {
    val count = this.counts.getOrElse(elem, 0) + 1
    new MultiSet(this.counts + (elem -> count)) 
  }
  override def -(elem: A): MultiSet[A] = this.counts.get(elem) match {
    case None => this
    case Some(1) => new MultiSet(this.counts - elem)
    case Some(n) => new MultiSet(this.counts + (elem -> (n - 1)))
  }
  override def contains(elem: A): Boolean = this.counts.contains(elem)
  override def empty: MultiSet[A] = new MultiSet[A]
  override def iterator: Iterator[A] = {
    for ((elem, count) <- this.counts.iterator; _ <- 1 to count) yield elem
  }
  override def newBuilder: Builder[A,MultiSet[A]] = new Builder[A, MultiSet[A]] {
    var multiSet = empty
    def +=(elem: A): this.type = {this.multiSet += elem; this}
    def clear(): Unit = this.multiSet = empty
    def result(): MultiSet[A] = this.multiSet
  }
  override def seq: MultiSet[A] = this
}

object MultiSet {
  def empty[A]: MultiSet[A] = new MultiSet[A]
  def apply[A](elem: A, elems: A*): MultiSet[A] = MultiSet.empty + elem ++ elems
  def apply[A](elems: Seq[A]): MultiSet[A] = MultiSet.empty ++ elems
  def apply[A](elem: (A, Int), elems: (A, Int)*) = new MultiSet((elem +: elems).toMap)
  def apply[A](elems: Map[A, Int]): MultiSet[A] = new MultiSet(elems)
}

拡張は、結合、差異などの定義を自動的に取得Setすることを意味するため、便利です。次のすべてが当てはまります。MultiSet

// add
assert(
  MultiSet("X" -> 3, "Y" -> 1) + "X" ===
    MultiSet("X" -> 4, "Y" -> 1))
assert(
  MultiSet("X" -> 3, "Y" -> 1) + "Z" ===
    MultiSet("X" -> 3, "Y" -> 1, "Z" -> 1))

// remove
assert(
  MultiSet("a" -> 2, "b" -> 5) - "b" ===
    MultiSet("a" -> 2, "b" -> 4))
assert(
  MultiSet("a" -> 2, "b" -> 5) - "c" ===
    MultiSet("a" -> 2, "b" -> 5))

// add all
assert(
  MultiSet(10 -> 1, 100 -> 3) ++ MultiSet(10 -> 1, 1 -> 7) ===
    MultiSet(100 -> 3, 10 -> 2, 1 -> 7))

// remove all
assert(
  MultiSet("a" -> 2, "b" -> 5) -- MultiSet("a" -> 3) ===
    MultiSet("b" -> 5))

ただし、のようないくつかの継承されたメソッドをオーバーライドする必要があります。これは、マルチセットに対して間違った処理を行うためです。たとえば、次のようにはなりませんunion。intersect

// union (takes max of values)
assert(
  MultiSet(10 -> 5, 1 -> 1).union(MultiSet(10 -> 3, 1 -> 7)) ===
    MultiSet(10 -> 5, 1 -> 7))

// intersection (takes min of values)
assert(
  MultiSet(10 -> 5, 100 -> 3).intersect(MultiSet(10 -> 1, 1 -> 7)) ===
    MultiSet(10 -> 1))

拡張に関する別の問題は、エラーが発生するため、私はそうするSetことができないということです。たとえば、別のメソッドを宣言することでこれを回避できますが、クラスを単ににすることを強くお勧めします。MultiSetA => Intillegal inheritance; class MultiSet inherits different type instances of trait Function1: A => Int and A => BooleancountA => Int

別のアプローチは、から継承するMap[A, Int]ことです。これにより、必要なものが得られますが、これらはペアで定義されるためA => Int、自分の、などをすべて定義する++必要--がありますが、マルチセットの場合は定義する必要があります。 s以上 。Map(A, Int)A

Set3番目のアプローチは、との両方をあきらめてMap、の新しいサブクラスなどを実装することだと思いIterableます。

あなたは何をお勧めします？MulitSetScalaコレクションフレームワーク内に収まるための最良の方法は何ですか？

4

1 に答える 1

1

ただし、intersectなどの継承されたメソッドは、マルチセットに対して間違った処理を行うため、オーバーライドする必要があります。

弾丸を噛んでそれをしなければならないと思います。

Setを拡張する際の別の問題は、MultiSetをA => Int

Function1実際、異なるタイプのパラメーターを使用して、同じ特性（ここ）を2回継承することはできません。そして実際には、この場合、これは単に厄介な技術的制限ではありませんが、呼び出すときにapplyどのオーバーロードを呼び出したいかを知る方法がないため、実際にはあまり意味がありません：def apply( key: A ): Booleanまたはdef apply( key: A ): Int？引数リストは同じなのでわかりません。

ただし、できることは、からMultiSet[A]への暗黙の変換を追加することA => Intです。このように、aはデフォルトで（任意のセットとして）MultiSetとして扱われますが、必要に応じて強制的に強制することができます（特に、関数を期待する関数に直接渡すことができます）。A => BooleanA => IntA => Int

class MultiSet[A] ... {
  ...
  def count(elem: A): Int = counts.getOrElse( elem, 0 )
}
object MultiSet {
  ...
  implicit def toCountFunc[A]( ms: MultiSet[A] ): A => Int = { 
    (x: A) => ms.count( x )
  } 
}

REPLでのいくつかのテスト：

scala> val ms = MultiSet("a" -> 2, "b" -> 5)
ms: MultiSet[String] = Set(a, a, b, b, b, b, b)
scala> ms("a")
res17: Boolean = true
scala> ms("c")
res18: Boolean = false

scala> def testExists( f: String => Boolean, keys: String *) {
     |   println( keys.map( f ).toList )
     | }
testExists: (f: String => Boolean, keys: String*)Unit
scala> testExists( ms, "a", "c" )
List(true, false)

scala> def testCounts( f: String => Int, keys: String *) {
     |   println( keys.map( f ).toList )
     | }
testCounts: (f: String => Int, keys: String*)Unit
scala> testCounts( ms, "a", "c" )
List(2, 0)
于 2013-02-25T12:35:12.743 に答える