Moduleunordered-containers-0.2.21Haskell2010

Data.HashSet

Introduction

HashSet allows you to store unique elements, providing efficient insertion, lookups, and deletion. A HashSet makes no guarantees as to the order of its elements.

If you are storing sets of Data.Ints consider using Data.IntSet from the containers package.

Examples

All the examples below assume HashSet is imported qualified, and uses the following dataStructures set.

Example2 expressions

>>> import qualified Data.HashSet as HashSet>>> let dataStructures = HashSet.fromList ["Set", "Map", "Graph", "Sequence"]

Basic Operations

Check membership in a set:

Example3 expressions

>>> -- Check if "Map" and "Trie" are in the set of data structures.>>> HashSet.member "Map" dataStructuresTrue>>> HashSet.member "Trie" dataStructuresFalse

Add a new entry to the set:

Example2 expressions

>>> let moreDataStructures = HashSet.insert "Trie" dataStructures>>> HashSet.member "Trie" moreDataStructures> True

Remove the "Graph" entry from the set of data structures.

Example2 expressions

>>> let fewerDataStructures = HashSet.delete "Graph" dataStructures>>> HashSet.toList fewerDataStructures["Map","Set","Sequence"]

Create a new set and combine it with our original set.

Example2 expressions

>>> let unorderedDataStructures = HashSet.fromList ["HashSet", "HashMap"]>>> HashSet.union dataStructures unorderedDataStructuresfromList ["Map","HashSet","Graph","HashMap","Set","Sequence"]

Using custom data with HashSet

To create a HashSet of your custom type, the type must have instances for Eq and Hashable. The Hashable typeclass is defined in the hashable package, see the documentation for information on how to make your type an instance of Hashable.

We'll start by setting up our custom data type:

Example5 expressions

>>> :set -XDeriveGeneric>>> import GHC.Generics (Generic)>>> import Data.Hashable>>> data Person = Person { name :: String, likesDogs :: Bool } deriving (Show, Eq, Generic)>>> instance Hashable Person

And now we'll use it!

Example2 expressions

>>> let people = HashSet.fromList [Person "Lana" True, Person "Joe" False, Person "Simon" True]>>> HashSet.filter likesDogs peoplefromList [Person {name = "Simon", likesDogs = True},Person {name = "Lana", likesDogs = True}]

Performance

The implementation is based on hash array mapped tries. A HashSet is often faster than other Ord-based set types, especially when value comparisons are 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
22 values

Packageunordered-containers-0.2.21
Exports23
LanguageHaskell2010
LicenceBSD-3-Clause
SourceHashSet.hs

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

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

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

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]