Document the Semigroup for Map
[packages/containers.git] / docs / map.rst
1 Maps
2 ====
3
4 .. highlight:: haskell
5
6 Maps (sometimes referred to as dictionaries in other languages) allow you to
7 store associations between *unique keys* and *values*. There are three
8 implementations provided by the ``containers`` package:
9 :haddock:`/Data.Map.Strict`, :haddock:`/Data.Map.Lazy`, and
10 :haddock:`/Data.IntMap`. You almost never want the lazy version so use
11 ``Data.Map.Strict``, or if your keys are ``Int`` use ``Data.IntMap``.
12
13 ::
14
15     data Map k v = ...
16
17     data IntMap v = ...
18
19 .. IMPORTANT::
20    ``Map`` relies on the key type ``k`` having instances of the ``Eq`` and
21    ``Ord`` typeclass for its internal representation. These are already defined
22    for builtin types, and if you are using your own data type you can use the
23    `deriving
24    <https://en.wikibooks.org/wiki/Haskell/Classes_and_types#Deriving>`_
25    mechanism.
26
27 All of these implementations are *immutable* which means that any update
28 functions do not modify the map that you passed in, they creates a new map. In
29 order to keep the changes you need to assign it to a new variable. For example::
30
31     let m1 = Map.fromList [("a", 1), ("b", 2)]
32     let m2 = Map.delete "a" m1
33     print m1
34     > fromList [("a",1),("b",2)]
35     print m2
36     > fromList [("b",2)]
37
38
39 Short Example
40 -------------
41
42 The following GHCi session shows some of the basic map functionality::
43
44     import qualified Data.Map.Strict as Map
45
46     let nums = Map.fromList [(1,"one"), (2,"two"), (3,"three")]
47
48     -- Get the English word for the number 3 and 4.
49     Map.lookup 3 nums
50     > Just "three"
51
52     Map.lookup 4 nums
53     > Nothing
54
55
56     -- Add (4, "four") to our original map.
57     let moreNums = Map.insert 4 "four" nums
58
59     Map.member 4 moreNums
60     > True
61
62
63     -- Remove the entry for 1 from our original map.
64     let fewerNums = Map.delete 1 nums
65
66     Map.toAscList fewerNums
67     > [(2,"two"),(3,"three")]
68
69
70     -- Create a new map and combine it with our original map.
71     -- fromList is right-biased: if a key is repeated the rightmost value is taken.
72     let newNums = Map.fromList [(3,"new three"), (4,"new four"), (4,"newer four")]
73
74     -- union is left-biased: if a key occurs more than once the value from the
75     -- left map is taken.
76     Map.union newNums nums
77     > fromList [(1,"one"),(2,"two"),(3,"new three"),(4,"newer four")]
78
79 .. TIP:: You can use the `OverloadedLists
80          <https://ghc.haskell.org/trac/ghc/wiki/OverloadedLists>`_ extension so
81          you don't need to write ``fromList [1, 2, 3]`` everywhere; instead you
82          can just write ``[1, 2, 3]`` and if the function is expecting a map it
83          will be converted automatically! The code here will continue to use
84          ``fromList`` for clarity though.
85
86
87 Importing Map and IntMap
88 ------------------------
89
90 When using ``Map`` or ``IntMap`` in a Haskell source file you should always use
91 a ``qualified`` import because these modules export names that clash with the
92 standard Prelude (you can import the type constructor on its own though!). You
93 should also import ``Prelude`` and hide ``lookup`` because if you accidentally
94 leave off the ``Map.`` qualifier you'll get confusing type errors. You can
95 always import any specific identifiers you want unqualified. Most of the time,
96 that will include the type constructor (``Map``).
97
98 ::
99
100     import Prelude hiding (lookup)
101
102     import Data.Map.Strict (Map)
103     import qualified Data.Map.Strict as Map
104
105     import Data.IntMap (IntMap)
106     import qualified Data.IntMap.Strict as IntMap
107
108
109 Common API Functions
110 --------------------
111
112 .. TIP::
113    All of these functions that work for ``Map`` will also work for ``IntMap``,
114    which has the key type ``k`` specialized to ``Int``. Anywhere that you
115    see ``Map Int v`` you can replace it with ``IntMap v``. This will speed up
116    most operations tremendously (see `Performance`_) with the exception of
117    ``size`` which is O(1) for ``Map`` and O(n) for ``IntMap``.
118
119 .. NOTE::
120    A ``Map`` is printed as an association list preceeded by ``fromList``. For
121    example, it might look like ``fromList [(Key1,True),(Key2,False)]``.
122
123
124 Construction and Conversion
125 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
126
127 Create an empty map
128 """""""""""""""""""
129
130 ::
131
132     Map.empty :: Map k v
133     Map.empty = ...
134
135 :haddock_short:`/Data.Map.Strict#empty` creates a map without any entries.
136
137 ::
138
139     Map.empty
140     > fromList []
141
142 Create a map with one entry (singleton)
143 """""""""""""""""""""""""""""""""""""""
144
145 ::
146
147     Map.singleton :: k -> v -> Map k v
148     Map.singleton key value = ...
149
150 :haddock_short:`/Data.Map.Strict#singleton` creates a map with a single
151 ``(key,value)`` entry in it.
152
153 ::
154
155     Map.singleton 1 "one"
156     > fromList [(1,"one")]
157
158     Map.singleton "containers" ["base"]
159     > fromList [("containers",["base"])]
160
161 Create a map from a list
162 """"""""""""""""""""""""
163
164 ::
165
166     Map.fromList :: Ord k => [(k, v)] -> Map k v
167     Map.fromList xs = ...
168
169 :haddock_short:`/Data.Map.Strict#fromList` creates a map containing the entries
170 of the list ``xs`` where the keys comes from the first entries of the pairs and
171 the values from the second. If the same key appears more than once then the last
172 value is taken.
173
174 ::
175
176     Map.fromList []
177     > fromList []
178
179     Map.fromList [(1,"uno"), (1,"one"), (2,"two"), (3,"three")]
180     > fromList [(1,"one"),(2,"two"),(3,"three")]
181
182 There's another incredibly useful function for constructing a map from a list::
183
184     Map.fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map.Map k a
185     Map.fromListWith f xs = ...
186
187 :haddock_short:`/Data.Map.Strict#fromListWith` allows you to build a map from a
188 list ``xs`` with repeated keys, where ``f`` is used to "combine" (or "choose")
189 values with the same key.
190
191 ::
192
193     -- Build a map from a list, but only keep the largest value for each key.
194     Map.fromListWith max [("a", 2), ("a", 1), ("b", 2)]
195     > fromList [("a",2),("b",2)]
196
197     -- Build a histogram from a list of elements.
198     Map.fromListWith (+) (map (\x -> (x, 1)) ["a", "a", "b", "c", "c", "c"])
199     > fromList [("a",2),("b",1),("c",3)]
200
201     -- Build a map from a list, combining the string values for the same key.
202     Map.fromListWith (++) [(1, "a"), (1, "b"), (2, "x"), (2, "y")]
203     > fromList [(1,"ba"),(2,"yx")]
204
205
206
207 Create a list from a map
208 """"""""""""""""""""""""
209
210 ::
211
212     Map.toAscList, Map.toList, Map.assocs :: Map k v -> [(k, v)]
213     Map.toAscList m = ...
214
215 .. NOTE::
216    These all do the same thing; use ``toAscList`` because its name indicates
217    the ordering.
218
219 .. NOTE::
220    ``Map.toList`` is **not** the same as ``Foldable.toList``; the latter is
221    equivalent to ``elems``, although is rarely useful for maps. In general, use
222    ``toAscList``.
223
224 :haddock_short:`/Data.Map.Strict#toAscList`,
225 :haddock_short:`/Data.Map.Strict#toList`, and
226 :haddock_short:`/Data.Map.Strict#assocs` returns a list containing the (key,
227 value) pairs in the map ``m`` in *ascending* key order.
228
229 ::
230
231     Map.toDescList :: Map k v -> [(k, v)]
232     Map.toDescList m = ...
233
234 :haddock_short:`/Data.Map.Strict#toDescList` returns a list containing the (key,
235 value) pairs in the map ``m`` in *descending* key order.
236
237 ::
238
239     Map.toAscList (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
240     > [(1,"one"),(2,"two"),(3,"three")]
241
242     Map.toDescList (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
243     > [(3,"three"),(2,"two"),(1,"one")]
244
245
246 Querying
247 ^^^^^^^^
248
249 Lookup an entry in the map (lookup)
250 """""""""""""""""""""""""""""""""""
251
252 ::
253
254     Map.lookup :: Ord k => k -> Map k v -> Maybe v
255     Map.lookup key m = ...
256
257     Map.!? :: Ord k => Map k v -> k -> Maybe v
258     Map.!? m key = ...
259
260 :haddock_short:`/Data.Map.Strict#lookup` the value corresponding to the given
261 ``key``, returns ``Nothing`` if the key is not present; the ``!?`` operator
262 (*since 0.5.10*) is a flipped version of ``lookup`` and can often be imported
263 unqualified.
264
265
266 If you want to provide a default value if the key doesn't exist you can do:
267
268 ::
269
270     import Data.Maybe (fromMaybe)
271
272     -- fromMaybe :: a -> Maybe a -> a
273     fromMaybe defaultValue (lookup k m)
274
275 For example::
276
277     import Data.Map.Strict ((!?))
278     import Data.Maybe (fromMaybe)
279
280     Map.lookup 1 Map.empty
281     > Nothing
282
283     Map.lookup 1 (Map.fromList [(1,"one"),(2,"two"),(3,"three")])
284     > Just "one"
285
286     > (Map.fromList [(1,"one"),(2,"two"),(3,"three")]) !? 1
287     > Just "one"
288
289     fromMaybe "?" (Map.empty !? 1)
290     > "?"
291
292     fromMaybe "?" (Map.fromList [(1,"one"), (2,"two"), (3,"three")] !? 1)
293     > "one"
294
295 .. WARNING::
296    **DO NOT** Use ``Map.!``. It is partial and throws a runtime error if the key
297    doesn't exist.
298
299 Check if a map is empty
300 """""""""""""""""""""""
301
302 ::
303
304     Map.null :: Map k v -> Bool
305     Map.null m = ...
306
307 :haddock_short:`/Data.Map.Strict#null` returns ``True`` if the map ``m`` is
308 empty and ``False`` otherwise.
309
310 ::
311
312     Map.null Map.empty
313     > True
314
315     Map.null (Map.fromList [(1,"one")])
316     > False
317
318 The number of entries in a map
319 """"""""""""""""""""""""""""""
320
321 ::
322
323     Map.size :: Map k v -> Int
324     Map.size m = ...
325
326 :haddock_short:`/Data.Map.Strict#size` returns the number of entries in the map
327 ``m``.
328
329 ::
330
331     Map.size Map.empty
332     > 0
333
334     Map.size (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
335     > 3
336
337 Find the minimum/maximum
338 """"""""""""""""""""""""
339
340 *Since version 0.5.9*
341
342 ::
343
344     Map.lookupMin, Map.lookupMax :: Map k v -> Maybe (k, v)
345     Map.lookupMin m = ...
346     Map.lookupMax m = ...
347
348 :haddock_short:`/Data.Map.Strict#lookupMin` and
349 :haddock_short:`/Data.Map.Strict#lookupMax` respectively return the
350 minimum or maximum element of the map ``m``, or ``Nothing`` if the map is empty.
351
352 ::
353
354     Map.lookupMin Map.empty
355     > Nothing
356
357     Map.lookupMin (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
358     > Just (1,"one")
359
360     Map.lookupMax (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
361     > Just (3,"three")
362
363 .. WARNING::
364    **DO NOT** use ``Map.findMin`` or ``Map.findMax``. They are partial and throw
365    a runtime error if the map is empty.
366
367 Modification
368 ^^^^^^^^^^^^
369
370 Adding a new entry to a map
371 """""""""""""""""""""""""""
372
373 ::
374
375     Map.insert :: Ord k => k -> v -> Map k v -> Map k v
376     Map.insert key value m = ...
377
378 :haddock_short:`/Data.Map.Strict#insert` adds the ``value`` into the map ``m``
379 with the given ``key``, replacing the existing value if the key already exists.
380
381 ::
382
383     Map.insert 1 "one" Map.empty
384     > Map.fromList [(1,"one")]
385
386     Map.insert 4 "four" (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
387     > fromList [(1,"one"),(2,"two"),(3,"three"),(4,"four")]
388
389     Map.insert 1 "uno" (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
390     > fromList [(1,"uno"),(2,"two"),(3,"three")]
391
392
393 Removing an entry from a map
394 """"""""""""""""""""""""""""
395
396 ::
397
398     Map.delete :: Ord k => k -> Map k v -> Map k v
399     Map.delete key m = ...
400
401 :haddock_short:`/Data.Map.Strict#delete` removes the entry with the specified
402 ``key`` from the map ``m``.  If the key doesn't exist it leaves the map
403 unchanged.
404
405 ::
406
407     Map.delete 1 Map.empty
408     > Map.empty
409
410     Map.delete 1 (Map.fromList [(1,"one"),(2,"two"),(3,"three")])
411     > fromList [(2,"two"),(3,"three")]
412
413 Filtering map entries
414 """""""""""""""""""""
415
416 ::
417
418     Map.filterWithKey :: (k -> v -> Bool) -> Map k v -> Map k v
419     Map.filterWithKey predicate m = ...
420
421 :haddock_short:`/Data.Map.Strict#filterWithKey` produces a map consisting of all
422 entries of ``m`` for which the ``predicate`` returns ``True``.
423
424 ::
425
426     let f key value = key == 2 || value == "one"
427     Map.filterWithKey f (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
428     > fromList [(1,"one"),(2,"two"]
429
430
431 Modifying a map entry
432 """""""""""""""""""""
433
434 ::
435
436     Map.adjust :: Ord k => (v -> v) -> k -> Map k v -> Map k v
437     Map.adjust f key m = ...
438
439 :haddock_short:`/Data.Map.Strict#adjust` applies the value transformation
440 function ``f`` to the entry with given ``key``. If no entry for that key exists
441 then the map is left unchanged.
442
443 ::
444
445     Map.alter :: Ord k => (Maybe v -> Maybe v) -> k -> Map k v -> Map k v
446     Map.alter f key m = ...
447
448 Apply the value transformation function ``f`` to the entry with given ``key``,
449 if no entry for that key exists then the function is passed ``Nothing``. If the
450 function returns ``Nothing`` then the entry is deleted, if the function returns
451 ``Just v2`` then the value for the ``key`` is updated to ``v2``. In other words,
452 alter can be used to insert, update, or delete a value.
453
454 ::
455
456     import Data.Maybe (isJust)
457     let addValueIfMissing mv = if isJust mv then mv else (Just 1)
458     Map.alter addValueIfMissing "key" (Map.fromList [("key", 0)])
459     > fromList [("key",0)]
460
461     let addValueIfMissing mv = if isJust mv then mv else (Just 1)
462     Map.alter addValueIfMissing "new_key" (Map.fromList [("key", 0)])
463     > fromList [("key",0),("new_key",1)]
464
465 The function ``doubleIfPositive`` below will need to be placed in a Haskell
466 source file.
467
468 ::
469
470     doubleIfPositive :: Maybe Int -> Maybe Int
471     doubleIfPositive mv = case mv of
472       -- Do nothing if the key doesn't exist.
473       Nothing -> Nothing
474
475       -- If the key does exist, double the value if it is positive.
476       Just v -> if v > 0 then (Just v*2) else (Just v)
477
478     -- In GHCi
479     Map.alter doubleIfPositive "a" (Map.fromList [("a", 1), ("b", -1)])
480     > Map.fromList [("a",2), ("b",-1)]
481
482     Map.alter doubleIfPositive "b" (Map.fromList [("a", 1), ("b", -1)])
483     > Map.fromList [("a", 1), ("b",-1)]
484
485 Modifying all map entries (mapping and traversing)
486 """"""""""""""""""""""""""""""""""""""""""""""""""
487
488 ::
489
490     Map.map :: (a -> b) -> Map k a -> Map k v
491     Map.map f m = ...
492
493     Map.mapWithKey :: (k -> a -> b) -> Map.Map k a -> Map.Map k b
494     Map.mapWithKey g m = ...
495
496
497 :haddock_short:`/Data.Map.Strict#map` creates a new map by applying the
498 transformation function ``f`` to each entries value. This is how `Functor
499 <https://wiki.haskell.org/Typeclassopedia#Functor>`_ is defined for maps.
500
501 :haddock_short:`/Data.Map.Strict#mapWithKey` does the same as ``map`` but gives
502 you access to the key in the transformation function ``g``.
503
504 ::
505
506     Map.map (*10) (Map.fromList [("haskell", 45), ("idris", 15)])
507     > fromList [("haskell",450),("idris",150)]
508
509     -- Use the Functor instance for Map.
510     (*10) <$> Map.fromList [("haskell", 45), ("idris", 15)]
511     > fromList [("haskell",450),("idris",150)]
512
513     let g key value = if key == "haskell" then (value * 1000) else value
514     Map.mapWithKey g (Map.fromList [("haskell", 45), ("idris", 15)])
515     > fromList [("haskell",45000),("idris",15)]
516
517
518 You can also apply a function which performs *actions* (such as printing) to
519 each entry in the map.
520
521 ::
522
523     Map.traverseWithKey :: Applicative t => (k -> a -> t b) -> Map.Map k a -> t (Map.Map k b)
524     Map.traverseWithKey f m = ...
525
526 :haddock_short:`/Data.Map.Strict#traverseWithKey` maps each element of the map
527 ``m`` to an *action* that produces a result of type ``b``. The actions are
528 performed and the values of the map are replaced with the results from the
529 function. You can think of this as a ``map`` with affects.
530
531 ::
532
533     -- | Ask the user how they want to schedule a bunch of tasks
534     -- that the boss has assigned certain priorities.
535     makeSchedule :: Map Task Priority -> IO (Map Task DateTime)
536     makeSchedule = traverseWithKey $ \task priority ->
537       do
538         putStrLn $ "The boss thinks " ++ show task ++
539                      " has priority " ++ show priority ++
540                      ". When do you want to do it?"
541         readLn
542
543
544
545 Set-like Operations
546 ^^^^^^^^^^^^^^^^^^^
547
548 .. _union:
549
550 Union
551 """""
552
553 ::
554
555     Map.unionWith :: Ord k => (v -> v -> v) -> Map k v -> Map k v -> Map k v
556     Map.unionWith f l r = ...
557
558 :haddock_short:`/Data.Map.Strict#union` returns a map containing all entries that
559 are keyed in either of the two maps. If the same key appears in both maps, the
560 value is determined by calling ``f`` passing in the left and right value (`set
561 union <https://en.wikipedia.org/wiki/Union_(set_theory)>`_).
562
563 ::
564
565
566     Map.unionWith (++) Map.empty (Map.fromList [(1,"x"),(2,"y")])
567     > fromList [(1,"x"),(2,"y")]
568
569     let f lv rv = lv
570     Map.unionWith f (Map.fromList [(1, "a")]) (Map.fromList [(1,"x"),(2,"y")])
571     > fromList [(1,"a"),(2,"y")]
572
573     Map.unionWith (++) (Map.fromList [(1, "a")]) (Map.fromList [(1,"x"),(2,"y")])
574     > fromList [(1,"ax"),(2,"y")]
575
576
577 Intersection
578 """"""""""""
579
580 ::
581
582     Map.intersectionWith :: Ord k => (v -> v -> v) -> Map k v -> Map k v -> Map k v
583     Map.intersectionWith f l r = ...
584
585 :haddock_short:`/Data.Map.Strict#intersection` returns a map containing all
586 entries that have a key in both maps ``l`` and ``r``. The value in the returned
587 map is determined by calling ``f`` on the values from the left and right map
588 (`set intersection <https://en.wikipedia.org/wiki/Intersection_(set_theory)>`_).
589
590 ::
591
592     Map.intersectionWith (++) Map.empty (Map.fromList [(1,"x"), (2,"y")])
593     > fromList []
594
595     Map.intersectionWith (++) (Map.fromList [(1, "a")]) (Map.fromList [(1,"x"),(2,"y")])
596     > fromList [(1,"ax")]
597
598
599
600 Difference
601 """"""""""
602
603 ::
604
605     Map.difference :: Ord k => Map k v -> Map k v -> Map k v
606     Map.difference l r = ...
607
608 :haddock_short:`/Data.Map.Strict#difference` returns a map containing all entries
609 that have a key in the ``l`` map but not the ``r`` map (`set difference/relative
610 complement
611 <https://en.wikipedia.org/wiki/Complement_(set_theory)#Relative_complement>`_).
612
613 ::
614
615     Map.difference (Map.fromList [(1,"one"), (2,"two"), (3,"three")]) Map.empty
616     > fromList [(1,"uno"),(2,"two"),(3,"three")]
617
618     Map.difference (Map.fromList[(1,"one"), (2,"two")]) (Map.fromList [(1,"uno")])
619     > fromList [(2,"two")]
620
621
622 Serialization
623 -------------
624
625 The best way to serialize and deserialize maps is to use one of the many
626 libraries which already support serializing maps. :haddock:`binary`,
627 :haddock:`cereal`, and :haddock:`store` are some common libraries that people
628 use.
629
630 .. TIP::
631    If you are writing custom serialization code use
632    :haddock_short:`/Data.Map.Strict#fromDistinctAscList` (see
633    `#405 <https://github.com/haskell/containers/issues/405>`_ for more info).
634
635
636 Performance
637 -----------
638
639 The API docs are annotated with the Big-*O* complexities of each of the map
640 operations. For benchmarks see the `haskell-perf/dictionaries
641 <https://github.com/haskell-perf/dictionaries>`_ page.
642
643
644 Looking for more?
645 -----------------
646
647 Didn't find what you're looking for? This tutorial only covered the most common
648 map functions, for a full list of functions see the
649 :haddock_short:`/Data.Map.Strict#Map` and
650 :haddock_short:`/Data.IntMap.Strict#IntMap` API documentation.