title: implement a multiset/bag as Scala collection
body: <p>Inspired by <a href="https://stackoverflow.com/questions/14617024/are-multisets-missing-in-scala">this question</a>, I'd like to implement a <a href="http://en.wikipedia.org/wiki/Multiset_%28abstract_data_type%29#Multiset" rel="nofollow noreferrer">Multiset</a> in Scala. I'd like a <code>MultiSet[A]</code> to:</p>
  
  <ul>
  <li>Support adding, removing, union, intersection and difference</li>
  <li>Be an <code>A =&gt; Int</code>, providing the count of each element</li>
  </ul>
  
  <p>Here's one approach, extending <code>Set</code>:</p>
  
  <pre><code>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 -&gt; count)) 
    }
    override def -(elem: A): MultiSet[A] = this.counts.get(elem) match {
      case None =&gt; this
      case Some(1) =&gt; new MultiSet(this.counts - elem)
      case Some(n) =&gt; new MultiSet(this.counts + (elem -&gt; (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) &lt;- this.counts.iterator; _ &lt;- 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)
  }
  </code></pre>
  
  <p>Extending <code>Set</code> is nice, because it means that <code>MultiSet</code> automatically gets definitions for union, difference, etc. All the following will hold:</p>
  
  <pre><code>// add
  assert(
    MultiSet("X" -&gt; 3, "Y" -&gt; 1) + "X" ===
      MultiSet("X" -&gt; 4, "Y" -&gt; 1))
  assert(
    MultiSet("X" -&gt; 3, "Y" -&gt; 1) + "Z" ===
      MultiSet("X" -&gt; 3, "Y" -&gt; 1, "Z" -&gt; 1))
  
  // remove
  assert(
    MultiSet("a" -&gt; 2, "b" -&gt; 5) - "b" ===
      MultiSet("a" -&gt; 2, "b" -&gt; 4))
  assert(
    MultiSet("a" -&gt; 2, "b" -&gt; 5) - "c" ===
      MultiSet("a" -&gt; 2, "b" -&gt; 5))
  
  // add all
  assert(
    MultiSet(10 -&gt; 1, 100 -&gt; 3) ++ MultiSet(10 -&gt; 1, 1 -&gt; 7) ===
      MultiSet(100 -&gt; 3, 10 -&gt; 2, 1 -&gt; 7))
  
  // remove all
  assert(
    MultiSet("a" -&gt; 2, "b" -&gt; 5) -- MultiSet("a" -&gt; 3) ===
      MultiSet("b" -&gt; 5))
  </code></pre>
  
  <p>However, I would have to override some inherited methods like <code>union</code> and <code>intersect</code> because they would do the wrong things for multisets, e.g. the following would not hold:</p>
  
  <pre><code>// union (takes max of values)
  assert(
    MultiSet(10 -&gt; 5, 1 -&gt; 1).union(MultiSet(10 -&gt; 3, 1 -&gt; 7)) ===
      MultiSet(10 -&gt; 5, 1 -&gt; 7))
  
  // intersection (takes min of values)
  assert(
    MultiSet(10 -&gt; 5, 100 -&gt; 3).intersect(MultiSet(10 -&gt; 1, 1 -&gt; 7)) ===
      MultiSet(10 -&gt; 1))
  </code></pre>
  
  <p>Another problem with extending <code>Set</code> is that then I can't have <code>MultiSet</code> be an <code>A =&gt; Int</code> because I'll get the error: <code>illegal inheritance;  class MultiSet inherits different type instances of trait Function1: A =&gt; Int and A =&gt; Boolean</code>. I could work around this by declaring a separate, say, <code>count</code> method, but I'd really prefer that the class just be an <code>A =&gt; Int</code>.</p>
  
  <p>Another approach would be to inherit from <code>Map[A, Int]</code>, which would give me the <code>A =&gt; Int</code> that I want, but then I would have to define all of my own <code>++</code>, <code>--</code>, etc. since in <code>Map</code> these would be defined over <code>(A, Int)</code> pairs, but for a multiset they need to be defined over  <code>A</code>s.</p>
  
  <p>I guess a third approach would be to give up on both <code>Set</code> and <code>Map</code>, and just implement a new subclass of <code>Iterable</code> or whatever.</p>
  
  <p>What would you recommend? What's the best way to fit a <code>MulitSet</code> within the Scala collections framework?</p>