Portability | portable |
---|---|
Stability | provisional |
Maintainer | fox@ucw.cz |
Persistent Set
based on hashing, which is defined as
dataSet
e =Data.IntMap.IntMap
(Some e)
is an Data.IntMap.IntMap
indexed by hash values of elements,
containing a value of Some e
. That contains either one e
or a
with elements of the same hash values.
Data.Set.Set
e
The interface of a Set
is a suitable subset of Data.IntSet.IntSet
and can be used as a drop-in replacement of Data.Set.Set
.
The complexity of operations is determined by the complexities of
Data.IntMap.IntMap
and Data.Set.Set
operations. See the sources of
Set
to see which operations from containers
package are used.
- data Set a
- type HashSet a = Set a
- (\\) :: Ord a => Set a -> Set a -> Set a
- null :: Set a -> Bool
- size :: Set a -> Int
- member :: (Hashable a, Ord a) => a -> Set a -> Bool
- notMember :: (Hashable a, 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 :: Hashable a => a -> Set a
- insert :: (Hashable a, Ord a) => a -> Set a -> Set a
- delete :: (Hashable a, 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)
- map :: (Hashable b, Ord b) => (a -> b) -> Set a -> Set b
- fold :: (a -> b -> b) -> b -> Set a -> b
- elems :: Set a -> [a]
- toList :: Set a -> [a]
- fromList :: (Hashable a, Ord a) => [a] -> Set a
Documentation
The abstract type of a Set
. Its interface is a suitable
subset of Data.IntSet.IntSet
.
The HashSet
is a type synonym for Set
for backward compatibility.
It is deprecated and will be removed in furture releases.
Operators
Query
isProperSubsetOf :: Ord a => Set a -> Set a -> BoolSource
Is this a proper subset? (ie. a subset but not equal).
Construction
insert :: (Hashable a, Ord a) => a -> Set a -> Set aSource
Add a value to the set. When the value is already an element of the set,
it is replaced by the new one, ie. insert
is left-biased.
delete :: (Hashable a, Ord a) => a -> Set a -> Set aSource
Delete a value in the set. Returns the original set when the value was not present.
Combine
Filter
filter :: Ord a => (a -> Bool) -> Set a -> Set aSource
Filter all elements that satisfy some predicate.
partition :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)Source
Partition the set according to some predicate. The first set contains all elements that satisfy the predicate, the second all elements that fail the predicate.
Map
map :: (Hashable b, Ord b) => (a -> b) -> Set a -> Set bSource
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
Fold
fold :: (a -> b -> b) -> b -> Set a -> bSource
Fold over the elements of a set in an unspecified order.