| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Synopsis | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Set type | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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 tells whether isSubsetOf s2)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.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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 () is a pair split x set(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 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

f to each element of s.
It's worth noting that the size of the result may be smaller if,
for some | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

deleteFindMin set = (findMin set, deleteMin set) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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 |