Haskell Hierarchical Libraries (collections package)ContentsIndex
Data.Set.Enum
Contents
Set type
Operators
Query
Construction
Combine
Filter
Map
Fold
Min/Max
Conversion
List
Ordered list
Description

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.

Synopsis
data Set a
(\\) :: Set a -> Set a -> Set a
null :: Set a -> Bool
size :: 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
data Set a
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.
show/hide Instances
Typeable1 Set
Eq (Set a)
Enum a => Monoid (Set a)
(Enum a, Ord a) => Ord (Set a)
(Enum a, Show a) => Show (Set a)
Enum a => Foldable (Set a) a
Enum a => Set (Set a) a
Enum a => Collection (Set a) a a
Enum a => Map (Set a) a ()
Operators
(\\) :: Set a -> Set a -> Set a
Query
null :: Set a -> Bool
O(1). Is this the empty set?
size :: Set a -> Int
O(1). The number of elements in the set.
member :: Enum a => a -> Set a -> Bool
O(1). Is the element in the set?
isSubsetOf :: Set a -> Set a -> Bool
O(1). Is this a subset? (s1 isSubsetOf s2) tells whether s1 is a subset of s2.
isProperSubsetOf :: Set a -> Set a -> Bool
O(1). Is this a proper subset? (ie. a subset but not equal).
Construction
empty :: Set a
O(1). The empty set.
singleton :: Enum a => a -> Set a
O(1). Create a singleton set.
insert :: Enum a => a -> Set a -> Set a
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.
delete :: Enum a => a -> Set a -> Set a
O(1). Delete an element from a set.
Combine
union :: Set a -> Set a -> Set a
O(1). The union of two sets.
unions :: [Set a] -> Set a
The union of a list of sets: (unions == foldl union empty).
difference :: Set a -> Set a -> Set a
O(1). Difference of two sets.
intersection :: Set a -> Set a -> Set a
O(1). The intersection of two sets.
complement :: (Bounded a, Enum a) => Set a -> Set a
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 a
Filter
filter :: Enum a => (a -> Bool) -> Set a -> Set a
O(n). Filter all elements that satisfy the predicate.
partition :: Enum a => (a -> Bool) -> Set a -> (Set a, Set a)
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, Enum a) => a -> Set a -> (Set a, Set a)
splitMember :: (Ord a, Enum a) => a -> Set a -> (Set a, Bool, Set a)
Map
map :: (Enum a, Enum b) => (a -> b) -> Set a -> Set b

O(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 :: (Enum a, Enum b) => (a -> b) -> Set a -> Set b
mapMonotonic is provided for compatibility with the Data.Set interface.
Fold
fold :: Enum a => (b -> a -> b) -> b -> Set a -> b
O(n). Fold over the elements of a set in an unspecified order.
foldr :: Enum a => (a -> c -> c) -> c -> Set a -> c
Min/Max
findMin :: Enum a => Set a -> a
O(n). The minimal element of a set.
findMax :: Enum a => Set a -> a
O(n). The maximal element of a set.
deleteMin :: Set a -> Set a
O(n). Delete the minimal element.
deleteMax :: Set a -> Set a
O(n). Delete the maximal element.
deleteFindMin :: Enum a => Set a -> (a, Set a)
deleteFindMax :: Enum a => Set a -> (a, Set a)
Conversion
List
elems :: Enum a => Set a -> [a]
O(n). The elements of a set.
toList :: Enum a => Set a -> [a]
O(n). Convert the set to a list of elements.
fromList :: Enum a => [a] -> Set a
O(n). Create a set from a list of elements.
Ordered list
toAscList :: (Ord a, Enum a) => Set a -> [a]
O(n). Convert the set to an ascending list of elements.
fromAscList :: Enum a => [a] -> Set a
fromAscList and fromDistinctAscList maintained for compatibility with Data.Set, but here give no advantage.
fromDistinctAscList :: Enum a => [a] -> Set a
Produced by Haddock version 0.7