| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Description | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
An efficient implementation of sets. 1) The filter function clashes with the Prelude. If you want to use Set unqualified, this function should be hidden. import Prelude hiding (filter) import Set Another solution is to use qualified names. This is also the only way how a Map, Set, and MultiSet can be used within one module. import qualified Set ... Set.single "Paris" Or, if you prefer a terse coding style: import qualified Set as S ... S.single "Berlin" 2) The implementation of Set is based on size balanced binary trees (or trees of bounded balance) as described by:
3) Note that the implementation left-biased -- the elements of a first argument are always perferred to the second, for example in union or insert. Off course, left-biasing can only be observed when equality an equivalence relation instead of structural equality. 4) Another implementation of sets based on size balanced trees exists as Data.Set in the Ghc libraries. The good part about this library is that it is highly tuned and thorougly tested. However, it is also fairly old, it is implemented indirectly on top of Data.FiniteMap and only supports the basic set operations. The Set module overcomes some of these issues:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Synopsis | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Set type | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
data 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
disjoint :: Ord a => Set a -> Set a -> Bool | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
O(n+m). Are two sets disjoint? | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
all :: Ord a => (a -> Bool) -> Set a -> Bool | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
O(n). Do all elements satisfy the predicate? | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
any :: Ord a => (a -> Bool) -> Set a -> Bool | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
O(n). Does some element satisfy the predicate? | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Fold | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
fold :: (a -> b -> b) -> b -> Set a -> b | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
O(n). Fold the elements of a set. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
image :: Ord b => (a -> b) -> Set a -> Set b | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
n. Image of a set under a function | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Maybe | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
maybeToSet :: Maybe a -> Set a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Convert Maybe a to Set a; Nothing becomes the empty set | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
maybeSetToSet :: Maybe (Set a) -> Set a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Convert Maybe (Set a) to Set a; Nothing becomes the empty set | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Produced by Haddock version 0.6 |