| ||||||||

| ||||||||

| ||||||||

Description | ||||||||

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 Since many function names (but not the type name) clash with
Prelude names, this module is usually imported import Data.MultiSet (MultiSet) import qualified Data.MultiSet as MultiSet The implementation of Note that the implementation is In the complexity of functions | ||||||||

Synopsis | ||||||||

MultiSet type | ||||||||

| ||||||||

| ||||||||

| ||||||||

The number of occurences of an element | ||||||||

Operators | ||||||||

| ||||||||

O(n+m). See difference.
| ||||||||

Query | ||||||||

| ||||||||

O(1). Is this the empty multiset?
| ||||||||

| ||||||||

O(n). The number of elements in the multiset.
| ||||||||

| ||||||||

O(1). The number of distinct elements in the multiset.
| ||||||||

| ||||||||

O(log n). Is the element in the multiset?
| ||||||||

| ||||||||

O(log n). Is the element not in the multiset?
| ||||||||

| ||||||||

O(log n). The number of occurences of an element in a multiset.
| ||||||||

| ||||||||

O(n+m). Is this a subset?
(s1 `isSubsetOf` s2) tells whether s1 is a subset of s2.
| ||||||||

| ||||||||

O(n+m). Is this a proper subset? (ie. a subset but not equal).
| ||||||||

Construction | ||||||||

| ||||||||

O(1). The empty mutli set.
| ||||||||

| ||||||||

O(1). Create a singleton mutli set.
| ||||||||

| ||||||||

O(log n). Insert an element in a multiset.
| ||||||||

| ||||||||

Negative numbers remove occurences of the given element. | ||||||||

| ||||||||

O(log n). Delete a single element from a multiset.
| ||||||||

| ||||||||

Negative numbers add occurences of the given element. | ||||||||

| ||||||||

O(log n). Delete all occurences of an element from a multiset.
| ||||||||

Combine | ||||||||

| ||||||||

O(n+m). The union of two multisets, preferring the first multiset when
equal elements are encountered.
The implementation uses the efficient hedge-union algorithm.
Hedge-union is more efficient on (bigset union smallset).
| ||||||||

| ||||||||

The union of a list of multisets: ().
unions == foldl union empty | ||||||||

| ||||||||

O(n+m). Difference of two multisets.
The implementation uses an efficient hedge algorithm comparable with hedge-union.
| ||||||||

| ||||||||

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

Filter | ||||||||

| ||||||||

O(n). Filter all elements that satisfy the predicate.
| ||||||||

| ||||||||

O(n). Partition the multiset into two multisets, one with all elements that satisfy
the predicate and one with all elements that don't satisfy the predicate.
See also split.
| ||||||||

| ||||||||

O(log n). The expression () is a pair split x set(set1,set2)
where all elements in set1 are lower than x and all elements in
set2 larger than x. x is not found in neither set1 nor set2.
| ||||||||

| ||||||||

O(log n). Performs a split but also returns the number of
occurences of the pivot element in the original set.
| ||||||||

Map | ||||||||

| ||||||||

O(n*log n).
is the multiset obtained by applying map f sf to each element of s.
| ||||||||

| ||||||||

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(n). Map and collect the Just results.
| ||||||||

| ||||||||

O(n). Map and separate the Left and Right results.
| ||||||||

| ||||||||

O(n). Apply a function to each element, and take the union of the results
| ||||||||

| ||||||||

O(n). Apply a function to each element, and take the union of the results
| ||||||||

Monadic | ||||||||

| ||||||||

O(n). The monad bind operation, (>>=), for multisets.
| ||||||||

| ||||||||

O(n). The monad join operation for multisets.
| ||||||||

Fold | ||||||||

| ||||||||

O(t). Fold over the elements of a multiset in an unspecified order.
| ||||||||

| ||||||||

O(n). Fold over the elements of a multiset with their occurences.
| ||||||||

Min/Max | ||||||||

| ||||||||

O(log n). The minimal element of a multiset.
| ||||||||

| ||||||||

O(log n). The maximal element of a multiset.
| ||||||||

| ||||||||

O(log n). Delete the minimal element.
| ||||||||

| ||||||||

O(log n). Delete the maximal element.
| ||||||||

| ||||||||

O(log n). Delete all occurences of the minimal element.
| ||||||||

| ||||||||

O(log n). Delete all occurences of the maximal element.
| ||||||||

| ||||||||

deleteFindMin set = (findMin set, deleteMin set) | ||||||||

| ||||||||

deleteFindMax set = (findMax set, deleteMax set) | ||||||||

| ||||||||

O(log n). Retrieves the maximal element of the multiset,
and the set with that element removed.
fails (in the monad) when passed an empty multiset.
| ||||||||

| ||||||||

O(log n). Retrieves the minimal element of the multiset,
and the set with that element removed.
fails (in the monad) when passed an empty multiset.
| ||||||||

Conversion | ||||||||

List | ||||||||

| ||||||||

O(t). The elements of a multiset.
| ||||||||

| ||||||||

distinctElems = map fst . toOccurList | ||||||||

| ||||||||

O(t). Convert the multiset to a list of elements.
| ||||||||

| ||||||||

O(t*log t). Create a multiset from a list of elements.
| ||||||||

Ordered list | ||||||||

| ||||||||

O(t). Convert the multiset to an ascending list of elements.
| ||||||||

| ||||||||

O(t). Build a multiset from an ascending list in linear time.
The precondition (input list is ascending) is not checked.
| ||||||||

| ||||||||

O(n). Build a multiset from an ascending list of distinct elements in linear time.
The precondition (input list is strictly ascending) is not checked.
| ||||||||

Occurrence lists | ||||||||

| ||||||||

O(n). Convert the multiset to a list of element/occurence pairs.
| ||||||||

| ||||||||

O(n). Convert the multiset to an ascending list of element/occurence pairs.
| ||||||||

| ||||||||

O(n*log n). Create a multiset from a list of element/occurence pairs.
| ||||||||

| ||||||||

O(n). Build a multiset from an ascending list of element/occurence pairs in linear time.
The precondition (input list is ascending) is not checked.
| ||||||||

| ||||||||

O(n). Build a multiset from an ascending list of elements/occurence pairs where each elements appears only once.
The precondition (input list is strictly ascending) is not checked.
| ||||||||

Map | ||||||||

| ||||||||

O(1). Convert a multiset to a Map from elements to number of occurrences.
| ||||||||

| ||||||||

O(n). Convert a Map from elements to occurrences to a multiset.
| ||||||||

| ||||||||

O(1). Convert a Map from elements to occurrences to a multiset.
Assumes that the Map contains only values larger than one.
The precondition (all elements > 1) is not checked.
| ||||||||

Set | ||||||||

| ||||||||

O(n). Convert a multiset to a Set, removing duplicates.
| ||||||||

| ||||||||

O(n). Convert a Set to a multiset.
| ||||||||

Debugging | ||||||||

| ||||||||

O(n). Show the tree that implements the set. The tree is shown
in a compressed, hanging format.
| ||||||||

| ||||||||

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

| ||||||||

O(n). Test if the internal multiset structure is valid.
| ||||||||

Produced by Haddock version 2.4.2 |