Data.TrieSet

Set type

data TSet a

A set of values a, backed by a trie.

Instances

TKey a => Eq (TSet a)

(TKey a, Ord a) => Ord (TSet a)

(TKey a, Show a) => Show (TSet a)

TKey a => Monoid (TSet a)

Operators

(\\) :: TKey a => TSet a -> TSet a -> TSet a

See difference.

Query

null :: TKey a => TSet a -> Bool

O(1). Is this the empty set?

size :: TKey a => TSet a -> Int

O(1). The number of elements in the set.

member :: TKey a => a -> TSet a -> Bool

Is the element in the set?

notMember :: TKey a => a -> TSet a -> Bool

Is the element not in the set?

isSubsetOf :: TKey a => TSet a -> TSet a -> Bool

Is this a subset? (s1 isSubsetOf s2) tells whether s1 is a subset of s2.

isProperSubsetOf :: TKey a => TSet a -> TSet a -> Bool

Is this a proper subset? (ie. a subset but not equal).

Construction

empty :: TKey a => TSet a

The empty TSet.

singleton :: TKey a => a -> TSet a

O(1). Create a singleton set.

insert :: TKey a => a -> TSet a -> TSet a

Insert an element into the TSet.

delete :: TKey a => a -> TSet a -> TSet a

Delete an element from the TSet.

Combine

union :: TKey a => TSet a -> TSet a -> TSet a

The union of two TSets, preferring the first set when equal elements are encountered.

symmetricDifference :: TKey a => TSet a -> TSet a -> TSet a

The symmetric difference of two TSets.

intersection :: TKey a => TSet a -> TSet a -> TSet a

Intersection of two TSets. Elements of the result come from the first set.

difference :: TKey a => TSet a -> TSet a -> TSet a

Difference of two TSets.

Filter

filter :: TKey a => (a -> Bool) -> TSet a -> TSet a

Filter all elements that satisfy the predicate.

partition :: TKey a => (a -> Bool) -> TSet a -> (TSet a, TSet a)

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)

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.

splitMember :: TKey a => a -> TSet a -> (TSet a, Bool, TSet a)

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 b

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

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

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

foldl :: TKey b => (a -> b -> a) -> a -> TSet b -> a

Pre-order fold.

foldr :: TKey a => (a -> b -> b) -> b -> TSet a -> b

Post-order fold.

Min/Max

findMin :: TKey a => TSet a -> a

The minimal element of the set.

findMax :: TKey a => TSet a -> a

The maximal element of the set.

deleteMin :: TKey a => TSet a -> TSet a

Delete the minimal element.

deleteMax :: TKey a => TSet a -> TSet a

Delete the maximal element.

deleteFindMin :: TKey a => TSet a -> (a, TSet a)

Delete and find the minimal element.

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

deleteFindMax :: TKey a => TSet a -> (a, TSet a)

Delete and find the maximal element.

 'deleteFindMax' set = ('findMax' set, 'deleteMax' set)

minView :: TKey a => TSet a -> Maybe (a, TSet a)

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)

Retrieves the maximal key of the set, and the set stripped of that element, or Nothing if passed an empty set.

Conversion

Map

mapSet :: TKey a => (a -> b) -> TSet a -> TMap a b

Generate a TMap by mapping on the elements of a TSet.

List

elems :: TKey a => TSet a -> [a]

See toAscList.

toList :: TKey a => TSet a -> [a]

See toAscList.

fromList :: TKey a => [a] -> TSet a

Create a set from a list of elements.

Ordered lists

toAscList :: TKey a => TSet a -> [a]

Convert the set to an ascending list of elements.

fromAscList :: TKey a => [a] -> TSet a

Build a set from an ascending list in linear time. The precondition (input list is ascending) is not checked.

fromDistinctAscList :: TKey a => [a] -> TSet a

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.