- data TSet a
- (\\) :: TKey a => TSet a -> TSet a -> TSet a
- null :: TKey a => TSet a -> Bool
- size :: TKey a => TSet a -> Int
- member :: TKey a => a -> TSet a -> Bool
- notMember :: TKey a => a -> TSet a -> Bool
- isSubsetOf :: TKey a => TSet a -> TSet a -> Bool
- isProperSubsetOf :: TKey a => TSet a -> TSet a -> Bool
- empty :: TKey a => TSet a
- singleton :: TKey a => a -> TSet a
- insert :: TKey a => a -> TSet a -> TSet a
- delete :: TKey a => a -> TSet a -> TSet a
- union :: TKey a => TSet a -> TSet a -> TSet a
- symmetricDifference :: TKey a => TSet a -> TSet a -> TSet a
- intersection :: TKey a => TSet a -> TSet a -> TSet a
- difference :: TKey a => TSet a -> TSet a -> TSet a
- filter :: TKey a => (a -> Bool) -> TSet a -> TSet a
- partition :: TKey a => (a -> Bool) -> TSet a -> (TSet a, TSet a)
- split :: TKey a => a -> TSet a -> (TSet a, TSet a)
- splitMember :: TKey a => a -> TSet a -> (TSet a, Bool, TSet a)
- map :: (TKey a, TKey b) => (a -> b) -> TSet a -> TSet b
- mapMonotonic :: (TKey a, TKey b) => (a -> b) -> TSet a -> TSet b
- foldl :: TKey b => (a -> b -> a) -> a -> TSet b -> a
- foldr :: TKey a => (a -> b -> b) -> b -> TSet a -> b
- findMin :: TKey a => TSet a -> a
- findMax :: TKey a => TSet a -> a
- deleteMin :: TKey a => TSet a -> TSet a
- deleteMax :: TKey a => TSet a -> TSet a
- deleteFindMin :: TKey a => TSet a -> (a, TSet a)
- deleteFindMax :: TKey a => TSet a -> (a, TSet a)
- minView :: TKey a => TSet a -> Maybe (a, TSet a)
- maxView :: TKey a => TSet a -> Maybe (a, TSet a)
- elemAt :: TKey a => Int -> TSet a -> a
- deleteAt :: TKey a => Int -> TSet a -> TSet a
- lookupIndex :: TKey a => a -> TSet a -> Maybe Int
- mapSet :: TKey a => (a -> b) -> TSet a -> TMap a b
- elems :: TKey a => TSet a -> [a]
- toList :: TKey a => TSet a -> [a]
- fromList :: TKey a => [a] -> TSet a
- toVector :: (TKey a, Vector v a) => TSet a -> v a
- fromVector :: (TKey a, Vector v a) => v a -> TSet a
- toAscList :: TKey a => TSet a -> [a]
- fromAscList :: TKey a => [a] -> TSet a
- fromDistinctAscList :: TKey a => [a] -> TSet a
- fromAscVector :: (TKey a, Vector v a) => v a -> TSet a
- fromDistinctAscVector :: (TKey a, Vector v a) => v a -> TSet a
Set type
A set of values a
, backed by a trie.
Operators
Query
isSubsetOf :: TKey a => TSet a -> TSet a -> BoolSource
Is this a subset? (s1
tells whether isSubsetOf
s2)s1
is a subset of s2
.
isProperSubsetOf :: TKey a => TSet a -> TSet a -> BoolSource
Is this a proper subset? (ie. a subset but not equal).
Construction
Combine
union :: TKey a => TSet a -> TSet a -> TSet aSource
The union of two TSet
s, preferring the first set when
equal elements are encountered.
symmetricDifference :: TKey a => TSet a -> TSet a -> TSet aSource
The symmetric difference of two TSet
s.
intersection :: TKey a => TSet a -> TSet a -> TSet aSource
Intersection of two TSet
s. Elements of the result come from the first set.
Filter
filter :: TKey a => (a -> Bool) -> TSet a -> TSet aSource
Filter all elements that satisfy the predicate.
partition :: TKey a => (a -> Bool) -> TSet a -> (TSet a, TSet a)Source
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 :: TKey a => a -> TSet a -> (TSet a, TSet a)Source
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
.
splitMember :: TKey a => a -> TSet a -> (TSet a, Bool, TSet a)Source
Performs a split
but also returns whether the pivot
element was found in the original set.
Map
map :: (TKey a, TKey b) => (a -> b) -> TSet a -> TSet bSource
is the set obtained by applying map
f sf
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
mapMonotonic :: (TKey a, TKey b) => (a -> b) -> TSet a -> TSet bSource
, but works only when mapMonotonic
f s == map
f sf
is strictly 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
Min/Max
deleteFindMin :: TKey a => TSet a -> (a, TSet a)Source
Delete and find the minimal element.
'deleteFindMin' set = ('findMin' set, 'deleteMin' set)
deleteFindMax :: TKey a => TSet a -> (a, TSet a)Source
Delete and find the maximal element.
'deleteFindMax' set = ('findMax' set, 'deleteMax' set)
minView :: TKey a => TSet a -> Maybe (a, TSet a)Source
Retrieves the minimal key of the set, and the set
stripped of that element, or Nothing
if passed an empty set.
maxView :: TKey a => TSet a -> Maybe (a, TSet a)Source
Retrieves the maximal key of the set, and the set
stripped of that element, or Nothing
if passed an empty set.
Index
elemAt :: TKey a => Int -> TSet a -> aSource
Returns the element at the specified index. Throws an error if an invalid index is specified.
deleteAt :: TKey a => Int -> TSet a -> TSet aSource
Deletes the element at the specified index. Throws an error if an invalid index is specified.
Conversion
Map
List
Vector
toVector :: (TKey a, Vector v a) => TSet a -> v aSource
O(n). Construct a vector from the elements of this set. Does not currently fuse.
fromVector :: (TKey a, Vector v a) => v a -> TSet aSource
Create a set from a vector of elements.
Ordered lists
fromAscList :: TKey a => [a] -> TSet aSource
Build a set from an ascending list in linear time. The precondition (input list is ascending) is not checked.
fromDistinctAscList :: TKey a => [a] -> TSet aSource
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.
Ordered vectors
fromAscVector :: (TKey a, Vector v a) => v a -> TSet aSource
Build a set from an ascending vector in linear time. The precondition (input vector is ascending) is not checked.
fromDistinctAscVector :: (TKey a, Vector v a) => v a -> TSet aSource
O(n). Build a set from an ascending vector of distinct elements in linear time. The precondition (input vector is strictly ascending) is not checked.