Copyright | (c) Twan van Laarhoven 2008 |
---|---|

License | BSD-style |

Maintainer | libraries@haskell.org |

Stability | provisional |

Portability | portable |

Safe Haskell | Safe |

Language | Haskell2010 |

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.

- data IntMultiSet
- type Key = Int
- type Occur = Int
- (\\) :: IntMultiSet -> IntMultiSet -> IntMultiSet
- null :: IntMultiSet -> Bool
- size :: IntMultiSet -> Int
- distinctSize :: IntMultiSet -> Int
- member :: Key -> IntMultiSet -> Bool
- notMember :: Key -> IntMultiSet -> Bool
- occur :: Key -> IntMultiSet -> Int
- isSubsetOf :: IntMultiSet -> IntMultiSet -> Bool
- isProperSubsetOf :: IntMultiSet -> IntMultiSet -> Bool
- empty :: IntMultiSet
- singleton :: Key -> IntMultiSet
- insert :: Key -> IntMultiSet -> IntMultiSet
- insertMany :: Key -> Occur -> IntMultiSet -> IntMultiSet
- delete :: Key -> IntMultiSet -> IntMultiSet
- deleteMany :: Key -> Occur -> IntMultiSet -> IntMultiSet
- deleteAll :: Key -> IntMultiSet -> IntMultiSet
- union :: IntMultiSet -> IntMultiSet -> IntMultiSet
- unions :: [IntMultiSet] -> IntMultiSet
- maxUnion :: IntMultiSet -> IntMultiSet -> IntMultiSet
- difference :: IntMultiSet -> IntMultiSet -> IntMultiSet
- intersection :: IntMultiSet -> IntMultiSet -> IntMultiSet
- filter :: (Key -> Bool) -> IntMultiSet -> IntMultiSet
- partition :: (Key -> Bool) -> IntMultiSet -> (IntMultiSet, IntMultiSet)
- split :: Int -> IntMultiSet -> (IntMultiSet, IntMultiSet)
- splitOccur :: Int -> IntMultiSet -> (IntMultiSet, Int, IntMultiSet)
- map :: (Key -> Key) -> IntMultiSet -> IntMultiSet
- mapMonotonic :: (Key -> Key) -> IntMultiSet -> IntMultiSet
- mapMaybe :: (Key -> Maybe Key) -> IntMultiSet -> IntMultiSet
- mapEither :: (Key -> Either Key Key) -> IntMultiSet -> (IntMultiSet, IntMultiSet)
- concatMap :: (Key -> [Key]) -> IntMultiSet -> IntMultiSet
- unionsMap :: (Key -> IntMultiSet) -> IntMultiSet -> IntMultiSet
- bind :: IntMultiSet -> (Key -> IntMultiSet) -> IntMultiSet
- join :: MultiSet IntMultiSet -> IntMultiSet
- fold :: (Key -> b -> b) -> b -> IntMultiSet -> b
- foldOccur :: (Key -> Occur -> b -> b) -> b -> IntMultiSet -> b
- findMin :: IntMultiSet -> Key
- findMax :: IntMultiSet -> Key
- deleteMin :: IntMultiSet -> IntMultiSet
- deleteMax :: IntMultiSet -> IntMultiSet
- deleteMinAll :: IntMultiSet -> IntMultiSet
- deleteMaxAll :: IntMultiSet -> IntMultiSet
- deleteFindMin :: IntMultiSet -> (Key, IntMultiSet)
- deleteFindMax :: IntMultiSet -> (Key, IntMultiSet)
- maxView :: IntMultiSet -> Maybe (Key, IntMultiSet)
- minView :: IntMultiSet -> Maybe (Key, IntMultiSet)
- elems :: IntMultiSet -> [Key]
- distinctElems :: IntMultiSet -> [Key]
- toList :: IntMultiSet -> [Key]
- fromList :: [Int] -> IntMultiSet
- toAscList :: IntMultiSet -> [Key]
- fromAscList :: [Int] -> IntMultiSet
- fromDistinctAscList :: [Int] -> IntMultiSet
- toOccurList :: IntMultiSet -> [(Int, Int)]
- toAscOccurList :: IntMultiSet -> [(Int, Int)]
- fromOccurList :: [(Int, Int)] -> IntMultiSet
- fromAscOccurList :: [(Int, Int)] -> IntMultiSet
- fromDistinctAscOccurList :: [(Int, Int)] -> IntMultiSet
- toMap :: IntMultiSet -> IntMap Int
- fromMap :: IntMap Int -> IntMultiSet
- fromOccurMap :: IntMap Int -> IntMultiSet
- toSet :: IntMultiSet -> IntSet
- fromSet :: IntSet -> IntMultiSet
- showTree :: IntMultiSet -> String
- showTreeWith :: Bool -> Bool -> IntMultiSet -> String

# MultiSet type

data IntMultiSet Source

A multiset of integers. The same value can occur multiple times.

# Operators

(\\) :: IntMultiSet -> IntMultiSet -> IntMultiSet infixl 9 Source

*O(n+m)*. See `difference`

.

# Query

null :: IntMultiSet -> Bool Source

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

size :: IntMultiSet -> Int Source

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

distinctSize :: IntMultiSet -> Int Source

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

member :: Key -> IntMultiSet -> Bool Source

*O(min(n,W))*. Is the element in the multiset?

notMember :: Key -> IntMultiSet -> Bool Source

*O(min(n,W))*. Is the element not in the multiset?

occur :: Key -> IntMultiSet -> Int Source

*O(min(n,W))*. The number of occurrences of an element in a multiset.

isSubsetOf :: IntMultiSet -> IntMultiSet -> Bool Source

*O(n+m)*. Is this a subset?
`(s1 `isSubsetOf` s2)`

tells whether `s1`

is a subset of `s2`

.

isProperSubsetOf :: IntMultiSet -> IntMultiSet -> Bool Source

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

# Construction

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

singleton :: Key -> IntMultiSet Source

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

insert :: Key -> IntMultiSet -> IntMultiSet Source

*O(min(n,W))*. Insert an element in a multiset.

insertMany :: Key -> Occur -> IntMultiSet -> IntMultiSet Source

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

Negative numbers remove occurrences of the given element.

delete :: Key -> IntMultiSet -> IntMultiSet Source

*O(min(n,W))*. Delete a single element from a multiset.

deleteMany :: Key -> Occur -> IntMultiSet -> IntMultiSet Source

*O(min(n,W))*. Delete an element from a multiset a given number of times.

Negative numbers add occurrences of the given element.

deleteAll :: Key -> IntMultiSet -> IntMultiSet Source

*O(min(n,W))*. Delete all occurrences of an element from a multiset.

# Combine

union :: IntMultiSet -> IntMultiSet -> IntMultiSet Source

*O(n+m)*. The union of two multisets. The union adds the occurrences together.

The implementation uses the efficient *hedge-union* algorithm.
Hedge-union is more efficient on (bigset `union`

smallset).

unions :: [IntMultiSet] -> IntMultiSet Source

maxUnion :: IntMultiSet -> IntMultiSet -> IntMultiSet Source

*O(n+m)*. The union of two multisets.
The number of occurrences of each element in the union is
the maximum of the number of occurrences in the arguments (instead of the sum).

The implementation uses the efficient *hedge-union* algorithm.
Hedge-union is more efficient on (bigset `union`

smallset).

difference :: IntMultiSet -> IntMultiSet -> IntMultiSet Source

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

intersection :: IntMultiSet -> IntMultiSet -> IntMultiSet Source

*O(n+m)*. The intersection of two multisets.

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

.

# Filter

filter :: (Key -> Bool) -> IntMultiSet -> IntMultiSet Source

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

partition :: (Key -> Bool) -> IntMultiSet -> (IntMultiSet, IntMultiSet) Source

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

.

split :: Int -> IntMultiSet -> (IntMultiSet, IntMultiSet) Source

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

.

splitOccur :: Int -> IntMultiSet -> (IntMultiSet, Int, IntMultiSet) Source

*O(log n)*. Performs a `split`

but also returns the number of
occurrences of the pivot element in the original set.

# Map

map :: (Key -> Key) -> IntMultiSet -> IntMultiSet Source

*O(n*log n)*.

is the multiset obtained by applying `map`

f s`f`

to each element of `s`

.

mapMonotonic :: (Key -> Key) -> IntMultiSet -> IntMultiSet Source

*O(n)*. The

, but works only when `mapMonotonic`

f s == `map`

f 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

mapMaybe :: (Key -> Maybe Key) -> IntMultiSet -> IntMultiSet Source

*O(n)*. Map and collect the `Just`

results.

mapEither :: (Key -> Either Key Key) -> IntMultiSet -> (IntMultiSet, IntMultiSet) Source

concatMap :: (Key -> [Key]) -> IntMultiSet -> IntMultiSet Source

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

unionsMap :: (Key -> IntMultiSet) -> IntMultiSet -> IntMultiSet Source

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

# Monadic

bind :: IntMultiSet -> (Key -> IntMultiSet) -> IntMultiSet Source

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

join :: MultiSet IntMultiSet -> IntMultiSet Source

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

# Fold

fold :: (Key -> b -> b) -> b -> IntMultiSet -> b Source

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

foldOccur :: (Key -> Occur -> b -> b) -> b -> IntMultiSet -> b Source

*O(n)*. Fold over the elements of a multiset with their occurrences.

# Min/Max

findMin :: IntMultiSet -> Key Source

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

findMax :: IntMultiSet -> Key Source

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

deleteMin :: IntMultiSet -> IntMultiSet Source

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

deleteMax :: IntMultiSet -> IntMultiSet Source

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

deleteMinAll :: IntMultiSet -> IntMultiSet Source

*O(log n)*. Delete all occurrences of the minimal element.

deleteMaxAll :: IntMultiSet -> IntMultiSet Source

*O(log n)*. Delete all occurrences of the maximal element.

deleteFindMin :: IntMultiSet -> (Key, IntMultiSet) Source

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

deleteFindMin set = (findMin set, deleteMin set)

deleteFindMax :: IntMultiSet -> (Key, IntMultiSet) Source

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

deleteFindMax set = (findMax set, deleteMax set)

maxView :: IntMultiSet -> Maybe (Key, IntMultiSet) Source

*O(log n)*. Retrieves the maximal element of the multiset, and the set stripped from that element
`fail`

s (in the monad) when passed an empty multiset.

Examples:

`>>>`

Just (300,fromOccurList [(100,2),(200,1)])`maxView $ fromList [100, 100, 200, 300]`

minView :: IntMultiSet -> Maybe (Key, IntMultiSet) Source

*O(log n)*. Retrieves the minimal element of the multiset, and the set stripped from that element
Returns `Nothing`

when passed an empty multiset.

Examples:

`>>>`

Just (100,fromOccurList [(100,1),(200,1),(300,1)])`minView $ fromList [100, 100, 200, 300]`

# Conversion

## List

elems :: IntMultiSet -> [Key] Source

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

distinctElems :: IntMultiSet -> [Key] Source

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

distinctElems = map fst . toOccurList

toList :: IntMultiSet -> [Key] Source

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

fromList :: [Int] -> IntMultiSet Source

*O(t*min(n,W))*. Create a multiset from a list of elements.

## Ordered list

toAscList :: IntMultiSet -> [Key] Source

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

fromAscList :: [Int] -> IntMultiSet Source

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

fromDistinctAscList :: [Int] -> IntMultiSet Source

*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

toOccurList :: IntMultiSet -> [(Int, Int)] Source

*O(n)*. Convert the multiset to a list of element/occurrence pairs.

toAscOccurList :: IntMultiSet -> [(Int, Int)] Source

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

fromOccurList :: [(Int, Int)] -> IntMultiSet Source

*O(n*min(n,W))*. Create a multiset from a list of element/occurrence pairs.
Occurrences must be positive.
*The precondition (all occurrences > 0) is not checked.*

fromAscOccurList :: [(Int, Int)] -> IntMultiSet Source

*O(n)*. Build a multiset from an ascending list of element/occurrence pairs in linear time.
Occurrences must be positive.
*The precondition (input list is ascending, all occurrences > 0) is not checked.*

fromDistinctAscOccurList :: [(Int, Int)] -> IntMultiSet Source

*O(n)*. Build a multiset from an ascending list of elements/occurrence pairs where each elements appears only once.
Occurrences must be positive.
*The precondition (input list is strictly ascending, all occurrences > 0) is not checked.*

## Map

toMap :: IntMultiSet -> IntMap Int Source

*O(1)*. Convert a multiset to an `IntMap`

from elements to number of occurrences.

fromMap :: IntMap Int -> IntMultiSet Source

*O(n)*. Convert an `IntMap`

from elements to occurrences to a multiset.

fromOccurMap :: IntMap Int -> IntMultiSet Source

## Set

toSet :: IntMultiSet -> IntSet Source

*O(n)*. Convert a multiset to an `IntMap`

, removing duplicates.

fromSet :: IntSet -> IntMultiSet Source

*O(n)*. Convert an `IntMap`

to a multiset.

# Debugging

showTree :: IntMultiSet -> String Source

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

showTreeWith :: Bool -> Bool -> IntMultiSet -> String Source

*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