b45de041d5973a1090ce3f0c69243f816602c7df
[packages/containers.git] / docs / set.rst
1 Sets
2 ====
3
4 .. highlight:: haskell
5
6 Sets allow you to store *unique*, *ordered* elements, providing efficient
7 insertion, lookups, deletions, and set operations. There are two implementations
8 provided by the ``containers`` package: :haddock:`/Data.Set` and
9 :haddock:`/Data.IntSet`. Use ``IntSet`` if you are storing, well... ``Int`` s.
10
11 ::
12
13     data Set element = ...
14
15     data IntSet = ...
16
17 .. IMPORTANT::
18    ``Set`` relies on the `element` type having instances of the ``Eq`` and
19    ``Ord`` typeclass for its internal representation. These are already defined
20    for builtin types, and if you are using your own data type you can use the
21    `deriving
22    <https://en.wikibooks.org/wiki/Haskell/Classes_and_types#Deriving>`_
23    mechanism.
24
25
26 All of these implementations are *immutable* which means that any update
27 functions do not modify the set that you passed in, they creates a new set. In
28 order to keep the changes you need to assign it to a new variable. For example::
29
30     let s1 = Set.fromList ["a", "b"]
31     let s2 = Set.delete "a" s1
32     print s1
33     > fromList ["a","b"]
34     print s2
35     > fromList ["b"]
36
37
38 Short Example
39 -------------
40
41 The following GHCi session shows some of the basic set functionality::
42
43     import qualified Data.Set as Set
44
45     let dataStructures = Set.fromList ["Set", "Map", "Graph", "Sequence"]
46
47     -- Check if "Map" and "Trie" are in the set of data structures.
48     Set.member "Map" dataStructures
49     > True
50
51     Set.member "Trie" dataStructures
52     > False
53
54
55     -- Add "Trie" to our original set of data structures.
56     let moreDataStructures = Set.insert "Trie" dataStructures
57
58     Set.member "Trie" moreDataStructures
59     > True
60
61
62     -- Remove "Graph" from our original set of data structures.
63     let fewerDataStructures = Set.delete "Graph" dataStructures
64
65     Set.toAscList fewerDataStructures
66     > ["Map","Sequence","Set"]
67
68
69     -- Create a new set and combine it with our original set.
70     let unorderedDataStructures = Set.fromList ["HashSet", "HashMap"]
71
72     Set.union dataStructures unorderedDataStructures
73     > fromList ["Graph","HashMap","HashSet","Map","Sequence","Set"]
74
75
76 .. TIP:: You can use the `OverloadedLists
77          <https://ghc.haskell.org/trac/ghc/wiki/OverloadedLists>`_ extension so
78          you don't need to write ``fromList [1, 2, 3]`` everywhere. Instead you
79          can just write ``[1, 2, 3]`` and if the function is expecting a set it
80          will be converted automatically! The code here will continue to use
81          ``fromList`` for clarity though.
82
83
84 Importing Set and IntSet
85 ------------------------
86
87 When using ``Set`` or ``IntSet`` in a Haskell source file you should always use
88 a ``qualified`` import because these modules export names that clash with the
89 standard Prelude. You can import the type constructor and additional functions
90 that you care about unqualified.
91
92 ::
93
94     import Data.Set (Set, lookupMin, lookupMax)
95     import qualified Data.Set as Set
96
97     import Data.IntSet (IntSet)
98     import qualified Data.IntSet as IntSet
99
100
101 Common API Functions
102 --------------------
103
104 .. TIP::
105    All of these functions that work for ``Set`` will also work for ``IntSet``,
106    which has the element type ``a`` specialized to ``Int``. Anywhere that you
107    see ``Set Int`` you can replace it with ``IntSet``. This will speed up
108    most operations tremendously (see `Performance`_) with the exception of
109    ``size`` which is O(1) for ``Set`` and O(n) for ``IntSet``.
110
111 .. NOTE::
112    ``fromList [some,list,elements]`` is how a ``Set`` is printed.
113
114
115 Construction and Conversion
116 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
117
118 Create an empty set
119 """""""""""""""""""
120
121 ::
122
123     Set.empty :: Set a
124     Set.empty = ...
125
126 :haddock_short:`/Data.Set#empty` creates a set with zero elements.
127
128 ::
129
130     Set.empty
131     > fromList []
132
133 Create a set with one element (singleton)
134 """""""""""""""""""""""""""""""""""""""""
135
136 ::
137
138     Set.singleton :: a -> Set a
139     Set.singleton x = ...
140
141 :haddock_short:`/Data.Set#singleton` creates a set with a single element ``x`` in
142 it.
143
144 ::
145
146     Set.singleton "containers"
147     > fromList ["containers"]
148
149     Set.singleton 1
150     > fromList [1]
151
152 Create a set from a list
153 """"""""""""""""""""""""
154
155 ::
156
157     Set.fromList :: Ord a => [a] -> Set a
158     Set.fromList xs = ...
159
160 :haddock_short:`/Data.Set#fromList` creates a set containing the elements of the
161 list ``xs``. Since sets don't contain duplicates, if there are repeated elements
162 in the list they will only appear once.
163
164 ::
165
166     Set.fromList ["base", "containers", "QuickCheck"]
167     > fromList ["QuickCheck","base","containers"]
168
169     Set.fromList [1, 1, 2, 3, 4, 4, 5, 1]
170     > fromList [1,2,3,4,5]
171
172 Create a list from a set
173 """"""""""""""""""""""""
174
175 ::
176
177     Set.toAscList, Set.toList, Set.elems :: Set a -> [a]
178     Set.toAscList s = ...
179
180 :haddock_short:`/Data.Set#toAscList`, :haddock_short:`/Data.Set#toList`, and
181 :haddock_short:`/Data.Set#elems` return a list containing the elements of the set
182 :haddock_short:`/`s`` in *ascending* order.
183
184 .. NOTE::
185    These all do the same thing; use ``toAscList`` because its name indicates the
186    ordering.
187
188 ::
189
190     Set.toDescList :: Set a -> [a]
191     Set.toDescList s = ...
192
193 :haddock_short:`/Data.Set#toDescList` returns a list containing the elements of
194 the set ``s`` in *descending* order.
195
196 ::
197
198     Set.toAscList (Set.fromList [0, 2, 4, 6])
199     > [0,2,4,6]
200
201     Set.toDescList (Set.fromList [0, 2, 4, 6]
202     > [6,4,2,0]
203
204
205 Querying
206 ^^^^^^^^
207
208 Check if an element is in a set (member)
209 """"""""""""""""""""""""""""""""""""""""
210
211 ::
212
213     Set.member :: Ord a => a -> Set a -> Bool
214     Set.member x s = ...
215
216 :haddock_short:`/Data.Set#member` returns ``True`` if the element ``x`` is in the
217 set ``s``, ``False`` otherwise.
218
219 ::
220
221     Set.member 0 Set.empty
222     > False
223
224     Set.member 0 (Set.fromList [0, 2, 4, 6])
225     > True
226
227 Check if a set is empty
228 """""""""""""""""""""""
229
230 ::
231
232     Set.null :: Set a -> Bool
233     Set.null s = ...
234
235 :haddock_short:`/Data.Set#null` returns ``True`` if the set ``s`` is empty,
236 ``False`` otherwise.
237
238 ::
239
240     Set.null Set.empty
241     > True
242
243     Set.null (Set.fromList [0, 2, 4, 6])
244     > False
245
246
247 The number of elements in a set
248 """""""""""""""""""""""""""""""
249
250 ::
251
252     Set.size :: Set a -> Int
253     Set.size s = ...
254
255 :haddock_short:`/Data.Set#size` returns the number of elements in the set ``s``.
256
257 ::
258
259     Set.size Set.empty
260     > 0
261
262     Set.size (Set.fromList [0, 2, 4, 6])
263     > 4
264
265 Find the minimum/maximum element in a set
266 """""""""""""""""""""""""""""""""""""""""
267
268 *Since version 0.5.9*
269
270 ::
271
272    lookupMin, lookupMax :: Set a -> Maybe a
273    lookupMin s = ...
274    lookupMax s = ...
275
276 :haddock_short:`/Data.Set#lookupMin` returns the minimum, or maximum
277 respectively, element of the set ``s``, or ``Nothing`` if the set is empty.
278
279 ::
280
281     Set.lookupMin Set.empty
282     > Nothing
283
284     Set.lookupMin (Set.fromList [0, 2, 4, 6])
285     > Just 0
286
287     Set.lookupMax (Set.fromList [0, 2, 4, 6])
288     > Just 6
289
290 .. WARNING::
291    Unless you're using an old version of ``containers`` **DO NOT** use
292    ``Set.findMin`` or ``Set.findMax``. They are partial and throw a runtime
293    error if the set is empty.
294
295 Modification
296 ^^^^^^^^^^^^
297
298 Adding a new element to a set
299 """""""""""""""""""""""""""""
300
301 ::
302
303     Set.insert :: Ord a => a -> Set a -> Set a
304     Set.insert x s = ...
305
306 :haddock_short:`/Data.Set#insert` places the element ``x`` into the set ``s``,
307 replacing an existing equal element if it already exists.
308
309 ::
310
311     Set.insert 100 Set.empty
312     > fromList [100]
313
314     Set.insert 0 (Set.fromList [0, 2, 4, 6])
315     > fromList [0,2,4,6]
316
317 Removing an element from a set
318 """"""""""""""""""""""""""""""
319
320 ::
321
322     Set.delete :: Ord a => a -> Set a -> Set a
323     Set.delete x s = ...
324
325 :haddock_short:`/Data.Set#delete` the element ``x`` from the set ``s``. If it’s
326 not a member it leaves the set unchanged.
327
328 ::
329
330     Set.delete 0 (Set.fromList [0, 2, 4, 6])
331     > fromList [2,4,6]
332
333 Filtering elements from a set
334 """""""""""""""""""""""""""""
335
336 ::
337
338     Set.filter :: (a -> Bool) -> Set a -> Set a
339     Set.filter predicate s = ...
340
341 :haddock_short:`/Data.Set#filter` produces a set consisting of all elements of
342 ``s`` for which the `predicate`` returns ``True``.
343
344 ::
345
346     Set.filter (==0) (Set.fromList [0, 2, 4, 6])
347     > fromList [0]
348
349
350 Set Operations
351 ^^^^^^^^^^^^^^
352
353 Union
354 """""
355
356 ::
357
358     Set.union :: Ord a => Set a -> Set a -> Set a
359     Set.union l r = ...
360
361 :haddock_short:`/Data.Set#union` returns a set containing all elements that are
362 in either of the two sets ``l`` or ``r`` (`set union
363 <https://en.wikipedia.org/wiki/Union_(set_theory)>`_).
364
365 ::
366
367     Set.union Set.empty (Set.fromList [0, 2, 4, 6])
368     > fromList [0,2,4,6]
369
370     Set.union (Set.fromList [1, 3, 5, 7]) (Set.fromList [0, 2, 4, 6])
371     > fromList [0,1,2,3,4,5,6,7]
372
373 Intersection
374 """"""""""""
375
376 ::
377
378     Set.intersection :: Ord a => Set a -> Set a -> Set a
379     Set.intersection l r = ...
380
381 :haddock_short:`/Data.Set#intersection` returns a set the elements that are in
382 both sets ``l`` and ``r`` (`set intersection
383 <https://en.wikipedia.org/wiki/Intersection_(set_theory)>`_).
384
385 ::
386
387     Set.intersection Set.empty (Set.fromList [0, 2, 4, 6])
388     > fromList []
389
390     Set.intersection (Set.fromList [1, 3, 5, 7]) (Set.fromList [0, 2, 4, 6])
391     > fromList []
392
393     Set.intersection (Set.singleton 0) (Set.fromList [0, 2, 4, 6])
394     > fromList [0]
395
396 Difference
397 """"""""""
398
399 ::
400
401     Set.difference :: Ord a => Set a -> Set a -> Set a
402     Set.difference l r = ...
403
404 :haddock_short:`/Data.Set#difference` returns a set containing the elements that
405 are in the first set ``l`` but not the second set ``r`` (`set
406 difference/relative compliment
407 <https://en.wikipedia.org/wiki/Complement_(set_theory)#Relative_complement>`_).
408
409 ::
410
411     Set.difference (Set.fromList [0, 2, 4, 6]) Set.empty
412     > fromList [0,2,4,6]
413
414     Set.difference (Set.fromList [0, 2, 4, 6]) (Set.fromList [1, 3, 5, 7])
415     > fromList [0,2,4,6]
416
417     Set.difference (Set.fromList [0, 2, 4, 6]) (Set.singleton 0)
418     > fromList [2,4,6]
419
420 Subset
421 """"""
422
423 ::
424
425     Set.isSubsetOf :: Ord a => Set a -> Set a -> Bool
426     Set.isSubsetOf l r = ...
427
428 :haddock_short:`/Data.Set#isSubsetOf` returns ``True`` if all elements in the
429 first set ``l`` are also in the second set ``r`` (`subset
430 <https://en.wikipedia.org/wiki/Subset>`_).
431
432 .. NOTE::
433    We use `infix notation
434    <https://wiki.haskell.org/Infix_operator#Using_infix_functions_with_prefix_notation>`_
435    so that it reads nicer. These are back-ticks (`), not single quotes (').
436
437 ::
438
439     Set.empty `Set.isSubsetOf` Set.empty
440     > True
441
442     Set.empty `Set.isSubsetOf` (Set.fromList [0, 2, 4, 6])
443     > True
444
445     (Set.singleton 0) `Set.isSubsetOf` (Set.fromList [0, 2, 4, 6])
446     > True
447
448     (Set.singleton 1) `Set.isSubsetOf` (Set.fromList [0, 2, 4, 6])
449     > False
450
451
452 Serialization
453 -------------
454
455 The best way to serialize and deserialize sets is to use one of the many
456 libraries which already support serializing sets. :haddock:`binary`,
457 :haddock:`cereal`, and :haddock:`store` are some common libraries that people
458 use.
459
460 .. TIP::
461    If you are writing custom serialization code use
462    :haddock_short:`/Data.Set#fromDistinctAscList` (see
463    `#405 <https://github.com/haskell/containers/issues/405>`_ for more info).
464
465 Performance
466 -----------
467
468 The API docs are annotated with the Big-*O* complexities of each of the set
469 operations. For benchmarks see the `haskell-perf/sets
470 <https://github.com/haskell-perf/sets>`_ page.
471
472
473 Looking for more?
474 -----------------
475
476 Didn't find what you're looking for? This tutorial only covered the most common
477 set functions, for a full list of functions see the
478 :haddock_short:`/Data.Set#Set` and :haddock_short:`/Data.IntSet#IntSet` API
479 documentation.