1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
{-# 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 or 32) 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 ()
|
