|
|
|
|
|
| Description |
|
|
| Synopsis |
|
|
|
|
| Set type
|
|
| data Set a |
| A set of values a.
|  Instances | | Eq a => Eq (Set a) | | Show a => Show (Set a) |
|
|
|
| Operators
|
|
| (\\) :: Ord a => Set a -> Set a -> Set a |
| O(n+m). See difference.
|
|
| Query
|
|
| isEmpty :: Set a -> Bool |
| O(1). Is this the empty set?
|
|
| size :: Set a -> Int |
| O(1). The number of elements in the set.
|
|
| member :: Ord a => a -> Set a -> Bool |
| O(log n). Is the element in the set?
|
|
| subset :: Ord a => Set a -> Set a -> Bool |
| O(n+m). Is this a subset?
|
|
| properSubset :: Ord a => Set a -> Set a -> Bool |
| O(n+m). Is this a proper subset? (ie. a subset but not equal).
|
|
| Construction
|
|
| empty :: Set a |
| O(1). The empty set.
|
|
| single :: a -> Set a |
| O(1). Create a singleton set.
|
|
| insert :: Ord a => a -> Set a -> Set a |
| O(log n). Insert an element in a set.
|
|
| delete :: Ord a => a -> Set a -> Set a |
| O(log n). Delete an element from a set.
|
|
| Combine
|
|
| union :: Ord a => Set a -> Set a -> Set a |
| O(n+m). The union of two sets. Uses the efficient hedge-union algorithm.
|
|
| unions :: Ord a => [Set a] -> Set a |
| The union of a list of sets: (unions == foldl union empty).
|
|
| difference :: Ord a => Set a -> Set a -> Set a |
| O(n+m). Difference of two sets.
The implementation uses an efficient hedge algorithm comparable with hedge-union.
|
|
| intersection :: Ord a => Set a -> Set a -> Set a |
| O(n+m). The intersection of two sets.
|
|
| Filter
|
|
| filter :: Ord a => (a -> Bool) -> Set a -> Set a |
| O(n). Filter all elements that satisfy the predicate.
|
|
| partition :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a) |
| O(n). Partition the set into two sets, one with all elements that satisfy
the predicate and one with all elements that don't satisfy the predicate.
See also split.
|
|
| split :: Ord a => a -> Set a -> (Set a, Set a) |
| 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 :: Ord a => a -> Set a -> (Bool, Set a, Set a) |
| O(log n). Performs a split but also returns whether the pivot
element was found in the original set.
|
|
| Fold
|
|
| fold :: (a -> b -> b) -> b -> Set a -> b |
| O(n). Fold the elements of a set.
|
|
| Min/Max
|
|
| findMin :: Set a -> a |
| O(log n). The minimal element of a set.
|
|
| findMax :: Set a -> a |
| O(log n). The maximal element of a set.
|
|
| deleteMin :: Set a -> Set a |
| O(log n). Delete the minimal element.
|
|
| deleteMax :: Set a -> Set a |
| O(log n). Delete the maximal element.
|
|
| deleteFindMin :: Set a -> (a, Set a) |
| O(log n). Delete and find the minimal element.
|
|
| deleteFindMax :: Set a -> (a, Set a) |
| O(log n). Delete and find the maximal element.
|
|
| Conversion
|
|
| List
|
|
| elems :: Set a -> [a] |
| O(n). The elements of a set.
|
|
| toList :: Set a -> [a] |
| O(n). Convert the set to a list of elements.
|
|
| fromList :: Ord a => [a] -> Set a |
| O(n*log n). Create a set from a list of elements.
|
|
| Ordered list
|
|
| toAscList :: Set a -> [a] |
| O(n). Convert the set to an ascending list of elements.
|
|
| fromAscList :: Eq a => [a] -> Set a |
| O(n). Build a map from an ascending list in linear time.
|
|
| fromDistinctAscList :: [a] -> Set a |
| O(n). Build a set from an ascending list of distinct elements in linear time.
|
|
| Debugging
|
|
| showTree :: Show a => Set a -> String |
| O(n). Show the tree that implements the set. The tree is shown
in a compressed, hanging format.
|
|
| showTreeWith :: Show a => Bool -> Bool -> Set a -> 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.
Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1..5]
4
+--2
| +--1
| +--3
+--5
Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1..5]
4
|
+--2
| |
| +--1
| |
| +--3
|
+--5
Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1..5]
+--5
|
4
|
| +--3
| |
+--2
|
+--1
|
|
| valid :: Ord a => Set a -> Bool |
| O(n). Test if the internal set structure is valid.
|
|
| Produced by Haddock version 0.8 |
