| Portability | portable |
|---|---|
| Stability | provisional |
| Maintainer | johan.tibell@gmail.com |
| Safe Haskell | Safe-Infered |
Data.HashSet
Contents
Description
A set of hashable values. A set cannot contain duplicate items.
A HashSet makes no guarantees as to the order of its elements.
The implementation is based on big-endian patricia trees, indexed
by a hash of the original value. A HashSet is often faster than
other tree-based set types, especially when value comparison is
expensive, as in the case of strings.
Many operations have a worst-case complexity of O(min(n,W)).
This means that the operation can become linear in the number of
elements with a maximum of W -- the number of bits in an Int
(32 or 64).
- data HashSet a
- empty :: HashSet a
- singleton :: Hashable a => a -> HashSet a
- union :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
- null :: HashSet a -> Bool
- size :: HashSet a -> Int
- member :: (Eq a, Hashable a) => a -> HashSet a -> Bool
- insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a
- delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a
- map :: (Hashable b, Eq b) => (a -> b) -> HashSet a -> HashSet b
- difference :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
- intersection :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
- foldl' :: (a -> b -> a) -> a -> HashSet b -> a
- foldr :: (b -> a -> a) -> a -> HashSet b -> a
- filter :: (a -> Bool) -> HashSet a -> HashSet a
- toList :: HashSet a -> [a]
- fromList :: (Eq a, Hashable a) => [a] -> HashSet a
Documentation
A set of values. A set cannot contain duplicate values.
Construction
Combine
union :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet aSource
O(n) Construct a set containing all elements from both sets.
To obtain good performance, the smaller set must be presented as the first argument.
Basic interface
insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet aSource
O(min(n,W)) Add the specified value to this set.
delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet aSource
O(min(n,W)) Remove the specified value from this set if present.
Transformations
map :: (Hashable b, Eq b) => (a -> b) -> HashSet a -> HashSet bSource
O(n) Transform this set by applying a function to every value. The resulting set may be smaller than the source.
Difference and intersection
difference :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet aSource
O(n) Difference of two sets. Return elements of the first set not existing in the second.
intersection :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet aSource
O(n) Intersection of two sets. Return elements present in both the first set and the second.
Folds
foldl' :: (a -> b -> a) -> a -> HashSet b -> aSource
O(n) Reduce this set by applying a binary operator to all elements, using the given starting value (typically the left-identity of the operator). Each application of the operator is evaluated before before using the result in the next application. This function is strict in the starting value.
foldr :: (b -> a -> a) -> a -> HashSet b -> aSource
O(n) Reduce this set by applying a binary operator to all elements, using the given starting value (typically the right-identity of the operator).
Filter
filter :: (a -> Bool) -> HashSet a -> HashSet aSource
O(n) Filter this set by retaining only elements satisfying a predicate.