| Copyright | 2011 Bryan O'Sullivan |
|---|---|
| License | BSD-style |
| Maintainer | johan.tibell@gmail.com |
| Stability | provisional |
| Portability | portable |
| Safe Haskell | None |
| Language | Haskell98 |
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 hash array mapped trie. 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 average-case complexity of O(log n). The implementation uses a large base (i.e. 16) so in practice these operations are constant time.
- data HashSet a
- empty :: HashSet a
- singleton :: Hashable a => a -> HashSet a
- union :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
- unions :: (Eq a, Hashable 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.
Instances
| Foldable HashSet | |
| (Eq a, Hashable a) => IsList (HashSet a) | |
| (Hashable a, Eq a) => Eq (HashSet a) | |
| (Data a, Eq a, Hashable a) => Data (HashSet a) | |
| (Eq a, Hashable a, Read a) => Read (HashSet a) | |
| Show a => Show (HashSet a) | |
| (Hashable a, Eq a) => Monoid (HashSet a) | |
| NFData a => NFData (HashSet a) | |
| Typeable (* -> *) HashSet | |
| type Item (HashSet a) = a |
Construction
Combine
union :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a Source
O(n+m) Construct a set containing all elements from both sets.
To obtain good performance, the smaller set must be presented as the first argument.
unions :: (Eq a, Hashable a) => [HashSet a] -> HashSet a Source
Construct a set containing all elements from a list of sets.
Basic interface
insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a Source
O(min(n,W)) Add the specified value to this set.
delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a Source
O(min(n,W)) Remove the specified value from this set if present.
Transformations
map :: (Hashable b, Eq b) => (a -> b) -> HashSet a -> HashSet b Source
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 a Source
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 a Source
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 -> a Source
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 -> a Source
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 a Source
O(n) Filter this set by retaining only elements satisfying a predicate.