Rebase.Data.HashSet · rebase-1.21.2

newtypenewtype HashSet a

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

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

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.

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

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.

valueempty :: HashSet a

#

O(1) Construct an empty set.

Example1 expression

>>> HashSet.emptyfromList []

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

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"]

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

#

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

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

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

#

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

Example1 expression

>>> HashSet.singleton 1fromList [1]

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

#

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

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]

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]

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]

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)

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]

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

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

#

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

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]

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

valuefromMap :: HashMap a () -> HashSet a

#

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

Example1 expression

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

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.

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