An efficient implementation of multisets, also somtimes called bags.

A multiset is like a set, but it can contain multiple copies of the same element. Unless otherwise specified all insert and remove opertions affect only a single copy of an element. For example the minimal element before and after deleteMin could be the same, only with one less occurence.

Since many function names (but not the type name) clash with Prelude names, this module is usually imported qualified, e.g.

  import Data.MultiSet (MultiSet)
  import qualified Data.MultiSet as MultiSet

The implementation of MultiSet is based on the Data.Map module.

Note that the implementation is left-biased -- the elements of a first argument are always preferred to the second, for example in union or insert. Of course, left-biasing can only be observed when equality is an equivalence relation instead of structural equality.

In the complexity of functions n refers to the number of distinct elements, t is the total number of elements.

O(log n). Insert an element in a multiset a given number of times.

Negative numbers remove occurences of the given element.

O(log n). Delete an element from a multiset a given number of times.

Negative numbers add occurences of the given element.

O(n+m). The intersection of two multisets. Elements of the result come from the first multiset, so for example

 import qualified Data.MultiSet as MS
 data AB = A | B deriving Show
 instance Ord AB where compare _ _ = EQ
 instance Eq AB where _ == _ = True
 main = print (MS.singleton A `MS.intersection` MS.singleton B,
               MS.singleton B `MS.intersection` MS.singleton A)

prints (fromList [A],fromList [B]).

O(n). The

mapMonotonic f s == map f s, but works only when f is strictly monotonic. The precondition is not checked. Semi-formally, we have:

 and [x < y ==> f x < f y | x <- ls, y <- ls]
                     ==> mapMonotonic f s == map f s
     where ls = toList s

O(log n). Delete and find the minimal element.

 deleteFindMin set = (findMin set, deleteMin set)

O(log n). Delete and find the maximal element.

 deleteFindMax set = (findMax set, deleteMax set)

O(n). The distinct elements of a multiset, each element occurs only once in the list.

 distinctElems = map fst . toOccurList

O(n). The expression (showTreeWith hang wide map) shows the tree that implements the set. If hang is True, a hanging tree is shown otherwise a rotated tree is shown. If wide is True, an extra wide version is shown.

 Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1,1,2,3,4,5]
 (1*) 4
 +--(1*) 2
 |  +--(2*) 1
 |  +--(1*) 3
 +--(1*) 5
 
 Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1,1,2,3,4,5]
 (1*) 4
 |
 +--(1*) 2
 |  |
 |  +--(2*) 1
 |  |
 |  +--(1*) 3
 |
 +--(1*) 5
 
 Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1,1,2,3,4,5]
 +--(1*) 5
 |
 (1*) 4
 |
 |  +--(1*) 3
 |  |
 +--(1*) 2
    |
    +--(2*) 1