RIO.HashSet · rio-0.1.22.0 · horizon-platform

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

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]

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.

Basic interface

5 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

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]

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

Difference and intersection

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

Folds

2 declarations

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.

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

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

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

Examples

Examples

Construction

Combine

Basic interface

Transformations

Difference and intersection

Folds

Filter

Conversions

Lists

HashMaps