實現一個multiset /包作爲斯卡拉集合

Question

受this question的啓發，我想在斯卡拉實現一個Multiset。我想一個MultiSet[A]到：

• 支持添加，刪除，並集，交集和差
• 是A => Int，提供每個元素的計數

這裏有一個方法，延長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自動克工會，差異等所有ETS定義下面將舉行：

// 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另一個問題是，那麼我不能有MultiSet是A => Int，因爲我得到的錯誤：illegal inheritance; class MultiSet inherits different type instances of trait Function1: A => Int and A => Boolean。我可以通過聲明一個單獨的方法來解決這個問題，比如count方法，但我更喜歡這個類只是一個A => Int。

另一種方法是從Map[A, Int]繼承，這會給我我想要的A => Int，但我必須定義自Map這些將在(A, Int)對來定義所有的我自己++，--等。 ，但對於multiset，他們需要通過A來定義。

我想第三種方法是放棄Set和Map，只是實現一個新的子類Iterable或其他什麼。

你會推薦什麼？在Scala集合框架中適合MulitSet的最佳方法是什麼？

Answer 1

However, I would have to override some inherited methods like intersect because they would do the wrong things for multisets

我想你必須硬着頭皮來做那件事。

Another problem with extending Set is that then I can't have MultiSet be an A => Int

事實上，你不能繼承相同的特質兩次（在這裏Function1）與不同類型的參數。實際上，在這種情況下，這不僅僅是一個令人討厭的技術限制，但是這樣做實際上沒有什麼意義，因爲撥打apply時，無法知道您要撥打哪個超載：def apply(key: A): Boolean或def apply(key: A): Int？你不能說因爲參數列表是相同的。

但是，您可以做的是添加從MultiSet[A]到A => Int的隱式轉換。這樣，MultiSet在默認情況下被視爲A => Boolean（作爲任何集合），但在被約束時可以強制爲A => Int（特別是它可以直接傳遞給期望A => 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)