- 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