- data Set a
- (\\) :: Ord a => Set a -> Set a -> Set a
- isEmpty :: Set a -> Bool
- size :: Set a -> Int
- member :: Ord a => a -> Set a -> Bool
- subset :: Ord a => Set a -> Set a -> Bool
- properSubset :: Ord a => Set a -> Set a -> Bool
- empty :: Set a
- single :: a -> Set a
- insert :: Ord a => a -> Set a -> Set a
- delete :: Ord a => a -> Set a -> Set a
- union :: Ord a => Set a -> Set a -> Set a
- unions :: Ord a => [Set a] -> Set a
- difference :: Ord a => Set a -> Set a -> Set a
- intersection :: Ord a => Set a -> Set a -> Set a
- filter :: Ord a => (a -> Bool) -> Set a -> Set a
- partition :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)
- split :: Ord a => a -> Set a -> (Set a, Set a)
- splitMember :: Ord a => a -> Set a -> (Bool, Set a, Set a)
- fold :: (a -> b -> b) -> b -> Set a -> b
- findMin :: Set a -> a
- findMax :: Set a -> a
- deleteMin :: Set a -> Set a
- deleteMax :: Set a -> Set a
- deleteFindMin :: Set a -> (a, Set a)
- deleteFindMax :: Set a -> (a, Set a)
- elems :: Set a -> [a]
- toList :: Set a -> [a]
- fromList :: Ord a => [a] -> Set a
- toAscList :: Set a -> [a]
- fromAscList :: Eq a => [a] -> Set a
- fromDistinctAscList :: [a] -> Set a
- showTree :: Show a => Set a -> String
- showTreeWith :: Show a => Bool -> Bool -> Set a -> String
- valid :: Ord a => Set a -> Bool
Set type
Operators
Query
properSubset :: Ord a => Set a -> Set a -> BoolSource
O(n+m). Is this a proper subset? (ie. a subset but not equal).
Construction
Combine
union :: Ord a => Set a -> Set a -> Set aSource
O(n+m). The union of two sets. Uses the efficient hedge-union algorithm.
unions :: Ord a => [Set a] -> Set aSource
The union of a list of sets: (unions == foldl union empty
).
difference :: Ord a => Set a -> Set a -> Set aSource
O(n+m). Difference of two sets. The implementation uses an efficient hedge algorithm comparable with hedge-union.
Filter
filter :: Ord a => (a -> Bool) -> Set a -> Set aSource
O(n). Filter all elements that satisfy the predicate.
partition :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)Source
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
.
split :: Ord a => a -> Set a -> (Set a, Set a)Source
O(log n). The expression (split x set
) is a pair (set1,set2)
where all elements in set1
are lower than x
and all elements in
set2
larger than x
.
splitMember :: Ord a => a -> Set a -> (Bool, Set a, Set a)Source
O(log n). Performs a split
but also returns whether the pivot
element was found in the original set.
Fold
Min/Max
deleteFindMin :: Set a -> (a, Set a)Source
O(log n). Delete and find the minimal element.
deleteFindMax :: Set a -> (a, Set a)Source
O(log n). Delete and find the maximal element.
Conversion
List
Ordered list
fromAscList :: Eq a => [a] -> Set aSource
O(n). Build a map from an ascending list in linear time.
fromDistinctAscList :: [a] -> Set aSource
O(n). Build a set from an ascending list of distinct elements in linear time.
Debugging
showTree :: Show a => Set a -> StringSource
O(n). Show the tree that implements the set. The tree is shown in a compressed, hanging format.
showTreeWith :: Show a => Bool -> Bool -> Set a -> StringSource
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