- 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)
- 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
- toAscList :: TKey a => TSet a -> [a]
- fromAscList :: TKey a => [a] -> TSet a
- fromDistinctAscList :: TKey a => [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 s`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`

mapMonotonic :: (TKey a, TKey b) => (a -> b) -> TSet a -> TSet bSource

, but works only when `mapMonotonic`

f s == `map`

f s`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

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

# Conversion

## Map

## List

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