|
|
|
|
|
|
| Synopsis |
|
| class US a where | | | | newtype Boxed a = Boxed a | | | (\\) :: (US a, Ord a) => USet a -> USet a -> USet a | | | member :: (US a, Ord a) => a -> USet a -> Bool | | | notMember :: (US a, Ord a) => a -> USet a -> Bool | | | isSubsetOf :: (US a, Ord a) => USet a -> USet a -> Bool | | | isProperSubsetOf :: (US a, Ord a) => USet a -> USet a -> Bool | | | empty :: US a => USet a | | | singleton :: US a => a -> USet a | | | insert :: (US a, Ord a) => a -> USet a -> USet a | | | delete :: (US a, Ord a) => a -> USet a -> USet a | | | union :: (US a, Ord a) => USet a -> USet a -> USet a | | | unions :: (US a, Ord a) => [USet a] -> USet a | | | difference :: (US a, Ord a) => USet a -> USet a -> USet a | | | intersection :: (US a, Ord a) => USet a -> USet a -> USet a | | | filter :: (US a, Ord a) => (a -> Bool) -> USet a -> USet a | | | partition :: (US a, Ord a) => (a -> Bool) -> USet a -> (USet a, USet a) | | | split :: (US a, Ord a) => a -> USet a -> (USet a, USet a) | | | splitMember :: (US a, Ord a) => a -> USet a -> (USet a, Bool, USet a) | | | map :: (US a, US b, Ord a, Ord b) => (a -> b) -> USet a -> USet b | | | mapMonotonic :: (US a, US b) => (a -> b) -> USet a -> USet b | | | fold :: US a => (a -> b -> b) -> b -> USet a -> b | | | findMin :: US a => USet a -> a | | | findMax :: US a => USet a -> a | | | deleteMin :: US a => USet a -> USet a | | | deleteMax :: US a => USet a -> USet a | | | deleteFindMin :: US a => USet a -> (a, USet a) | | | deleteFindMax :: US a => USet a -> (a, USet a) | | | maxView :: US a => USet a -> Maybe (a, USet a) | | | minView :: US a => USet a -> Maybe (a, USet a) | | | elems :: US a => USet a -> [a] | | | toList :: US a => USet a -> [a] | | | fromList :: (US a, Ord a) => [a] -> USet a | | | toAscList :: US a => USet a -> [a] | | | fromAscList :: (US a, Eq a) => [a] -> USet a | | | fromDistinctAscList :: US a => [a] -> USet a | | | showTree :: (US a, Show a) => USet a -> String | | | showTreeWith :: (US a, Show a) => Bool -> Bool -> USet a -> String | | | valid :: (US a, Ord a) => USet a -> Bool |
|
|
|
| Set type
|
|
|
| | Associated Types | | | | Methods | | | O(1). The number of elements in the set.
| | | | O(1). Is this the empty set?
|
| |  Instances | |
|
|
|
| Constructors | | | Instances | |
|
|
| Operators
|
|
|
| O(n+m). See difference.
|
|
| Query
|
|
|
| O(log n). Is the element in the set?
|
|
|
| O(log n). Is the element not in the set?
|
|
|
| O(n+m). Is this a subset?
(s1 isSubsetOf s2) tells whether s1 is a subset of s2.
|
|
|
| O(n+m). Is this a proper subset? (ie. a subset but not equal).
|
|
| Construction
|
|
|
| O(1). The empty set.
|
|
|
| O(1). Create a singleton set.
|
|
|
| O(log n). Insert an element in a set.
If the set already contains an element equal to the given value,
it is replaced with the new value.
|
|
|
| O(log n). Delete an element from a set.
|
|
| Combine
|
|
|
| O(n+m). The union of two sets, preferring the first set when
equal elements are encountered.
The implementation uses the efficient hedge-union algorithm.
Hedge-union is more efficient on (bigset union smallset).
|
|
|
| The union of a list of sets: (unions == foldl union empty).
|
|
|
| O(n+m). Difference of two sets.
The implementation uses an efficient hedge algorithm comparable with hedge-union.
|
|
|
O(n+m). The intersection of two sets.
Elements of the result come from the first set, so for example
import qualified Data.Set as S
data AB = A | B deriving Show
instance Ord AB where compare _ _ = EQ
instance Eq AB where _ == _ = True
main = print (S.singleton A `S.intersection` S.singleton B,
S.singleton B `S.intersection` S.singleton A)
prints (fromList [A],fromList [B]).
|
|
| Filter
|
|
|
| O(n). Filter all elements that satisfy the predicate.
|
|
|
| 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.
|
|
|
| O(log n). The expression (split x set) is a pair (set1,set2)
where set1 comprises the elements of set less than x and set2
comprises the elements of set greater than x.
|
|
|
| O(log n). Performs a split but also returns whether the pivot
element was found in the original set.
|
|
| Map
|
|
|
O(n*log n).
map f s is the set obtained by applying f to each element of s.
It's worth noting that the size of the result may be smaller if,
for some (x,y), x /= y && f x == f y
|
|
|
O(n). The
mapMonotonic f s == map f s, but works only when f is 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
|
|
| Fold
|
|
|
| O(n). Fold over the elements of a set in an unspecified order.
|
|
| Min/Max
|
|
|
| O(log n). The minimal element of a set.
|
|
|
| O(log n). The maximal element of a set.
|
|
|
| O(log n). Delete the minimal element.
|
|
|
| O(log n). Delete the maximal element.
|
|
|
O(log n). Delete and find the minimal element.
deleteFindMin set = (findMin set, deleteMin set)
|
|
|
O(log n). Delete and find the maximal element.
deleteFindMax set = (findMax set, deleteMax set)
|
|
|
| O(log n). Retrieves the maximal key of the set, and the set
stripped of that element, or Nothing if passed an empty set.
|
|
|
| O(log n). Retrieves the minimal key of the set, and the set
stripped of that element, or Nothing if passed an empty set.
|
|
| Conversion
|
|
| List
|
|
|
| O(n). The elements of a set.
|
|
|
| O(n). Convert the set to a list of elements.
|
|
|
| O(n*log n). Create a set from a list of elements.
|
|
| Ordered list
|
|
|
| O(n). Convert the set to an ascending list of elements.
|
|
|
| O(n). Build a set from an ascending list in linear time.
The precondition (input list is ascending) is not checked.
|
|
|
| O(n). Build a set from an ascending list of distinct elements in linear time.
The precondition (input list is strictly ascending) is not checked.
|
|
| Debugging
|
|
|
| O(n). Show the tree that implements the set. The tree is shown
in a compressed, hanging format.
|
|
|
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
|
|
|
| O(n). Test if the internal set structure is valid.
|
|
| Produced by Haddock version 2.4.2 |
