Copyright | 2011 Bryan O'Sullivan |
---|---|
License | BSD-style |
Maintainer | johan.tibell@gmail.com |
Portability | portable |
Safe Haskell | Trustworthy |
Language | Haskell2010 |
Data.HashSet.Internal
Description
WARNING
This module is considered internal .
The Package Versioning Policy does not apply .
The contents of this module may change in any way whatsoever and without any warning between minor versions of this package.
Authors importing this module are expected to track development closely.
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 tries
. 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. 32) so in practice these operations are constant time.
Synopsis
- newtype HashSet a = HashSet { }
- empty :: HashSet a
- singleton :: Hashable a => 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
- isSubsetOf :: ( Eq a, Hashable a) => HashSet a -> HashSet a -> Bool
- map :: ( Hashable b, Eq b) => (a -> b) -> HashSet a -> HashSet b
- union :: ( Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
- unions :: ( Eq a, Hashable a) => [ HashSet a] -> HashSet a
- difference :: ( Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
- intersection :: ( Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
- foldr :: (b -> a -> a) -> a -> HashSet b -> a
- foldr' :: (b -> a -> a) -> a -> HashSet b -> a
- foldl :: (a -> b -> a) -> a -> HashSet b -> a
- foldl' :: (a -> b -> 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
- keysSet :: HashMap k a -> HashSet k
Documentation
A set of values. A set cannot contain duplicate values.
Instances
Foldable HashSet Source # | |
Defined in Data.HashSet.Internal Methods fold :: Monoid m => HashSet m -> m Source # foldMap :: Monoid m => (a -> m) -> HashSet a -> m Source # foldMap' :: Monoid m => (a -> m) -> HashSet a -> m Source # foldr :: (a -> b -> b) -> b -> HashSet a -> b Source # foldr' :: (a -> b -> b) -> b -> HashSet a -> b Source # foldl :: (b -> a -> b) -> b -> HashSet a -> b Source # foldl' :: (b -> a -> b) -> b -> HashSet a -> b Source # foldr1 :: (a -> a -> a) -> HashSet a -> a Source # foldl1 :: (a -> a -> a) -> HashSet a -> a Source # toList :: HashSet a -> [a] Source # null :: HashSet a -> Bool Source # length :: HashSet a -> Int Source # elem :: Eq a => a -> HashSet a -> Bool Source # maximum :: Ord a => HashSet a -> a Source # minimum :: Ord a => HashSet a -> a Source # |
|
Eq1 HashSet Source # | |
Ord1 HashSet Source # | |
Defined in Data.HashSet.Internal |
|
Show1 HashSet Source # | |
NFData1 HashSet Source # |
Since: 0.2.14.0 |
Defined in Data.HashSet.Internal |
|
Hashable1 HashSet Source # | |
Defined in Data.HashSet.Internal |
|
Lift a => Lift ( HashSet a :: Type ) Source # |
Since: 0.2.17.0 |
( Eq a, Hashable a) => IsList ( HashSet a) Source # | |
Eq a => Eq ( HashSet a) Source # |
Note that, in the presence of hash collisions, equal
In general, the lack of substitutivity can be observed with any function that depends on the key ordering, such as folds and traversals. |
( Data a, Eq a, Hashable a) => Data ( HashSet a) Source # | |
Defined in Data.HashSet.Internal Methods gfoldl :: ( forall d b. Data d => c (d -> b) -> d -> c b) -> ( forall g. g -> c g) -> HashSet a -> c ( HashSet a) Source # gunfold :: ( forall b r. Data b => c (b -> r) -> c r) -> ( forall r. r -> c r) -> Constr -> c ( HashSet a) Source # toConstr :: HashSet a -> Constr Source # dataTypeOf :: HashSet a -> DataType Source # dataCast1 :: Typeable t => ( forall d. Data d => c (t d)) -> Maybe (c ( HashSet a)) Source # dataCast2 :: Typeable t => ( forall d e. ( Data d, Data e) => c (t d e)) -> Maybe (c ( HashSet a)) Source # gmapT :: ( forall b. Data b => b -> b) -> HashSet a -> HashSet a Source # gmapQl :: (r -> r' -> r) -> r -> ( forall d. Data d => d -> r') -> HashSet a -> r Source # gmapQr :: forall r r'. (r' -> r -> r) -> r -> ( forall d. Data d => d -> r') -> HashSet a -> r Source # gmapQ :: ( forall d. Data d => d -> u) -> HashSet a -> [u] Source # gmapQi :: Int -> ( forall d. Data d => d -> u) -> HashSet a -> u Source # gmapM :: Monad m => ( forall d. Data d => d -> m d) -> HashSet a -> m ( HashSet a) Source # gmapMp :: MonadPlus m => ( forall d. Data d => d -> m d) -> HashSet a -> m ( HashSet a) Source # gmapMo :: MonadPlus m => ( forall d. Data d => d -> m d) -> HashSet a -> m ( HashSet a) Source # |
|
Ord a => Ord ( HashSet a) Source # | |
Defined in Data.HashSet.Internal Methods compare :: HashSet a -> HashSet a -> Ordering Source # (<) :: HashSet a -> HashSet a -> Bool Source # (<=) :: HashSet a -> HashSet a -> Bool Source # (>) :: HashSet a -> HashSet a -> Bool Source # (>=) :: HashSet a -> HashSet a -> Bool 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 # |
\(O(n+m)\) To obtain good performance, the smaller set must be presented as the first argument. Examples
|
( Hashable a, Eq a) => Monoid ( HashSet a) Source # |
\(O(n+m)\) To obtain good performance, the smaller set must be presented as the first argument. Examples
|
NFData a => NFData ( HashSet a) Source # | |
Defined in Data.HashSet.Internal |
|
Hashable a => Hashable ( HashSet a) Source # | |
type Item ( HashSet a) Source # | |
Defined in Data.HashSet.Internal |
Construction
singleton :: Hashable a => a -> HashSet a Source #
\(O(1)\) Construct a set with a single element.
>>>
HashSet.singleton 1
fromList [1]
Basic interface
size :: HashSet a -> Int Source #
\(O(n)\) Return the number of elements in this set.
>>>
HashSet.size HashSet.empty
0>>>
HashSet.size (HashSet.fromList [1,2,3])
3
insert :: ( Eq a, Hashable a) => a -> HashSet a -> HashSet a Source #
\(O(\log n)\) Add the specified value to this set.
>>>
HashSet.insert 1 HashSet.empty
fromList [1]
delete :: ( Eq a, Hashable a) => a -> HashSet a -> HashSet a Source #
\(O(\log n)\) Remove the specified value from this set if present.
>>>
HashSet.delete 1 (HashSet.fromList [1,2,3])
fromList [2,3]>>>
HashSet.delete 1 (HashSet.fromList [4,5,6])
fromList [4,5,6]
isSubsetOf :: ( Eq a, Hashable a) => HashSet a -> HashSet a -> Bool Source #
\(O(n \log m)\) Inclusion of sets.
Examples
>>>
fromList [1,3] `isSubsetOf` fromList [1,2,3]
True
>>>
fromList [1,2] `isSubsetOf` fromList [1,3]
False
Since: 0.2.12
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.
>>>
HashSet.map show (HashSet.fromList [1,2,3])
HashSet.fromList ["1","2","3"]
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.
>>>
union (fromList [1,2]) (fromList [2,3])
fromList [1,2,3]
unions :: ( Eq a, Hashable a) => [ HashSet a] -> HashSet a Source #
Construct a set containing all elements from a list of sets.
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.
>>>
HashSet.difference (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])
fromList [1]
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.
>>>
HashSet.intersection (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])
fromList [2,3]
Folds
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).
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). Each application of the operator is evaluated before before using the result in the next application. This function is strict in the starting value.
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).
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.
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.
HashMaps
toMap :: HashSet a -> HashMap a () Source #
\(O(1)\)
Convert to set to the equivalent
HashMap
with
()
values.
>>>
HashSet.toMap (HashSet.singleton 1)
fromList [(1,())]