UU.DData.Set

Set type

data Set a

A set of values a.

Instances

Eq a => Eq (Set a)

Show a => Show (Set a)

Operators

(\\) :: Ord a => Set a -> Set a -> Set a

O(n+m). See difference.

Query

isEmpty :: Set a -> Bool

O(1). Is this the empty set?

size :: Set a -> Int

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

member :: Ord a => a -> Set a -> Bool

O(log n). Is the element in the set?

subset :: Ord a => Set a -> Set a -> Bool

O(n+m). Is this a subset?

properSubset :: Ord a => Set a -> Set a -> Bool

O(n+m). Is this a proper subset? (ie. a subset but not equal).

Construction

empty :: Set a

O(1). The empty set.

single :: a -> Set a

O(1). Create a singleton set.

insert :: Ord a => a -> Set a -> Set a

O(log n). Insert an element in a set.

delete :: Ord a => a -> Set a -> Set a

O(log n). Delete an element from a set.

Combine

union :: Ord a => Set a -> Set a -> Set a

O(n+m). The union of two sets. Uses the efficient hedge-union algorithm.

unions :: Ord a => [Set a] -> Set a

The union of a list of sets: (unions == foldl union empty).

difference :: Ord a => Set a -> Set a -> Set a

O(n+m). Difference of two sets. The implementation uses an efficient hedge algorithm comparable with hedge-union.

intersection :: Ord a => Set a -> Set a -> Set a

O(n+m). The intersection of two sets.

Filter

filter :: Ord a => (a -> Bool) -> Set a -> Set a

O(n). Filter all elements that satisfy the predicate.

partition :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)

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)

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)

O(log n). Performs a split but also returns whether the pivot element was found in the original set.

Fold

fold :: (a -> b -> b) -> b -> Set a -> b

O(n). Fold the elements of a set.

Min/Max

findMin :: Set a -> a

O(log n). The minimal element of a set.

findMax :: Set a -> a

O(log n). The maximal element of a set.

deleteMin :: Set a -> Set a

O(log n). Delete the minimal element.

deleteMax :: Set a -> Set a

O(log n). Delete the maximal element.

deleteFindMin :: Set a -> (a, Set a)

O(log n). Delete and find the minimal element.

deleteFindMax :: Set a -> (a, Set a)

O(log n). Delete and find the maximal element.

Conversion

List

elems :: Set a -> [a]

O(n). The elements of a set.

toList :: Set a -> [a]

O(n). Convert the set to a list of elements.

fromList :: Ord a => [a] -> Set a

O(n*log n). Create a set from a list of elements.

Ordered list

toAscList :: Set a -> [a]

O(n). Convert the set to an ascending list of elements.

fromAscList :: Eq a => [a] -> Set a

O(n). Build a map from an ascending list in linear time.

fromDistinctAscList :: [a] -> Set a

O(n). Build a set from an ascending list of distinct elements in linear time.

Debugging

showTree :: Show a => Set a -> String

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 -> String

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

valid :: Ord a => Set a -> Bool

O(n). Test if the internal set structure is valid.