Data.HashSet

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

$O(1)$ Construct an empty set.

>>> HashSet.empty
fromList []

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

>>> HashSet.singleton 1
fromList [1]

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

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

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

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

>>> HashSet.null HashSet.empty
True
>>> HashSet.null (HashSet.singleton 1)
False

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

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

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

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

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

>>> HashSet.insert 1 HashSet.empty
fromList [1]

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

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

$O(n\log m)$ Inclusion of sets.

Examples

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

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

Since: 0.2.12

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

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

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

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

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

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

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

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

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

$O(n)$ Return a list of this set's elements. The list is produced lazily.

$O(nmin(W,n))$ Construct a set from a list of elements.

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

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

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

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