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.

>>> import qualified Data.HashSet as HashSet

>>> let dataStructures = HashSet.fromList ["Set", "Map", "Graph", "Sequence"]

Basic Operations

Check membership in a set:

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

>>> HashSet.member "Map" dataStructures
True

>>> HashSet.member "Trie" dataStructures
False

Add a new entry to the set:

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

>>> HashSet.member "Trie" moreDataStructures
> True

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

>>> let fewerDataStructures = HashSet.delete "Graph" dataStructures

>>> HashSet.toList fewerDataStructures
["Map","Set","Sequence"]

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

>>> let unorderedDataStructures = HashSet.fromList ["HashSet", "HashMap"]

>>> HashSet.union dataStructures unorderedDataStructures
fromList ["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:

>>> :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!

>>> let people = HashSet.fromList [Person "Lana" True, Person "Joe" False, Person "Simon" True]

>>> HashSet.filter likesDogs people
fromList [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 <math>. The implementation uses a large base (i.e. 16) so in practice these operations are constant time.

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

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

Set with hashed members. Import as:

import qualified RIO.HashSet as HS

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

Persistent Set based on hashing, which is defined as

data Set e = IntMap (Some e)

is an IntMap indexed by hash values of elements, containing a value of Some e. That contains either one e or a Set e with elements of the same hash values. The interface of a Set is a suitable subset of IntSet and can be used as a drop-in replacement of Set. The complexity of operations is determined by the complexities of IntMap and Set operations. See the sources of Set to see which operations from containers package are used.

Deprecated: HashSet is deprecated. Please use Set instead.

A HashSet whose contents are tracked by the type parameter s. This is a "singleton": for a given s there's only one value of this type. Since this is just a Dict, you can freely convert between the value (HashSet) and the constraint (KnownHashSet). This library prefers to use the constraint.

Fold values into a hash-set

This is a slight lie, as roundtrip doesn't preserve ordering.

Codec for HashSet of values. Represented in TOML as an array of tables. Example: Haskell HashSet Int can look like this in your TOML file:

foo =
[ {a = 1}
, {a = 2}
]

Decodes to an empty HashSet in case of the missing field in TOML.

Decode a HashSet from a List with distinct elements.

>>> input (hashSetFromDistinctList natural) "[1, 2, 3]"
fromList [1,2,3]

An error is thrown if the list contains duplicates.

>>> input (hashSetFromDistinctList natural) "[1, 1, 3]"
*** Exception: Error: Failed extraction

The expression type-checked successfully but the transformation to the target
type failed with the following error:

One duplicate element in the list: 1

>>> input (hashSetFromDistinctList natural) "[1, 1, 3, 3]"
*** Exception: Error: Failed extraction

The expression type-checked successfully but the transformation to the target
type failed with the following error:

2 duplicates were found in the list, including 1

Decode a HashSet from a List.

>>> input (hashSetIgnoringDuplicates natural) "[1, 2, 3]"
fromList [1,2,3]

Duplicate elements are ignored.

>>> input (hashSetIgnoringDuplicates natural) "[1, 1, 3]"
fromList [1,3]

HashSet which tries its best to remember insertion order of elements.

Takes a BiMap of a value and returns a BiMap for a HashSet of values and AnyValue as an array. Usually used as the arrayHashSetOf combinator.

Codec for hash sets. Takes converter for single hashable value and returns a set of hashable values. Example: Haskell HashSet Int can look like this in your TOML file:

foo = [1, 2, 3]

In case of the missing field, the following error will be seen:

tomland decode error:  Key foo is not found