Derived from Data.Set by Daan Leijen License : BSD Maintainer : David F. Place Stability : Experimental Portability : ?

An efficient implementation of sets over small enumerations.

This module is intended to be imported `qualified`

, to avoid name
clashes with Prelude functions. eg.

import Data.Set.Enum as Set

The implementation of `EnumSet`

is based on bit-wise operations.

- data Set a
- (\\) :: Set a -> Set a -> Set a
- null :: Set a -> Bool
- size :: Enum a => Set a -> Int
- member :: Enum a => a -> Set a -> Bool
- isSubsetOf :: Set a -> Set a -> Bool
- isProperSubsetOf :: Set a -> Set a -> Bool
- empty :: Set a
- singleton :: Enum a => a -> Set a
- insert :: Enum a => a -> Set a -> Set a
- delete :: Enum a => a -> Set a -> Set a
- union :: Set a -> Set a -> Set a
- unions :: [Set a] -> Set a
- difference :: Set a -> Set a -> Set a
- intersection :: Set a -> Set a -> Set a
- complement :: (Bounded a, Enum a) => Set a -> Set a
- complementWith :: Set a -> Set a -> Set a
- filter :: Enum a => (a -> Bool) -> Set a -> Set a
- partition :: Enum a => (a -> Bool) -> Set a -> (Set a, Set a)
- split :: (Ord a, Enum a) => a -> Set a -> (Set a, Set a)
- splitMember :: (Ord a, Enum a) => a -> Set a -> (Set a, Bool, Set a)
- map :: (Enum a, Enum b) => (a -> b) -> Set a -> Set b
- mapMonotonic :: (Enum a, Enum b) => (a -> b) -> Set a -> Set b
- fold :: Enum a => (b -> a -> b) -> b -> Set a -> b
- foldr :: Enum a => (a -> c -> c) -> c -> Set a -> c
- findMin :: Enum a => Set a -> a
- findMax :: Enum a => Set a -> a
- deleteMin :: Set a -> Set a
- deleteMax :: Set a -> Set a
- deleteFindMin :: Enum a => Set a -> (a, Set a)
- deleteFindMax :: Enum a => Set a -> (a, Set a)
- elems :: Enum a => Set a -> [a]
- toList :: Enum a => Set a -> [a]
- fromList :: Enum a => [a] -> Set a
- toAscList :: (Ord a, Enum a) => Set a -> [a]
- fromAscList :: Enum a => [a] -> Set a
- fromDistinctAscList :: Enum a => [a] -> Set a

# Set type

A set of values `a`

implemented as bitwise operations. Useful
for members of class Enum with no more elements than there are bits
in `Word`

.

# Operators

# Query

isSubsetOf :: Set a -> Set a -> BoolSource

*O(1)*. Is this a subset?
`(s1 `

tells whether `isSubsetOf`

s2)`s1`

is a subset of `s2`

.

isProperSubsetOf :: Set a -> Set a -> BoolSource

*O(1)*. Is this a proper subset? (ie. a subset but not equal).

# Construction

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

*O(1)*. 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

difference :: Set a -> Set a -> Set aSource

*O(1)*. Difference of two sets.

intersection :: Set a -> Set a -> Set aSource

*O(1)*. The intersection of two sets.

complement :: (Bounded a, Enum a) => Set a -> Set aSource

*O(1)*. The complement of a set with its universe set.
`complement`

can be used with bounded types for which the universe set
will be automatically created.

complementWith :: Set a -> Set a -> Set aSource

# Filter

filter :: Enum a => (a -> Bool) -> Set a -> Set aSource

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

partition :: Enum 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`

.

# Map

map :: (Enum a, Enum b) => (a -> b) -> Set a -> Set bSource

*O(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 :: (Enum a, Enum b) => (a -> b) -> Set a -> Set bSource

is provided for compatibility with the
Data.Set interface.
`mapMonotonic`

# Fold

fold :: Enum a => (b -> a -> b) -> b -> Set a -> bSource

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

# Min/Max

deleteFindMin :: Enum a => Set a -> (a, Set a)Source

deleteFindMax :: Enum a => Set a -> (a, Set a)Source

# Conversion

## List

## Ordered list

toAscList :: (Ord a, Enum a) => Set a -> [a]Source

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

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

`fromAscList`

and `fromDistinctAscList`

maintained for compatibility
with Data.Set, but here give no advantage.

fromDistinctAscList :: Enum a => [a] -> Set aSource