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