Moduleunordered-containers-0.2.21Haskell2010

Data.HashSet.Internal

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

1 type
25 values

Packageunordered-containers-0.2.21
Exports26
LanguageHaskell2010
LicenceBSD-3-Clause
SourceInternal.hs

newtypenewtype HashSet a

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

Constructors

HashSet
- asMap :: HashMap a ()

Instances18Foldable, Eq1, Ord1, Show1, NFData1, Hashable1, …

Foldable HashSetDefined in unordered-containers-0.2.21 · Data.HashSet.Internal
Eq1 HashSetDefined in unordered-containers-0.2.21 · Data.HashSet.Internal
Ord1 HashSetDefined in unordered-containers-0.2.21 · Data.HashSet.Internal
Show1 HashSetDefined in unordered-containers-0.2.21 · Data.HashSet.Internal
NFData1 HashSetDefined in unordered-containers-0.2.21 · Data.HashSet.Internal
Hashable1 HashSetDefined in unordered-containers-0.2.21 · Data.HashSet.Internal
Lift a => Lift (HashSet a)Defined in unordered-containers-0.2.21 · Data.HashSet.Internal
Hashable a => IsList (HashSet a)Defined in unordered-containers-0.2.21 · Data.HashSet.Internal
Eq a => Eq (HashSet a)Defined in unordered-containers-0.2.21 · Data.HashSet.Internal
Note that, in the presence of hash collisions, equal HashSets may behave differently, i.e. extensionality may be violated:
Example2 expressions
```
>>> data D = A | B deriving (Eq, Show)>>> instance Hashable D where hashWithSalt salt _d = salt
```
Example2 expressions
```
>>> x = fromList [A, B]>>> y = fromList [B, A]
```
Example3 expressions
```
>>> x == yTrue>>> toList x[A,B]>>> toList y[B,A]
```
In general, the lack of extensionality can be observed with any function that depends on the key ordering, such as folds and traversals.
(Data a, Hashable a) => Data (HashSet a)Defined in unordered-containers-0.2.21 · Data.HashSet.Internal
Ord a => Ord (HashSet a)Defined in unordered-containers-0.2.21 · Data.HashSet.Internal
(Hashable a, Read a) => Read (HashSet a)Defined in unordered-containers-0.2.21 · Data.HashSet.Internal
Show a => Show (HashSet a)Defined in unordered-containers-0.2.21 · Data.HashSet.Internal
Hashable a => Semigroup (HashSet a)Defined in unordered-containers-0.2.21 · Data.HashSet.Internal
<> = union
O(n+m)
To obtain good performance, the smaller set must be presented as the first argument.
Examples
Example1 expression
```
>>> fromList [1,2] <> fromList [2,3]fromList [1,2,3]
```
Hashable a => Monoid (HashSet a)Defined in unordered-containers-0.2.21 · Data.HashSet.Internal
mempty = empty
mappend = union
O(n+m)
To obtain good performance, the smaller set must be presented as the first argument.
Examples
Example1 expression
```
>>> mappend (fromList [1,2]) (fromList [2,3])fromList [1,2,3]
```
NFData a => NFData (HashSet a)Defined in unordered-containers-0.2.21 · Data.HashSet.Internal
Hashable a => Hashable (HashSet a)Defined in unordered-containers-0.2.21 · Data.HashSet.Internal
type Item (HashSet a) = aDefined in unordered-containers-0.2.21 · Data.HashSet.Internal

Construction

2 declarations

valueempty :: HashSet a

O(1) Construct an empty set.

Example1 expression

>>> HashSet.emptyfromList []

valuesingleton :: Hashable a => a -> HashSet a

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

Example1 expression

>>> HashSet.singleton 1fromList [1]

Basic interface

7 declarations

valuenull :: HashSet a -> Bool

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

Example2 expressions

>>> HashSet.null HashSet.emptyTrue>>> HashSet.null (HashSet.singleton 1)False

valuesize :: HashSet a -> Int

O(n) Return the number of elements in this set.

Example2 expressions

>>> HashSet.size HashSet.empty0>>> HashSet.size (HashSet.fromList [1,2,3])3

valuemember :: Hashable a => a -> HashSet a -> Bool

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

Example2 expressions

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

valuelookupElement :: Hashable a => a -> HashSet a -> Maybe a

O(\log n) For a given value, return the equal element in the set if present, otherwise return Nothing.

This is useful for interning, i.e. to reduce memory usage.

valueinsert :: Hashable a => a -> HashSet a -> HashSet a

O(\log n) Add the specified value to this set.

Example1 expression

>>> HashSet.insert 1 HashSet.emptyfromList [1]

valuedelete :: Hashable a => a -> HashSet a -> HashSet a

O(\log n) Remove the specified value from this set if present.

Example2 expressions

>>> HashSet.delete 1 (HashSet.fromList [1,2,3])fromList [2,3]>>> HashSet.delete 1 (HashSet.fromList [4,5,6])fromList [4,5,6]

valueisSubsetOf :: Hashable a => HashSet a -> HashSet a -> Bool

O(n \log m) Inclusion of sets.

Examples

Example1 expression

>>> fromList [1,3] `isSubsetOf` fromList [1,2,3]True

Example1 expression

>>> fromList [1,2] `isSubsetOf` fromList [1,3]False

Transformations

1 declaration

valuemap :: Hashable b => (a -> b) -> HashSet a -> HashSet b

O(n \log n) Transform this set by applying a function to every value. The resulting set may be smaller than the source.

Example1 expression

>>> HashSet.map show (HashSet.fromList [1,2,3])HashSet.fromList ["1","2","3"]

Combine

2 declarations

valueunion :: Eq a => HashSet a -> HashSet a -> HashSet a

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.

Example1 expression

>>> union (fromList [1,2]) (fromList [2,3])fromList [1,2,3]

valueunions :: Eq a => [HashSet a] -> HashSet a

Construct a set containing all elements from a list of sets.

Difference and intersection

3 declarations

valuedifference :: Hashable a => HashSet a -> HashSet a -> HashSet a

O(n \log m) Difference of two sets. Return elements of the first set not existing in the second.

Example1 expression

>>> HashSet.difference (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])fromList [1]

valueintersection :: Eq a => HashSet a -> HashSet a -> HashSet a

O(n \log m) Intersection of two sets. Return elements present in both the first set and the second.

Example1 expression

>>> HashSet.intersection (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])fromList [2,3]

valuedisjoint :: Eq k => HashSet k -> HashSet k -> Bool

O(n \log m) Check whether two sets are disjoint (i.e., their intersection is empty).

xs `disjoint` ys = null (xs `intersection` ys)

Folds

4 declarations

valuefoldr :: (b -> a -> a) -> a -> HashSet b -> a

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

valuefoldr' :: (b -> a -> a) -> a -> HashSet b -> a

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.

valuefoldl :: (a -> b -> a) -> a -> HashSet b -> a

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

valuefoldl' :: (a -> b -> a) -> a -> HashSet b -> a

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

1 declaration

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

O(n) Filter this set by retaining only elements satisfying a predicate.

Conversions

0 declarations

Lists

valuetoList :: HashSet a -> [a]

O(n) Return a list of this set's elements. The list is produced lazily. The order of its elements is unspecified, and it may change from version to version of either this package or of hashable.

valuefromList :: Hashable a => [a] -> HashSet a

O(n \log n) Construct a set from a list of elements.

HashMaps

3 declarations

valuetoMap :: HashSet a -> HashMap a ()

O(1) Convert to set to the equivalent HashMap with () values.

Example1 expression

>>> HashSet.toMap (HashSet.singleton 1)fromList [(1,())]

valuefromMap :: HashMap a () -> HashSet a

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

Example1 expression

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

valuekeysSet :: HashMap k a -> HashSet k

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

Example1 expression

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