{-# LANGUAGE CPP #-}
{-# LANGUAGE Safe #-}
------------------------------------------------------------------------
{-|
Module : Data.HashSet
Copyright : 2011 Bryan O'Sullivan
License : BSD-style
Maintainer : johan.tibell@gmail.com
Stability : provisional
Portability : portable
= 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.Int"s consider using "Data.IntSet" from the
<https://hackage.haskell.org/package/containers 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
'Data.Eq.Eq' and 'Data.Hashable.Hashable'. The @Hashable@ typeclass is defined in the
<https://hackage.haskell.org/package/hashable 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 'Data.Ord.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) so in practice these
operations are constant time.
-}
module Data.HashSet
(
HashSet
-- * Construction
, empty
, singleton
-- * Combine
, union
, unions
-- * Basic interface
, null
, size
, member
, insert
, delete
, isSubsetOf
-- * Transformations
, map
-- * Difference and intersection
, difference
, intersection
-- * Folds
, foldl'
, foldr
-- * Filter
, filter
-- * Conversions
-- ** Lists
, toList
, fromList
-- * HashMaps
, toMap
, fromMap
) where
import Data.HashSet.Internal
import Prelude ()