Portability | portable |
---|---|

Stability | provisional |

Maintainer | libraries@haskell.org |

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.

- 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

A set of values `a`

.

# Operators

# Query

isSubsetOf :: Ord a => Set a -> Set a -> BoolSource

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

tells whether `isSubsetOf`

s2)`s1`

is a subset of `s2`

.

isProperSubsetOf :: Ord a => Set a -> Set a -> BoolSource

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

# Construction

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

*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.

# Combine

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

*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).

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*.

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

*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 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 (

) is a pair `split`

x set`(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 bSource

*O(n*log n)*.

is the set obtained by applying `map`

f s`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 bSource

*O(n)*. The

, but works only when `mapMonotonic`

f s == `map`

f s`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 -> bSource

*O(n)*. Fold over the elements of a set in an unspecified order.

# Min/Max

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

## Ordered list

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

*O(n)*. Build a set from an ascending list in linear time.
*The precondition (input list is ascending) is not checked.*

fromDistinctAscList :: [a] -> Set aSource

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