| containers-0.1.0.2: Assorted concrete container types | Source code | Contents | Index
Data.Set |
Portability | portable
Stability | provisional
Maintainer | libraries@haskell.org
Contents
Set type Operators Query Construction Combine Filter Map Fold Min/Max Conversion List Ordered list Debugging
Description
An efficient implementation of sets. Since many function names (but not the type name) clash with Prelude names, this module is usually imported `qualified`, e.g.
      import Data.Set (Set)
      import qualified Data.Set as Set
The implementation of `Set` is based on size balanced binary trees (or trees of bounded balance) as described by: Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/. J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973. Note that the implementation is left-biased -- the elements of a first argument are always preferred to the second, for example in `union` or `insert`. Of course, left-biasing can only be observed when equality is an equivalence relation instead of structural equality.
Synopsis
data Set a
(\\) :: Ord a => Set a -> Set a -> Set a
null :: Set a -> Bool
size :: Set a -> Int
member :: Ord a => a -> Set a -> Bool
notMember :: Ord a => a -> Set a -> Bool
isSubsetOf :: Ord a => Set a -> Set a -> Bool
isProperSubsetOf :: Ord a => Set a -> Set a -> Bool
empty :: Set a
singleton :: 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 -> (Set a, Bool, Set a)
map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b
mapMonotonic :: (a -> b) -> Set a -> Set b
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)
maxView :: Monad m => Set a -> m (a, Set a)
minView :: Monad m => Set a -> m (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
data Set a | Source
A set of values `a`.
Instances
Foldable Set
Typeable1 Set
(Data a, Ord a) => Data (Set a)
Eq a => Eq (Set a)
Ord a => Monoid (Set a)
Ord a => Ord (Set a)
(Read a, Ord a) => Read (Set a)
Show a => Show (Set a)
Operators
(\\) :: Ord a => Set a -> Set a -> Set a | Source
O(n+m). See `difference`.
Query
null :: Set a -> Bool | Source
O(1). Is this the empty set?
size :: Set a -> Int | Source
O(1). The number of elements in the set.
member :: Ord a => a -> Set a -> Bool | Source
O(log n). Is the element in the set?
notMember :: Ord a => a -> Set a -> Bool | Source
O(log n). Is the element not in the set?
isSubsetOf :: Ord a => Set a -> Set a -> Bool | Source
O(n+m). Is this a subset? `(s1 `isSubsetOf` s2)` tells whether `s1` is a subset of `s2`.
isProperSubsetOf :: Ord a => Set a -> Set a -> Bool | Source
O(n+m). Is this a proper subset? (ie. a subset but not equal).
Construction
empty :: Set a | Source
O(1). The empty set.
singleton :: a -> Set a | Source
O(1). Create a singleton set.
insert :: Ord a => a -> Set a -> Set a | Source
O(log n). Insert an element in a set. If the set already contains an element equal to the given value, it is replaced with the new value.
delete :: Ord a => a -> Set a -> Set a | Source
O(log n). Delete an element from a set.
Combine
union :: Ord a => Set a -> Set a -> Set a | Source
O(n+m). The union of two sets, preferring the first set when equal elements are encountered. The implementation uses the efficient hedge-union algorithm. Hedge-union is more efficient on (bigset `union` smallset).
unions :: Ord a => [Set a] -> Set a | Source
The union of a list of sets: (``unions` == `foldl` `union` `empty``).
difference :: Ord a => Set a -> Set a -> Set a | Source
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 | Source
O(n+m). The intersection of two sets. Elements of the result come from the first set, so for example
     import qualified Data.Set as S
     data AB = A | B deriving Show
     instance Ord AB where compare _ _ = EQ
     instance Eq AB where _ == _ = True
     main = print (S.singleton A `S.intersection` S.singleton B,
                   S.singleton B `S.intersection` S.singleton A)
prints `(fromList [A],fromList [B])`.
Filter
filter :: Ord a => (a -> Bool) -> Set a -> Set a | Source
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`. `x` is not found in neither `set1` nor `set2`.
splitMember :: Ord a => a -> Set a -> (Set a, Bool, Set a) | Source
O(log n). Performs a `split` but also returns whether the pivot element was found in the original set.
Map
map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b | Source
O(n*log n). ``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 :: (a -> b) -> Set a -> Set b | Source
O(n). The ``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
fold :: (a -> b -> b) -> b -> Set a -> b | Source
O(n). Fold over the elements of a set in an unspecified order.
Min/Max
findMin :: Set a -> a | Source
O(log n). The minimal element of a set.
findMax :: Set a -> a | Source
O(log n). The maximal element of a set.
deleteMin :: Set a -> Set a | Source
O(log n). Delete the minimal element.
deleteMax :: Set a -> Set a | Source
O(log n). Delete the maximal element.
deleteFindMin :: Set a -> (a, Set a) | Source
O(log n). Delete and find the minimal element.
     deleteFindMin set = (findMin set, deleteMin set)
deleteFindMax :: Set a -> (a, Set a) | Source
O(log n). Delete and find the maximal element.
     deleteFindMax set = (findMax set, deleteMax set)
maxView :: Monad m => Set a -> m (a, Set a) | Source
O(log n). Retrieves the maximal key of the set, and the set stripped from that element `fail`s (in the monad) when passed an empty set.
minView :: Monad m => Set a -> m (a, Set a) | Source
O(log n). Retrieves the minimal key of the set, and the set stripped from that element `fail`s (in the monad) when passed an empty set.
Conversion
List
elems :: Set a -> [a] | Source
O(n). The elements of a set.
toList :: Set a -> [a] | Source
O(n). Convert the set to a list of elements.
fromList :: Ord a => [a] -> Set a | Source
O(n*log n). Create a set from a list of elements.
Ordered list
toAscList :: Set a -> [a] | Source
O(n). Convert the set to an ascending list of elements.
fromAscList :: Eq a => [a] -> Set a | Source
O(n). Build a set from an ascending list in linear time. The precondition (input list is ascending) is not checked.
fromDistinctAscList :: [a] -> Set a | Source
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.
Debugging
showTree :: Show a => Set a -> String | Source
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 | Source
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 | Source
O(n). Test if the internal set structure is valid.
Produced by Haddock version 0.9