Copyright	2011 Bryan O'Sullivan
License	BSD-style
Maintainer	johan.tibell@gmail.com
Stability	provisional
Portability	portable
Safe Haskell	Safe
Language	Haskell2010

Data.HashSet

Contents

Construction
Combine
Basic interface
Transformations
Difference and intersection
Folds
Filter
Conversions
- Lists
HashMaps

Description

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 \(O(\log n)\). The implementation uses a large base (i.e. 16) so in practice these operations are constant time.

Synopsis

data HashSet a
empty :: HashSet a
singleton :: Hashable a => a -> HashSet a
union :: Eq a => HashSet a -> HashSet a -> HashSet a
unions :: Eq a => [HashSet a] -> HashSet a
null :: HashSet a -> Bool
size :: HashSet a -> Int
member :: (Eq a, Hashable a) => a -> HashSet a -> Bool
insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a
delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a
isSubsetOf :: (Eq a, Hashable a) => HashSet a -> HashSet a -> Bool
map :: (Hashable b, Eq b) => (a -> b) -> HashSet a -> HashSet b
difference :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
intersection :: Eq a => HashSet a -> HashSet a -> HashSet a
foldl' :: (a -> b -> a) -> a -> HashSet b -> a
foldr :: (b -> a -> a) -> a -> HashSet b -> a
filter :: (a -> Bool) -> HashSet a -> HashSet a
toList :: HashSet a -> [a]
fromList :: (Eq a, Hashable a) => [a] -> HashSet a
toMap :: HashSet a -> HashMap a ()
fromMap :: HashMap a () -> HashSet a

Documentation

data HashSet a Source #

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

Instances

Instances details

Foldable HashSet Source #
Instance details Defined in Data.HashSet.Internal Methods fold :: Monoid m => HashSet m -> m # foldMap :: Monoid m => (a -> m) -> HashSet a -> m # foldMap' :: Monoid m => (a -> m) -> HashSet a -> m # foldr :: (a -> b -> b) -> b -> HashSet a -> b # foldr' :: (a -> b -> b) -> b -> HashSet a -> b # foldl :: (b -> a -> b) -> b -> HashSet a -> b # foldl' :: (b -> a -> b) -> b -> HashSet a -> b # foldr1 :: (a -> a -> a) -> HashSet a -> a # foldl1 :: (a -> a -> a) -> HashSet a -> a # toList :: HashSet a -> [a] # null :: HashSet a -> Bool # length :: HashSet a -> Int # elem :: Eq a => a -> HashSet a -> Bool # maximum :: Ord a => HashSet a -> a # minimum :: Ord a => HashSet a -> a # sum :: Num a => HashSet a -> a # product :: Num a => HashSet a -> a #
Eq1 HashSet Source #
Instance details Defined in Data.HashSet.Internal Methods liftEq :: (a -> b -> Bool) -> HashSet a -> HashSet b -> Bool #
Ord1 HashSet Source #
Instance details Defined in Data.HashSet.Internal Methods liftCompare :: (a -> b -> Ordering) -> HashSet a -> HashSet b -> Ordering #
Show1 HashSet Source #
Instance details Defined in Data.HashSet.Internal Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> HashSet a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [HashSet a] -> ShowS #
NFData1 HashSet Source #	Since: 0.2.14.0
Instance details Defined in Data.HashSet.Internal Methods liftRnf :: (a -> ()) -> HashSet a -> () #
Hashable1 HashSet Source #
Instance details Defined in Data.HashSet.Internal Methods liftHashWithSalt :: (Int -> a -> Int) -> Int -> HashSet a -> Int #
Lift a => Lift (HashSet a :: Type) Source #	Since: 0.2.17.0
Instance details Defined in Data.HashSet.Internal Methods lift :: Quote m => HashSet a -> m Exp # liftTyped :: forall (m :: Type -> Type). Quote m => HashSet a -> Code m (HashSet a) #
(Data a, Eq a, Hashable a) => Data (HashSet a) Source #
Instance details Defined in Data.HashSet.Internal Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> HashSet a -> c (HashSet a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (HashSet a) # toConstr :: HashSet a -> Constr # dataTypeOf :: HashSet a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (HashSet a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (HashSet a)) # gmapT :: (forall b. Data b => b -> b) -> HashSet a -> HashSet a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> HashSet a -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> HashSet a -> r # gmapQ :: (forall d. Data d => d -> u) -> HashSet a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> HashSet a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> HashSet a -> m (HashSet a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> HashSet a -> m (HashSet a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> HashSet a -> m (HashSet a) #
(Hashable a, Eq a) => Monoid (HashSet a) Source #	`mempty` = `empty` `mappend` = `union` \(O(n+m)\) To obtain good performance, the smaller set must be presented as the first argument. Examples Expand `>>>` `mappend (fromList [1,2]) (fromList [2,3])`fromList [1,2,3]
Instance details Defined in Data.HashSet.Internal Methods mempty :: HashSet a # mappend :: HashSet a -> HashSet a -> HashSet a # mconcat :: [HashSet a] -> HashSet a #
(Hashable a, Eq a) => Semigroup (HashSet a) Source #	`<>` = `union` \(O(n+m)\) To obtain good performance, the smaller set must be presented as the first argument. Examples Expand `>>>` `fromList [1,2] <> fromList [2,3]`fromList [1,2,3]
Instance details Defined in Data.HashSet.Internal Methods (<>) :: HashSet a -> HashSet a -> HashSet a # sconcat :: NonEmpty (HashSet a) -> HashSet a # stimes :: Integral b => b -> HashSet a -> HashSet a #
(Eq a, Hashable a) => IsList (HashSet a) Source #
Instance details Defined in Data.HashSet.Internal Associated Types type Item (HashSet a) # Methods fromList :: [Item (HashSet a)] -> HashSet a # fromListN :: Int -> [Item (HashSet a)] -> HashSet a # toList :: HashSet a -> [Item (HashSet a)] #
(Eq a, Hashable a, Read a) => Read (HashSet a) Source #
Instance details Defined in Data.HashSet.Internal Methods readsPrec :: Int -> ReadS (HashSet a) # readList :: ReadS [HashSet a] # readPrec :: ReadPrec (HashSet a) # readListPrec :: ReadPrec [HashSet a] #
Show a => Show (HashSet a) Source #
Instance details Defined in Data.HashSet.Internal Methods showsPrec :: Int -> HashSet a -> ShowS # show :: HashSet a -> String # showList :: [HashSet a] -> ShowS #
NFData a => NFData (HashSet a) Source #
Instance details Defined in Data.HashSet.Internal Methods rnf :: HashSet a -> () #
Eq a => Eq (HashSet a) Source #	Note that, in the presence of hash collisions, equal `HashSet`s may behave differently, i.e. extensionality may be violated: `>>>` `data D = A \| B deriving (Eq, Show)``>>>` `instance Hashable D where hashWithSalt salt _d = salt` `>>>` `x = fromList [A, B]``>>>` `y = fromList [B, A]` `>>>` `x == y`True `>>>` `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.
Instance details Defined in Data.HashSet.Internal Methods (==) :: HashSet a -> HashSet a -> Bool # (/=) :: HashSet a -> HashSet a -> Bool #
Ord a => Ord (HashSet a) Source #
Instance details Defined in Data.HashSet.Internal Methods compare :: HashSet a -> HashSet a -> Ordering # (<) :: HashSet a -> HashSet a -> Bool # (<=) :: HashSet a -> HashSet a -> Bool # (>) :: HashSet a -> HashSet a -> Bool # (>=) :: HashSet a -> HashSet a -> Bool # max :: HashSet a -> HashSet a -> HashSet a # min :: HashSet a -> HashSet a -> HashSet a #
Hashable a => Hashable (HashSet a) Source #
Instance details Defined in Data.HashSet.Internal Methods hashWithSalt :: Int -> HashSet a -> Int # hash :: HashSet a -> Int #
type Item (HashSet a) Source #
Instance details Defined in Data.HashSet.Internal type Item (HashSet a) = a

Construction

empty :: HashSet a Source #

\(O(1)\) Construct an empty set.

>>> HashSet.empty
fromList []

singleton :: Hashable a => a -> HashSet a Source #

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

>>> HashSet.singleton 1
fromList [1]

Combine

union :: Eq a => HashSet a -> HashSet a -> HashSet a Source #

\(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]

unions :: Eq a => [HashSet a] -> HashSet a Source #

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

Basic interface

null :: HashSet a -> Bool Source #

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

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

size :: HashSet a -> Int Source #

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

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

member :: (Eq a, Hashable a) => a -> HashSet a -> Bool Source #

\(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

insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a Source #

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

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

delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a Source #

\(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]

isSubsetOf :: (Eq a, Hashable a) => HashSet a -> HashSet a -> Bool Source #

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

Examples

Expand

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

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

Since: 0.2.12

Transformations

map :: (Hashable b, Eq b) => (a -> b) -> HashSet a -> HashSet b Source #

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

Difference and intersection

difference :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a Source #

\(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]

intersection :: Eq a => HashSet a -> HashSet a -> HashSet a Source #

\(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]

Folds

foldl' :: (a -> b -> a) -> a -> HashSet b -> a Source #

\(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.

foldr :: (b -> a -> a) -> a -> HashSet b -> a Source #

\(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

filter :: (a -> Bool) -> HashSet a -> HashSet a Source #

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

Conversions

Lists

toList :: HashSet a -> [a] Source #

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

fromList :: (Eq a, Hashable a) => [a] -> HashSet a Source #

\(O(n \min(W, n))\) Construct a set from a list of elements.

HashMaps

toMap :: HashSet a -> HashMap a () Source #

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

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

fromMap :: HashMap a () -> HashSet a Source #

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

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