|
|
|
|
|
| Description |
|
|
| Synopsis |
|
|
|
|
| MultiSet type
|
|
| data MultiSet a |
| A multi set of values a.
|  Instances | |
|
|
| 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.8 |
