An efficient implementation of multisets of integers, also somtimes called bags.

A multiset is like a set, but it can contain multiple copies of the same element.

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.IntMap module.

Many operations have a worst-case complexity of O(min(n,W)). This means that the operation can become linear in the number of elements with a maximum of W -- the number of bits in an Int (32 or 64). Here n refers to the number of distinct elements, t is the total number of elements.

O(min(n,W)). Insert an element in a multiset a given number of times.

Negative numbers remove occurences of the given element.

O(min(n,W)). 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