Portability | portable |
---|---|
Stability | provisional |
Maintainer | libraries@haskell.org |
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 :: Monad m => IntMultiSet -> m (Key, IntMultiSet)
- minView :: Monad m => IntMultiSet -> m (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 -> IntMultiSetSource
O(n+m). See difference
.
Query
null :: IntMultiSet -> BoolSource
O(1). Is this the empty multiset?
size :: IntMultiSet -> IntSource
O(n). The number of elements in the multiset.
distinctSize :: IntMultiSet -> IntSource
O(1). The number of distinct elements in the multiset.
member :: Key -> IntMultiSet -> BoolSource
O(min(n,W)). Is the element in the multiset?
notMember :: Key -> IntMultiSet -> BoolSource
O(min(n,W)). Is the element not in the multiset?
occur :: Key -> IntMultiSet -> IntSource
O(min(n,W)). The number of occurences of an element in a multiset.
isSubsetOf :: IntMultiSet -> IntMultiSet -> BoolSource
O(n+m). Is this a subset?
(s1 `isSubsetOf` s2)
tells whether s1
is a subset of s2
.
isProperSubsetOf :: IntMultiSet -> IntMultiSet -> BoolSource
O(n+m). Is this a proper subset? (ie. a subset but not equal).
Construction
O(1). The empty mutli set.
singleton :: Key -> IntMultiSetSource
O(1). Create a singleton mutli set.
insert :: Key -> IntMultiSet -> IntMultiSetSource
O(min(n,W)). Insert an element in a multiset.
insertMany :: Key -> Occur -> IntMultiSet -> IntMultiSetSource
O(min(n,W)). Insert an element in a multiset a given number of times.
Negative numbers remove occurences of the given element.
delete :: Key -> IntMultiSet -> IntMultiSetSource
O(min(n,W)). Delete a single element from a multiset.
deleteMany :: Key -> Occur -> IntMultiSet -> IntMultiSetSource
O(min(n,W)). Delete an element from a multiset a given number of times.
Negative numbers add occurences of the given element.
deleteAll :: Key -> IntMultiSet -> IntMultiSetSource
O(min(n,W)). Delete all occurences of an element from a multiset.
Combine
union :: IntMultiSet -> IntMultiSet -> IntMultiSetSource
O(n+m). The union of two multisets. The union adds the occurences together.
The implementation uses the efficient hedge-union algorithm.
Hedge-union is more efficient on (bigset union
smallset).
unions :: [IntMultiSet] -> IntMultiSetSource
maxUnion :: IntMultiSet -> IntMultiSet -> IntMultiSetSource
O(n+m). The union of two multisets. The number of occurences of each element in the union is the maximum of the number of occurences 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 -> IntMultiSetSource
O(n+m). Difference of two multisets. The implementation uses an efficient hedge algorithm comparable with hedge-union.
intersection :: IntMultiSet -> IntMultiSet -> IntMultiSetSource
O(n+m). The intersection of two multisets.
prints (fromList [A],fromList [B])
.
Filter
filter :: (Key -> Bool) -> IntMultiSet -> IntMultiSetSource
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
occurences of the pivot element in the original set.
Map
map :: (Key -> Key) -> IntMultiSet -> IntMultiSetSource
O(n*log n).
is the multiset obtained by applying map
f sf
to each element of s
.
mapMonotonic :: (Key -> Key) -> IntMultiSet -> IntMultiSetSource
O(n). The
, but works only when mapMonotonic
f s == map
f sf
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 -> IntMultiSetSource
O(n). Map and collect the Just
results.
mapEither :: (Key -> Either Key Key) -> IntMultiSet -> (IntMultiSet, IntMultiSet)Source
concatMap :: (Key -> [Key]) -> IntMultiSet -> IntMultiSetSource
O(n). Apply a function to each element, and take the union of the results
unionsMap :: (Key -> IntMultiSet) -> IntMultiSet -> IntMultiSetSource
O(n). Apply a function to each element, and take the union of the results
Monadic
bind :: IntMultiSet -> (Key -> IntMultiSet) -> IntMultiSetSource
O(n). The monad bind operation, (>>=), for multisets.
join :: MultiSet IntMultiSet -> IntMultiSetSource
O(n). The monad join operation for multisets.
Fold
fold :: (Key -> b -> b) -> b -> IntMultiSet -> bSource
O(t). Fold over the elements of a multiset in an unspecified order.
foldOccur :: (Key -> Occur -> b -> b) -> b -> IntMultiSet -> bSource
O(n). Fold over the elements of a multiset with their occurences.
Min/Max
findMin :: IntMultiSet -> KeySource
O(log n). The minimal element of a multiset.
findMax :: IntMultiSet -> KeySource
O(log n). The maximal element of a multiset.
deleteMin :: IntMultiSet -> IntMultiSetSource
O(log n). Delete the minimal element.
deleteMax :: IntMultiSet -> IntMultiSetSource
O(log n). Delete the maximal element.
deleteMinAll :: IntMultiSet -> IntMultiSetSource
O(log n). Delete all occurences of the minimal element.
deleteMaxAll :: IntMultiSet -> IntMultiSetSource
O(log n). Delete all occurences 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 :: Monad m => IntMultiSet -> m (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.
minView :: Monad m => IntMultiSet -> m (Key, IntMultiSet)Source
O(log n). Retrieves the minimal element of the multiset, and the set stripped from that element
fail
s (in the monad) when passed an empty multiset.
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] -> IntMultiSetSource
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] -> IntMultiSetSource
O(t). Build a multiset from an ascending list in linear time. The precondition (input list is ascending) is not checked.
fromDistinctAscList :: [Int] -> IntMultiSetSource
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/occurence pairs.
toAscOccurList :: IntMultiSet -> [(Int, Int)]Source
O(n). Convert the multiset to an ascending list of element/occurence pairs.
fromOccurList :: [(Int, Int)] -> IntMultiSetSource
O(n*min(n,W)). Create a multiset from a list of element/occurence pairs.
fromAscOccurList :: [(Int, Int)] -> IntMultiSetSource
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.
fromDistinctAscOccurList :: [(Int, Int)] -> IntMultiSetSource
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
toMap :: IntMultiSet -> IntMap IntSource
O(1). Convert a multiset to an IntMap
from elements to number of occurrences.
fromMap :: IntMap Int -> IntMultiSetSource
O(n). Convert an IntMap
from elements to occurrences to a multiset.
Set
toSet :: IntMultiSet -> IntSetSource
O(n). Convert a multiset to an IntMap
, removing duplicates.
fromSet :: IntSet -> IntMultiSetSource
O(n). Convert an IntMap
to a multiset.
Debugging
showTree :: IntMultiSet -> StringSource
O(n). Show the tree that implements the set. The tree is shown in a compressed, hanging format.
showTreeWith :: Bool -> Bool -> IntMultiSet -> StringSource
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