unordered-containers-0.2.12.0: Efficient hashing-based container types

Copyright2011 Bryan O'Sullivan
LicenseBSD-style
Maintainerjohan.tibell@gmail.com
Portabilityportable
Safe HaskellTrustworthy
LanguageHaskell2010

Data.HashSet.Internal

Contents

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. 16) so in practice these operations are constant time.

Synopsis

Documentation

data HashSet a Source #

A set of values. A set cannot contain duplicate values.

Instances
Foldable HashSet Source # 
Instance details

Defined in Data.HashSet.Internal

Methods

fold :: Monoid m => HashSet m -> 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 #

toList :: HashSet a -> [a] #

null :: HashSet a -> Bool #

length :: HashSet a -> Int #

elem :: Eq a => a -> HashSet a -> Bool #

maximum :: Ord a => HashSet a -> a #

minimum :: Ord a => HashSet a -> a #

sum :: Num a => HashSet a -> a #

product :: Num a => HashSet a -> a #

Eq1 HashSet Source # 
Instance details

Defined in Data.HashSet.Internal

Methods

liftEq :: (a -> b -> Bool) -> HashSet a -> HashSet b -> Bool #

Ord1 HashSet Source # 
Instance details

Defined in Data.HashSet.Internal

Methods

liftCompare :: (a -> b -> Ordering) -> HashSet a -> HashSet b -> Ordering #

Show1 HashSet Source # 
Instance details

Defined in Data.HashSet.Internal

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> HashSet a -> ShowS #

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [HashSet a] -> ShowS #

Hashable1 HashSet Source # 
Instance details

Defined in Data.HashSet.Internal

Methods

liftHashWithSalt :: (Int -> a -> Int) -> Int -> HashSet a -> Int #

(Eq a, Hashable a) => IsList (HashSet a) Source # 
Instance details

Defined in Data.HashSet.Internal

Associated Types

type Item (HashSet a) :: Type #

Methods

fromList :: [Item (HashSet a)] -> HashSet a #

fromListN :: Int -> [Item (HashSet a)] -> HashSet a #

toList :: HashSet a -> [Item (HashSet a)] #

Eq a => Eq (HashSet a) Source #

Note that, in the presence of hash collisions, equal HashSets may behave differently, i.e. substitutivity may be violated:

>>> data D = A | B deriving (Eq, Show)
>>> instance Hashable D where hashWithSalt salt _d = salt
>>> x = fromList [A, B]
>>> y = fromList [B, A]
>>> x == y
True
>>> toList x
[A,B]
>>> toList y
[B,A]

In general, the lack of substitutivity can be observed with any function that depends on the key ordering, such as folds and traversals.

Instance details

Defined in Data.HashSet.Internal

Methods

(==) :: HashSet a -> HashSet a -> Bool #

(/=) :: HashSet a -> HashSet a -> Bool #

(Data a, Eq a, Hashable a) => Data (HashSet a) Source # 
Instance details

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) #

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 :: (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 # 
Instance details

Defined in Data.HashSet.Internal

Methods

compare :: HashSet a -> HashSet a -> Ordering #

(<) :: HashSet a -> HashSet a -> Bool #

(<=) :: HashSet a -> HashSet a -> Bool #

(>) :: HashSet a -> HashSet a -> Bool #

(>=) :: HashSet a -> HashSet a -> Bool #

max :: HashSet a -> HashSet a -> HashSet a #

min :: HashSet a -> HashSet a -> HashSet a #

(Eq a, Hashable a, Read a) => Read (HashSet a) Source # 
Instance details

Defined in Data.HashSet.Internal

Show a => Show (HashSet a) Source # 
Instance details

Defined in Data.HashSet.Internal

Methods

showsPrec :: Int -> HashSet a -> ShowS #

show :: HashSet a -> String #

showList :: [HashSet a] -> ShowS #

(Hashable a, Eq a) => Semigroup (HashSet a) Source #

<> = union

O(n+m)

To obtain good performance, the smaller set must be presented as the first argument.

Examples

Expand
>>> fromList [1,2] <> fromList [2,3]
fromList [1,2,3]
Instance details

Defined in Data.HashSet.Internal

Methods

(<>) :: HashSet a -> HashSet a -> HashSet a #

sconcat :: NonEmpty (HashSet a) -> HashSet a #

stimes :: Integral b => b -> HashSet a -> HashSet a #

(Hashable a, Eq a) => Monoid (HashSet a) Source #

mempty = empty

mappend = union

O(n+m)

To obtain good performance, the smaller set must be presented as the first argument.

Examples

Expand
>>> mappend (fromList [1,2]) (fromList [2,3])
fromList [1,2,3]
Instance details

Defined in Data.HashSet.Internal

Methods

mempty :: HashSet a #

mappend :: HashSet a -> HashSet a -> HashSet a #

mconcat :: [HashSet a] -> HashSet a #

NFData a => NFData (HashSet a) Source # 
Instance details

Defined in Data.HashSet.Internal

Methods

rnf :: HashSet a -> () #

Hashable a => Hashable (HashSet a) Source # 
Instance details

Defined in Data.HashSet.Internal

Methods

hashWithSalt :: Int -> HashSet a -> Int #

hash :: HashSet a -> Int #

type Item (HashSet a) Source # 
Instance details

Defined in Data.HashSet.Internal

type Item (HashSet a) = a

Construction

empty :: HashSet a Source #

O(1) Construct an empty set.

>>> HashSet.empty
fromList []

singleton :: Hashable a => a -> HashSet a Source #

O(1) Construct a set with a single element.

>>> HashSet.singleton 1
fromList [1]

Basic interface

null :: HashSet a -> Bool Source #

O(1) Return True if this set is empty, False otherwise.

>>> HashSet.null HashSet.empty
True
>>> HashSet.null (HashSet.singleton 1)
False

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

member :: (Eq a, Hashable a) => a -> HashSet a -> Bool Source #

O(log n) Return True if the given value is present in this set, False otherwise.

>>> HashSet.member 1 (Hashset.fromList [1,2,3])
True
>>> HashSet.member 1 (Hashset.fromList [4,5,6])
False

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

Expand
>>> 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,())]

fromMap :: HashMap a () -> HashSet a Source #

O(1) Convert from the equivalent HashMap with () values.

>>> HashSet.fromMap (HashMap.singleton 1 ())
fromList [1]

keysSet :: HashMap k a -> HashSet k Source #

O(n) Produce a HashSet of all the keys in the given HashMap.

>>> HashSet.keysSet (HashMap.fromList [(1, "a"), (2, "b")]
fromList [1,2]

Since: 0.2.10.0