ContentsIndex
MultiSet
Portability portable
Stability provisional
Maintainer daan@cs.uu.nl
Contents
MultiSet type
Operators
Query
Construction
Combine
Filter
Fold
Min/Max
Conversion
List
Ordered list
Occurrence lists
Map
Debugging
Description
An implementation of multi sets on top of the Map module. A multi set differs from a bag in the sense that it is represented as a map from elements to occurrence counts instead of retaining all elements. This means that equality on elements should be defined as a structural equality instead of an equivalence relation. If this is not the case, operations that observe the elements, like filter and fold, should be used with care.
Synopsis
data MultiSet a
(\\) :: (Ord a) => MultiSet a -> MultiSet a -> MultiSet a
isEmpty :: MultiSet a -> Bool
size :: MultiSet a -> Int
distinctSize :: MultiSet a -> Int
member :: (Ord a) => a -> MultiSet a -> Bool
occur :: (Ord a) => a -> MultiSet a -> Int
subset :: (Ord a) => MultiSet a -> MultiSet a -> Bool
properSubset :: (Ord a) => MultiSet a -> MultiSet a -> Bool
empty :: MultiSet a
single :: a -> MultiSet a
insert :: (Ord a) => a -> MultiSet a -> MultiSet a
insertMany :: (Ord a) => a -> Int -> MultiSet a -> MultiSet a
delete :: (Ord a) => a -> MultiSet a -> MultiSet a
deleteAll :: (Ord a) => a -> MultiSet a -> MultiSet a
union :: (Ord a) => MultiSet a -> MultiSet a -> MultiSet a
difference :: (Ord a) => MultiSet a -> MultiSet a -> MultiSet a
intersection :: (Ord a) => MultiSet a -> MultiSet a -> MultiSet a
unions :: (Ord a) => [MultiSet a] -> MultiSet a
filter :: (Ord a) => (a -> Bool) -> MultiSet a -> MultiSet a
partition :: (Ord a) => (a -> Bool) -> MultiSet a -> (MultiSet a, MultiSet a)
fold :: (a -> b -> b) -> b -> MultiSet a -> b
foldOccur :: (a -> Int -> b -> b) -> b -> MultiSet a -> b
findMin :: MultiSet a -> a
findMax :: MultiSet a -> a
deleteMin :: MultiSet a -> MultiSet a
deleteMax :: MultiSet a -> MultiSet a
deleteMinAll :: MultiSet a -> MultiSet a
deleteMaxAll :: MultiSet a -> MultiSet a
elems :: MultiSet a -> [a]
toList :: MultiSet a -> [a]
fromList :: (Ord a) => [a] -> MultiSet a
toAscList :: MultiSet a -> [a]
fromAscList :: (Eq a) => [a] -> MultiSet a
fromDistinctAscList :: [a] -> MultiSet a
toOccurList :: MultiSet a -> [(a, Int)]
toAscOccurList :: MultiSet a -> [(a, Int)]
fromOccurList :: (Ord a) => [(a, Int)] -> MultiSet a
fromAscOccurList :: (Ord a) => [(a, Int)] -> MultiSet a
toMap :: MultiSet a -> Map a Int
fromMap :: (Ord a) => Map a Int -> MultiSet a
fromOccurMap :: Map a Int -> MultiSet a
showTree :: (Show a) => MultiSet a -> String
showTreeWith :: (Show a) => Bool -> Bool -> MultiSet a -> String
valid :: (Ord a) => MultiSet a -> Bool
MultiSet type
data MultiSet a
A multi set of values a.
Instances
(Eq a) => Eq (MultiSet a)
(Show a) => Show (MultiSet a)
Operators
(\\) :: (Ord a) => MultiSet a -> MultiSet a -> MultiSet a
O(n+m). See difference.
Query
isEmpty :: MultiSet a -> Bool
O(1). Is the multi set empty?
size :: MultiSet a -> Int
O(n). The number of elements in the multi set.
distinctSize :: MultiSet a -> Int
O(1). Returns the number of distinct elements in the multi set, ie. (distinctSize mset == Set.size (toSet mset)).
member :: (Ord a) => a -> MultiSet a -> Bool
O(log n). Is the element in the multi set?
occur :: (Ord a) => a -> MultiSet a -> Int
O(log n). The number of occurrences of an element in the multi set.
subset :: (Ord a) => MultiSet a -> MultiSet a -> Bool
O(n+m). Is this a subset of the multi set?
properSubset :: (Ord a) => MultiSet a -> MultiSet a -> Bool
O(n+m). Is this a proper subset? (ie. a subset and not equal)
Construction
empty :: MultiSet a
O(1). Create an empty multi set.
single :: a -> MultiSet a
O(1). Create a singleton multi set.
insert :: (Ord a) => a -> MultiSet a -> MultiSet a
O(log n). Insert an element in the multi set.
insertMany :: (Ord a) => a -> Int -> MultiSet a -> MultiSet a
O(min(n,W)). The expression (insertMany x count mset) inserts count instances of x in the multi set mset.
delete :: (Ord a) => a -> MultiSet a -> MultiSet a
O(log n). Delete a single element.
deleteAll :: (Ord a) => a -> MultiSet a -> MultiSet a
O(log n). Delete all occurrences of an element.
Combine
union :: (Ord a) => MultiSet a -> MultiSet a -> MultiSet a

O(n+m). Union of two multisets. The union adds the elements together.

 MultiSet\> union (fromList [1,1,2]) (fromList [1,2,2,3])
 {1,1,1,2,2,2,3}
difference :: (Ord a) => MultiSet a -> MultiSet a -> MultiSet a

O(n+m). Difference between two multisets.

 MultiSet\> difference (fromList [1,1,2]) (fromList [1,2,2,3])
 {1}
intersection :: (Ord a) => MultiSet a -> MultiSet a -> MultiSet a

O(n+m). Intersection of two multisets.

 MultiSet\> intersection (fromList [1,1,2]) (fromList [1,2,2,3])
 {1,2}
unions :: (Ord a) => [MultiSet a] -> MultiSet a
The union of a list of multisets.
Filter
filter :: (Ord a) => (a -> Bool) -> MultiSet a -> MultiSet a
O(n). Filter all elements that satisfy some predicate.
partition :: (Ord a) => (a -> Bool) -> MultiSet a -> (MultiSet a, MultiSet a)
O(n). Partition the multi set according to some predicate.
Fold
fold :: (a -> b -> b) -> b -> MultiSet a -> b
O(n). Fold over each element in the multi set.
foldOccur :: (a -> Int -> b -> b) -> b -> MultiSet a -> b
O(n). Fold over all occurrences of an element at once.
Min/Max
findMin :: MultiSet a -> a
O(log n). The minimal element of a multi set.
findMax :: MultiSet a -> a
O(log n). The maximal element of a multi set.
deleteMin :: MultiSet a -> MultiSet a
O(log n). Delete the minimal element.
deleteMax :: MultiSet a -> MultiSet a
O(log n). Delete the maximal element.
deleteMinAll :: MultiSet a -> MultiSet a
O(log n). Delete all occurrences of the minimal element.
deleteMaxAll :: MultiSet a -> MultiSet a
O(log n). Delete all occurrences of the maximal element.
Conversion
elems :: MultiSet a -> [a]
O(n). The list of elements.
List
toList :: MultiSet a -> [a]
O(n). Create a list with all elements.
fromList :: (Ord a) => [a] -> MultiSet a
O(n*log n). Create a multi set from a list of elements.
Ordered list
toAscList :: MultiSet a -> [a]
O(n). Create an ascending list of all elements.
fromAscList :: (Eq a) => [a] -> MultiSet a
O(n). Create a multi set from an ascending list in linear time.
fromDistinctAscList :: [a] -> MultiSet a
O(n). Create a multi set from an ascending list of distinct elements in linear time.
Occurrence lists
toOccurList :: MultiSet a -> [(a, Int)]
O(n). Create a list of element/occurrence pairs.
toAscOccurList :: MultiSet a -> [(a, Int)]
O(n). Create an ascending list of element/occurrence pairs.
fromOccurList :: (Ord a) => [(a, Int)] -> MultiSet a
O(n*log n). Create a multi set from a list of element/occurrence pairs.
fromAscOccurList :: (Ord a) => [(a, Int)] -> MultiSet a
O(n). Create a multi set from an ascending list of element/occurrence pairs.
Map
toMap :: MultiSet a -> Map a Int
O(1). Convert to a Map from elements to number of occurrences.
fromMap :: (Ord a) => Map a Int -> MultiSet a
O(n). Convert a Map from elements to occurrences into a multi set.
fromOccurMap :: Map a Int -> MultiSet a
O(1). Convert a Map from elements to occurrences into a multi set. Assumes that the Map contains only elements that occur at least once.
Debugging
showTree :: (Show a) => MultiSet a -> String
O(n). Show the tree structure that implements the MultiSet. The tree is shown as a compressed and hanging.
showTreeWith :: (Show a) => Bool -> Bool -> MultiSet a -> String
O(n). The expression (showTreeWith hang wide map) shows the tree that implements the multi set. The tree is shown hanging when hang is True and otherwise as a rotated tree. When wide is True an extra wide version is shown.
valid :: (Ord a) => MultiSet a -> Bool
O(n). Is this a valid multi set?
Produced by Haddock version 0.4