|
|
|
|
|
| Description |
|
|
| Synopsis |
|
|
|
|
| Set type
|
|
| data IntSet |
| A set of integers.
|  Instances | |
|
|
| Operators
|
|
| (\\) :: IntSet -> IntSet -> IntSet |
| O(n+m). See difference.
|
|
| Query
|
|
| isEmpty :: IntSet -> Bool |
| O(1). Is the set empty?
|
|
| size :: IntSet -> Int |
| O(n). Cardinality of the set.
|
|
| member :: Int -> IntSet -> Bool |
| O(min(n,W)). Is the value a member of the set?
|
|
| subset :: IntSet -> IntSet -> Bool |
| O(n+m). Is this a subset?
|
|
| properSubset :: IntSet -> IntSet -> Bool |
| O(n+m). Is this a proper subset? (ie. a subset but not equal).
|
|
| Construction
|
|
| empty :: IntSet |
| O(1). The empty set.
|
|
| single :: Int -> IntSet |
| O(1). A set of one element.
|
|
| insert :: Int -> IntSet -> IntSet |
| O(min(n,W)). Add a value to the set. When the value is already
an element of the set, it is replaced by the new one, ie. insert
is left-biased.
|
|
| delete :: Int -> IntSet -> IntSet |
| O(min(n,W)). Delete a value in the set. Returns the
original set when the value was not present.
|
|
| Combine
|
|
| union :: IntSet -> IntSet -> IntSet |
| O(n+m). The union of two sets.
|
|
| unions :: [IntSet] -> IntSet |
| The union of a list of sets.
|
|
| difference :: IntSet -> IntSet -> IntSet |
| O(n+m). Difference between two sets.
|
|
| intersection :: IntSet -> IntSet -> IntSet |
| O(n+m). The intersection of two sets.
|
|
| Filter
|
|
| filter :: (Int -> Bool) -> IntSet -> IntSet |
| O(n). Filter all elements that satisfy some predicate.
|
|
| partition :: (Int -> Bool) -> IntSet -> (IntSet, IntSet) |
| O(n). partition the set according to some predicate.
|
|
| split :: Int -> IntSet -> (IntSet, IntSet) |
| O(log n). The expression (split x set) is a pair (set1,set2)
where all elements in set1 are lower than x and all elements in
set2 larger than x.
|
|
| splitMember :: Int -> IntSet -> (Bool, IntSet, IntSet) |
| O(log n). Performs a split but also returns whether the pivot
element was found in the original set.
|
|
| Fold
|
|
| fold :: (Int -> b -> b) -> b -> IntSet -> b |
O(n). Fold over the elements of a set in an unspecified order.
sum set = fold (+) 0 set
elems set = fold (:) [] set
|
|
| Conversion
|
|
| List
|
|
| elems :: IntSet -> [Int] |
| O(n). The elements of a set.
|
|
| toList :: IntSet -> [Int] |
| O(n). Convert the set to a list of elements.
|
|
| fromList :: [Int] -> IntSet |
| O(n*min(n,W)). Create a set from a list of integers.
|
|
| Ordered list
|
|
| toAscList :: IntSet -> [Int] |
| O(n). Convert the set to an ascending list of elements.
|
|
| fromAscList :: [Int] -> IntSet |
| O(n*min(n,W)). Build a set from an ascending list of elements.
|
|
| fromDistinctAscList :: [Int] -> IntSet |
| O(n*min(n,W)). Build a set from an ascending list of distinct elements.
|
|
| Debugging
|
|
| showTree :: IntSet -> String |
| O(n). Show the tree that implements the set. The tree is shown
in a compressed, hanging format.
|
|
| showTreeWith :: Bool -> Bool -> IntSet -> String |
| 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.
|
|
| Produced by Haddock version 0.8 |
