Are Multisets missing in Scala?

Question

I was trying the Facebook Hacker Cup 2013 Qualification Problems in Scala, and for the 3rd problem I felt the need of an ordered Multiset but could not find one in scala's (2.10) collections. Is this data structure missing in scala's collections. Is it going to be implemented in a future version? Is the Multiset not really necessary if you have already a set implemented?

Answer 1

A multiset is a rather peculiar and uncommon data structure. It is not, for instance, part of Java's standard library either. Guava does have one, and so does Boost, but Boost has basically everything.

If all you want is to count the number of occurrences of the elements, you could resort to a SortedMap from element to count instead. If you require, on the other hand, for the elements to be distinct, retrievable, but equivalent under sorting rules, you could use a SortedMap from element (not important which one) to a Set of distinguished elements.

Answer 2

A multiset can be pretty useful sometimes. I often find myself coding the Map[K, List[V]] manually. There is a great implementation of multisets called a Bag by Nicolas Stucki, and is released on Maven.

Announced here:

https://groups.google.com/forum/#!topic/scala-internals/ceaEAiQPgK4

Code here:

https://github.com/nicolasstucki/multisets

Maven:

https://github.com/nicolasstucki/multisets/blob/master/MavenRepository.md

Answer 3

Seq trait has diff, intersect and even union. That should help you with a lot of your multiset problems. http://www.scala-lang.org/api/2.11.7/index.html#scala.collection.Seq@diff(that:Seq[A]):Seq[A]

Answer 4

If all you need is equality and you don't care too much about performance, you can just use sorted lists.

Answer 5

Both mutable and immutable Multisets are provided in https://github.com/scala/scala-collection-contrib