Copyright | 2011 Bryan O'Sullivan |
---|---|
License | BSD-style |
Maintainer | johan.tibell@gmail.com |
Stability | provisional |
Portability | portable |
Safe Haskell | Safe |
Language | Haskell2010 |
Data.HashSet
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.
Synopsis
- 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
- toMap :: HashSet a -> HashMap a ()
- fromMap :: HashMap a () -> HashSet a
Documentation
A set of values. A set cannot contain duplicate values.
Instances
Foldable HashSet Source # | |
Defined in Data.HashSet.Base Methods fold :: Monoid m => HashSet m -> m # foldMap :: Monoid m => (a -> m) -> HashSet a -> m # foldMap' :: Monoid m => (a -> m) -> HashSet a -> m # foldr :: (a -> b -> b) -> b -> HashSet a -> b # foldr' :: (a -> b -> b) -> b -> HashSet a -> b # foldl :: (b -> a -> b) -> b -> HashSet a -> b # foldl' :: (b -> a -> b) -> b -> HashSet a -> b # foldr1 :: (a -> a -> a) -> HashSet a -> a # foldl1 :: (a -> a -> a) -> HashSet a -> a # elem :: Eq a => a -> HashSet a -> Bool # maximum :: Ord a => HashSet a -> a # minimum :: Ord a => HashSet a -> a # | |
Eq1 HashSet Source # | |
Ord1 HashSet Source # | |
Defined in Data.HashSet.Base | |
Show1 HashSet Source # | |
Hashable1 HashSet Source # | |
Defined in Data.HashSet.Base | |
(Eq a, Hashable a) => IsList (HashSet a) Source # | |
Eq a => Eq (HashSet a) Source # | |
(Data a, Eq a, Hashable a) => Data (HashSet a) Source # | |
Defined in Data.HashSet.Base Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> HashSet a -> c (HashSet a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (HashSet a) # toConstr :: HashSet a -> Constr # dataTypeOf :: HashSet a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (HashSet a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (HashSet a)) # gmapT :: (forall b. Data b => b -> b) -> HashSet a -> HashSet a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> HashSet a -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> HashSet a -> r # gmapQ :: (forall d. Data d => d -> u) -> HashSet a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> HashSet a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> HashSet a -> m (HashSet a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> HashSet a -> m (HashSet a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> HashSet a -> m (HashSet a) # | |
Ord a => Ord (HashSet a) Source # | |
(Eq a, Hashable a, Read a) => Read (HashSet a) Source # | |
Show a => Show (HashSet a) Source # | |
(Hashable a, Eq a) => Semigroup (HashSet a) Source # | |
(Hashable a, Eq a) => Monoid (HashSet a) Source # | |
NFData a => NFData (HashSet a) Source # | |
Defined in Data.HashSet.Base | |
Hashable a => Hashable (HashSet a) Source # | |
Defined in Data.HashSet.Base | |
type Item (HashSet a) Source # | |
Defined in Data.HashSet.Base |
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(log n) Add the specified value to this set.
delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a Source #
O(log n) 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.
Conversions
Lists
toList :: HashSet a -> [a] Source #
O(n) Return a list of this set's elements. The list is produced lazily.
fromList :: (Eq a, Hashable a) => [a] -> HashSet a Source #
O(n*min(W, n)) Construct a set from a list of elements.