Hash Sets

What are Hash Sets good for?

A Hash Set is very similar to a Set and can solve many of the same problems using virtually the same API. Note though, that the value type must have an instance of the Hashable class instead of the Ord class. This can usually be derived if it does not already exist.

Core operations (insert, delete, member) are typically more efficient with Hash Sets. Technically, they are still logarithmic in complexity, but for most practical cases you can think of them as constant time O(1).

What are Hash Sets not as good for?

Hash sets make no use of any ordering on their elements. Thus operations like max and min are inefficient, taking O(n) time. The lookup family of operations we saw with sets does not exist with hash sets.

Hash Set Parameters and Constraints

Hash Sets have a single type parameter for the contained type. Unlike normal sets, which require an Ord-erable type, for hash sets this type must satisfy the Hashable type class. This allows the structure to create its own internal integer representation of the inserted object.

We must also be able to test our objects for equality with the Eq typeclass. This is also technically a requirement for normal sets, but it is already a dependency of Ord.

How do I create a Hash Set?

Hash sets have the same 3 primary functions as normal sets.

empty :: HashSet a
singleton :: a -> HashSet  a
fromList :: [a] -> HashSet a

How do I get the size of a Hash Set?

Use Data.HashSet.size. This operation takes O(1) time.

size :: HashSet a -> Int

How do I add elements to a Hash Set?

As expected, we have an insert function.

insert :: a -> HashSet a -> HashSet a

How do I access Hash Set elements?

We can determine membership with the member function. However, the hash set API does not include notMember, as we saw with normal sets. And as we mentioned before, the lookup functions are not there either.

member :: a -> HashSet a -> Bool

How do I delete elements from a Hash Set?

As with normal sets, hash sets have a delete function.

delete :: a -> HashSet a -> HashSet a

How do I combine Hash Sets?

Hash sets have the same combination functions as normal sets, except that the module lacks an operator for the difference function.

union :: HashSet a -> HashSet a -> HashSet a
unions :: [HashSet a] -> HashSet a
intersection :: HashSet a -> HashSet a -> HashSet a
difference :: HashSet a -> HashSet a -> HashSet a

Import Notes

Hash sets have no operators, so the only unqualified name we ought to use is the type name itself.

import Data.HashSet (HashSet)
import qualified Data.HashSet as HS

Conclusion

If you want to learn about more data structures in Haskell, make sure to head back to the series page! The next structure to learn is the Hash Map!

For a more in depth look at this and other data structures, take a look at our eBooks page and look for the "In Depth" eBook!