| 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