1

受这个问题的启发，我想在 Scala 中实现一个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自动获取联合、差异等的定义。以下所有内容都将成立：

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

另一种方法是继承 from Map[A, Int]，这会给我A => Int我想要的，但是我必须定义我自己的所有++,--等，因为在Map这些中将定义(A, Int)成对，但对于多集，它们需要定义在 As.

我想第三种方法是同时放弃Setand Map，只实现一个新的子类Iterable或其他。

你会推荐什么？适合MulitSetScala 集合框架的最佳方法是什么？

4

1 回答 1

1

但是，我将不得不覆盖一些继承的方法，例如 intersect，因为它们会对多重集做错误的事情

我认为你必须硬着头皮去做。

扩展 Set 的另一个问题是，我不能让 MultiSet 成为A => Int

实际上，您不能Function1使用不同的类型参数继承两次相同的特征（此处）。实际上在这种情况下，这不仅是一个令人讨厌的技术限制，而且这样做实际上没有多大意义，因为在调用时apply无法知道要调用哪个重载：def apply( key: A ): Boolean或者def apply( key: A ): Int？您无法分辨，因为参数列表是相同的。

但是，您可以做的是添加从MultiSet[A]to的隐式转换A => Int。这样，MultiSet默认情况下 a 被视为 a A => Boolean（作为任何集合），但可以A => Int在 nedded 时强制为 a （特别是它可以直接传递给期望函数的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)
于 2013-02-25T12:35:12.743 回答