Ticket #1611: Data-Map.html

File Data-Map.html, 112.8 KB (added by guest, 7 years ago)

Data.Map haddock docs

Line 
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
2<!--Rendered using the Haskell Html Library v0.2-->
3<HTML
4><HEAD
5><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"
6><TITLE
7>Data.Map</TITLE
8>
9
10<style TYPE="text/css">
11/* -------- Global things --------- */
12
13BODY { 
14  background-color: #ffffff;
15  color: #000000;
16  font-family: sans-serif;
17  } 
18
19A:link    { color: #0000e0; text-decoration: none }
20A:visited { color: #0000a0; text-decoration: none }
21A:hover   { background-color: #e0e0ff; text-decoration: none }
22
23TABLE.vanilla {
24  width: 100%;
25  border-width: 0px;
26  /* I can't seem to specify cellspacing or cellpadding properly using CSS... */
27}
28
29TABLE.vanilla2 {
30  border-width: 0px;
31}
32
33/* <TT> font is a little too small in MSIE */
34TT  { font-size: 100%; }
35PRE { font-size: 100%; }
36
37LI P { margin: 0pt } 
38
39TD {
40  border-width: 0px;
41}
42
43TABLE.narrow {
44  border-width: 0px;
45}
46
47TD.s8  {  height: 8px;  }
48TD.s15 {  height: 15px; }
49
50SPAN.keyword { text-decoration: underline; }
51
52/* Resize the buttom image to match the text size */
53IMG.coll { width : 0.75em; height: 0.75em; margin-bottom: 0; margin-right: 0.5em }
54
55/* --------- Contents page ---------- */
56
57DIV.node {
58  padding-left: 3em;
59}
60
61DIV.cnode {
62  padding-left: 1.75em;
63}
64
65SPAN.pkg {
66  position: absolute;
67  left: 50em;
68}
69
70/* --------- Documentation elements ---------- */
71
72TD.children {
73  padding-left: 25px;
74  }
75
76TD.synopsis {
77  padding: 2px;
78  background-color: #f0f0f0;
79  font-family: monospace
80 }
81
82TD.decl { 
83  padding: 2px;
84  background-color: #f0f0f0; 
85  font-family: monospace;
86  vertical-align: top;
87  }
88
89TD.topdecl {
90  padding: 2px;
91  background-color: #f0f0f0;
92  font-family: monospace;
93  vertical-align: top;
94}
95
96TABLE.declbar {
97  border-spacing: 0px;
98 }
99
100TD.declname {
101  width: 100%;
102 }
103
104TD.declbut {
105  padding-left: 5px;
106  padding-right: 5px;
107  border-left-width: 1px;
108  border-left-color: #000099;
109  border-left-style: solid;
110  white-space: nowrap;
111  font-size: small;
112 }
113
114/*
115  arg is just like decl, except that wrapping is not allowed.  It is
116  used for function and constructor arguments which have a text box
117  to the right, where if wrapping is allowed the text box squashes up
118  the declaration by wrapping it.
119*/
120TD.arg { 
121  padding: 2px;
122  background-color: #f0f0f0; 
123  font-family: monospace;
124  vertical-align: top;
125  white-space: nowrap;
126  }
127
128TD.recfield { padding-left: 20px }
129
130TD.doc  { 
131  padding-top: 2px;
132  padding-left: 10px;
133  }
134
135TD.ndoc  { 
136  padding: 2px;
137  }
138
139TD.rdoc  { 
140  padding: 2px;
141  padding-left: 10px;
142  width: 100%;
143  }
144
145TD.body  { 
146  padding-left: 10px
147  }
148
149TD.pkg {
150  width: 100%;
151  padding-left: 10px
152}
153
154TD.indexentry {
155  vertical-align: top;
156  padding-right: 10px
157  }
158
159TD.indexannot {
160  vertical-align: top;
161  padding-left: 20px;
162  white-space: nowrap
163  }
164
165TD.indexlinks {
166  width: 100%
167  }
168
169/* ------- Section Headings ------- */
170
171TD.section1 {
172  padding-top: 15px;
173  font-weight: bold;
174  font-size: 150%
175  }
176
177TD.section2 {
178  padding-top: 10px;
179  font-weight: bold;
180  font-size: 130%
181  }
182
183TD.section3 {
184  padding-top: 5px;
185  font-weight: bold;
186  font-size: 110%
187  }
188
189TD.section4 {
190  font-weight: bold;
191  font-size: 100%
192  }
193
194/* -------------- The title bar at the top of the page */
195
196TD.infohead {
197  color: #ffffff;
198  font-weight: bold;
199  padding-right: 10px;
200  text-align: left;
201}
202
203TD.infoval {
204  color: #ffffff;
205  padding-right: 10px;
206  text-align: left;
207}
208
209TD.topbar {
210  background-color: #000099;
211  padding: 5px;
212}
213
214TD.title {
215  color: #ffffff;
216  padding-left: 10px;
217  width: 100%
218  }
219
220TD.topbut {
221  padding-left: 5px;
222  padding-right: 5px;
223  border-left-width: 1px;
224  border-left-color: #ffffff;
225  border-left-style: solid;
226  white-space: nowrap;
227  }
228
229TD.topbut A:link {
230  color: #ffffff
231  }
232
233TD.topbut A:visited {
234  color: #ffff00
235  }
236
237TD.topbut A:hover {
238  background-color: #6060ff;
239  }
240
241TD.topbut:hover {
242  background-color: #6060ff
243  }
244
245TD.modulebar { 
246  background-color: #0077dd;
247  padding: 5px;
248  border-top-width: 1px;
249  border-top-color: #ffffff;
250  border-top-style: solid;
251  }
252
253/* --------- The page footer --------- */
254
255TD.botbar {
256  background-color: #000099;
257  color: #ffffff;
258  padding: 5px
259  }
260TD.botbar A:link {
261  color: #ffffff;
262  text-decoration: underline
263  }
264TD.botbar A:visited {
265  color: #ffff00
266  }
267TD.botbar A:hover {
268  background-color: #6060ff
269  }
270</style>
271
272<SCRIPT SRC="haddock.js" TYPE="text/javascript"
273></SCRIPT
274></HEAD
275><BODY
276><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
277><TR
278><TD CLASS="topbar"
279><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
280><TR
281><TD
282><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "
283></TD
284><TD CLASS="title"
285></TD
286><TD CLASS="topbut"
287><A HREF="index.html"
288>Contents</A
289></TD
290><TD CLASS="topbut"
291><A HREF="doc-index.html"
292>Index</A
293></TD
294></TR
295></TABLE
296></TD
297></TR
298><TR
299><TD CLASS="modulebar"
300><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
301><TR
302><TD
303><FONT SIZE="6"
304>Data.Map</FONT
305></TD
306><TD ALIGN="right"
307><TABLE CLASS="narrow" CELLSPACING="0" CELLPADDING="0"
308><TR
309><TD CLASS="infohead"
310>Portability</TD
311><TD CLASS="infoval"
312>portable</TD
313></TR
314><TR
315><TD CLASS="infohead"
316>Stability</TD
317><TD CLASS="infoval"
318>provisional</TD
319></TR
320><TR
321><TD CLASS="infohead"
322>Maintainer</TD
323><TD CLASS="infoval"
324>[email protected]</TD
325></TR
326></TABLE
327></TD
328></TR
329></TABLE
330></TD
331></TR
332><TR
333><TD CLASS="s15"
334></TD
335></TR
336><TR
337><TD
338><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
339><TR
340><TD CLASS="section4"
341><B
342>Contents</B
343></TD
344></TR
345><TR
346><TD
347><DL
348><DT
349><A HREF="#1"
350>Map type
351</A
352></DT
353><DT
354><A HREF="#2"
355>Operators
356</A
357></DT
358><DT
359><A HREF="#3"
360>Query
361</A
362></DT
363><DT
364><A HREF="#4"
365>Construction
366</A
367></DT
368><DD
369><DL
370><DT
371><A HREF="#5"
372>Insertion
373</A
374></DT
375><DT
376><A HREF="#6"
377>Delete/Update
378</A
379></DT
380></DL
381></DD
382><DT
383><A HREF="#7"
384>Combine
385</A
386></DT
387><DD
388><DL
389><DT
390><A HREF="#8"
391>Union
392</A
393></DT
394><DT
395><A HREF="#9"
396>Difference
397</A
398></DT
399><DT
400><A HREF="#10"
401>Intersection
402</A
403></DT
404></DL
405></DD
406><DT
407><A HREF="#11"
408>Traversal
409</A
410></DT
411><DD
412><DL
413><DT
414><A HREF="#12"
415>Map
416</A
417></DT
418><DT
419><A HREF="#13"
420>Fold
421</A
422></DT
423></DL
424></DD
425><DT
426><A HREF="#14"
427>Conversion
428</A
429></DT
430><DD
431><DL
432><DT
433><A HREF="#15"
434>Lists
435</A
436></DT
437><DT
438><A HREF="#16"
439>Ordered lists
440</A
441></DT
442></DL
443></DD
444><DT
445><A HREF="#17"
446>Filter
447</A
448></DT
449><DT
450><A HREF="#18"
451>Submap
452</A
453></DT
454><DT
455><A HREF="#19"
456>Indexed
457</A
458></DT
459><DT
460><A HREF="#20"
461>Min/Max
462</A
463></DT
464><DT
465><A HREF="#21"
466>Debugging
467</A
468></DT
469></DL
470></TD
471></TR
472></TABLE
473></TD
474></TR
475><TR
476><TD CLASS="s15"
477></TD
478></TR
479><TR
480><TD CLASS="section1"
481>Description</TD
482></TR
483><TR
484><TD CLASS="doc"
485><P
486>An efficient implementation of maps from keys to values (dictionaries).
487</P
488><P
489>Since many function names (but not the type name) clash with
490 <A HREF="Prelude.html"
491>Prelude</A
492> names, this module is usually imported <TT
493>qualified</TT
494>, e.g.
495</P
496><PRE
497>  import Data.Map (Map)
498  import qualified Data.Map as Map
499</PRE
500><P
501>The implementation of <TT
502><A HREF="Data-Map.html#t%3AMap"
503>Map</A
504></TT
505> is based on <EM
506>size balanced</EM
507> binary trees (or
508 trees of <EM
509>bounded balance</EM
510>) as described by:
511</P
512><UL
513><LI
514> Stephen Adams, &quot;<EM
515>Efficient sets: a balancing act</EM
516>&quot;,
517        Journal of Functional Programming 3(4):553-562, October 1993,
518        <A HREF="http://www.swiss.ai.mit.edu/~adams/BB"
519>http://www.swiss.ai.mit.edu/~adams/BB</A
520>.
521</LI
522><LI
523> J. Nievergelt and E.M. Reingold,
524        &quot;<EM
525>Binary search trees of bounded balance</EM
526>&quot;,
527        SIAM journal of computing 2(1), March 1973.
528</LI
529></UL
530><P
531>Note that the implementation is <EM
532>left-biased</EM
533> -- the elements of a
534 first argument are always preferred to the second, for example in
535 <TT
536><A HREF="Data-Map.html#v%3Aunion"
537>union</A
538></TT
539> or <TT
540><A HREF="Data-Map.html#v%3Ainsert"
541>insert</A
542></TT
543>.
544</P
545><P
546>Operation comments contain the operation time complexity in
547 the Big-O notation <A HREF="http://en.wikipedia.org/wiki/Big_O_notation"
548>http://en.wikipedia.org/wiki/Big_O_notation</A
549>.
550</P
551></TD
552></TR
553><TR
554><TD CLASS="s15"
555></TD
556></TR
557><TR
558><TD CLASS="section1"
559>Synopsis</TD
560></TR
561><TR
562><TD CLASS="s15"
563></TD
564></TR
565><TR
566><TD CLASS="body"
567><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
568><TR
569><TD CLASS="decl"
570><SPAN CLASS="keyword"
571>data</SPAN
572> <A HREF="#t%3AMap"
573>Map</A
574> k a</TD
575></TR
576><TR
577><TD CLASS="s8"
578></TD
579></TR
580><TR
581><TD CLASS="decl"
582><A HREF="#v%3A%21"
583>(!)</A
584> :: <A HREF="Prelude.html#t%3AOrd"
585>Ord</A
586> k =&gt; <A HREF="Data-Map.html#t%3AMap"
587>Map</A
588> k a -&gt; k -&gt; a</TD
589></TR
590><TR
591><TD CLASS="s8"
592></TD
593></TR
594><TR
595><TD CLASS="decl"
596><A HREF="#v%3A%5C%5C"
597>(\\)</A
598> :: <A HREF="Prelude.html#t%3AOrd"
599>Ord</A
600> k =&gt; <A HREF="Data-Map.html#t%3AMap"
601>Map</A
602> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
603>Map</A
604> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
605>Map</A
606> k a</TD
607></TR
608><TR
609><TD CLASS="s8"
610></TD
611></TR
612><TR
613><TD CLASS="decl"
614><A HREF="#v%3Anull"
615>null</A
616> :: <A HREF="Data-Map.html#t%3AMap"
617>Map</A
618> k a -&gt; <A HREF="Prelude.html#t%3ABool"
619>Bool</A
620></TD
621></TR
622><TR
623><TD CLASS="s8"
624></TD
625></TR
626><TR
627><TD CLASS="decl"
628><A HREF="#v%3Asize"
629>size</A
630> :: <A HREF="Data-Map.html#t%3AMap"
631>Map</A
632> k a -&gt; <A HREF="Prelude.html#t%3AInt"
633>Int</A
634></TD
635></TR
636><TR
637><TD CLASS="s8"
638></TD
639></TR
640><TR
641><TD CLASS="decl"
642><A HREF="#v%3Amember"
643>member</A
644> :: <A HREF="Prelude.html#t%3AOrd"
645>Ord</A
646> k =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
647>Map</A
648> k a -&gt; <A HREF="Prelude.html#t%3ABool"
649>Bool</A
650></TD
651></TR
652><TR
653><TD CLASS="s8"
654></TD
655></TR
656><TR
657><TD CLASS="decl"
658><A HREF="#v%3AnotMember"
659>notMember</A
660> :: <A HREF="Prelude.html#t%3AOrd"
661>Ord</A
662> k =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
663>Map</A
664> k a -&gt; <A HREF="Prelude.html#t%3ABool"
665>Bool</A
666></TD
667></TR
668><TR
669><TD CLASS="s8"
670></TD
671></TR
672><TR
673><TD CLASS="decl"
674><A HREF="#v%3Alookup"
675>lookup</A
676> :: (<A HREF="Prelude.html#t%3AMonad"
677>Monad</A
678> m, <A HREF="Prelude.html#t%3AOrd"
679>Ord</A
680> k) =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
681>Map</A
682> k a -&gt; m a</TD
683></TR
684><TR
685><TD CLASS="s8"
686></TD
687></TR
688><TR
689><TD CLASS="decl"
690><A HREF="#v%3AfindWithDefault"
691>findWithDefault</A
692> :: <A HREF="Prelude.html#t%3AOrd"
693>Ord</A
694> k =&gt; a -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
695>Map</A
696> k a -&gt; a</TD
697></TR
698><TR
699><TD CLASS="s8"
700></TD
701></TR
702><TR
703><TD CLASS="decl"
704><A HREF="#v%3Aempty"
705>empty</A
706> :: <A HREF="Data-Map.html#t%3AMap"
707>Map</A
708> k a</TD
709></TR
710><TR
711><TD CLASS="s8"
712></TD
713></TR
714><TR
715><TD CLASS="decl"
716><A HREF="#v%3Asingleton"
717>singleton</A
718> :: k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
719>Map</A
720> k a</TD
721></TR
722><TR
723><TD CLASS="s8"
724></TD
725></TR
726><TR
727><TD CLASS="decl"
728><A HREF="#v%3Ainsert"
729>insert</A
730> :: <A HREF="Prelude.html#t%3AOrd"
731>Ord</A
732> k =&gt; k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
733>Map</A
734> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
735>Map</A
736> k a</TD
737></TR
738><TR
739><TD CLASS="s8"
740></TD
741></TR
742><TR
743><TD CLASS="decl"
744><A HREF="#v%3AinsertWith"
745>insertWith</A
746> :: <A HREF="Prelude.html#t%3AOrd"
747>Ord</A
748> k =&gt; (a -&gt; a -&gt; a) -&gt; k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
749>Map</A
750> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
751>Map</A
752> k a</TD
753></TR
754><TR
755><TD CLASS="s8"
756></TD
757></TR
758><TR
759><TD CLASS="decl"
760><A HREF="#v%3AinsertWithKey"
761>insertWithKey</A
762> :: <A HREF="Prelude.html#t%3AOrd"
763>Ord</A
764> k =&gt; (k -&gt; a -&gt; a -&gt; a) -&gt; k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
765>Map</A
766> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
767>Map</A
768> k a</TD
769></TR
770><TR
771><TD CLASS="s8"
772></TD
773></TR
774><TR
775><TD CLASS="decl"
776><A HREF="#v%3AinsertLookupWithKey"
777>insertLookupWithKey</A
778> :: <A HREF="Prelude.html#t%3AOrd"
779>Ord</A
780> k =&gt; (k -&gt; a -&gt; a -&gt; a) -&gt; k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
781>Map</A
782> k a -&gt; (<A HREF="Prelude.html#t%3AMaybe"
783>Maybe</A
784> a, <A HREF="Data-Map.html#t%3AMap"
785>Map</A
786> k a)</TD
787></TR
788><TR
789><TD CLASS="s8"
790></TD
791></TR
792><TR
793><TD CLASS="decl"
794><A HREF="#v%3AinsertWith%27"
795>insertWith'</A
796> :: <A HREF="Prelude.html#t%3AOrd"
797>Ord</A
798> k =&gt; (a -&gt; a -&gt; a) -&gt; k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
799>Map</A
800> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
801>Map</A
802> k a</TD
803></TR
804><TR
805><TD CLASS="s8"
806></TD
807></TR
808><TR
809><TD CLASS="decl"
810><A HREF="#v%3AinsertWithKey%27"
811>insertWithKey'</A
812> :: <A HREF="Prelude.html#t%3AOrd"
813>Ord</A
814> k =&gt; (k -&gt; a -&gt; a -&gt; a) -&gt; k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
815>Map</A
816> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
817>Map</A
818> k a</TD
819></TR
820><TR
821><TD CLASS="s8"
822></TD
823></TR
824><TR
825><TD CLASS="decl"
826><A HREF="#v%3Adelete"
827>delete</A
828> :: <A HREF="Prelude.html#t%3AOrd"
829>Ord</A
830> k =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
831>Map</A
832> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
833>Map</A
834> k a</TD
835></TR
836><TR
837><TD CLASS="s8"
838></TD
839></TR
840><TR
841><TD CLASS="decl"
842><A HREF="#v%3Aadjust"
843>adjust</A
844> :: <A HREF="Prelude.html#t%3AOrd"
845>Ord</A
846> k =&gt; (a -&gt; a) -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
847>Map</A
848> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
849>Map</A
850> k a</TD
851></TR
852><TR
853><TD CLASS="s8"
854></TD
855></TR
856><TR
857><TD CLASS="decl"
858><A HREF="#v%3AadjustWithKey"
859>adjustWithKey</A
860> :: <A HREF="Prelude.html#t%3AOrd"
861>Ord</A
862> k =&gt; (k -&gt; a -&gt; a) -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
863>Map</A
864> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
865>Map</A
866> k a</TD
867></TR
868><TR
869><TD CLASS="s8"
870></TD
871></TR
872><TR
873><TD CLASS="decl"
874><A HREF="#v%3Aupdate"
875>update</A
876> :: <A HREF="Prelude.html#t%3AOrd"
877>Ord</A
878> k =&gt; (a -&gt; <A HREF="Prelude.html#t%3AMaybe"
879>Maybe</A
880> a) -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
881>Map</A
882> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
883>Map</A
884> k a</TD
885></TR
886><TR
887><TD CLASS="s8"
888></TD
889></TR
890><TR
891><TD CLASS="decl"
892><A HREF="#v%3AupdateWithKey"
893>updateWithKey</A
894> :: <A HREF="Prelude.html#t%3AOrd"
895>Ord</A
896> k =&gt; (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
897>Maybe</A
898> a) -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
899>Map</A
900> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
901>Map</A
902> k a</TD
903></TR
904><TR
905><TD CLASS="s8"
906></TD
907></TR
908><TR
909><TD CLASS="decl"
910><A HREF="#v%3AupdateLookupWithKey"
911>updateLookupWithKey</A
912> :: <A HREF="Prelude.html#t%3AOrd"
913>Ord</A
914> k =&gt; (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
915>Maybe</A
916> a) -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
917>Map</A
918> k a -&gt; (<A HREF="Prelude.html#t%3AMaybe"
919>Maybe</A
920> a, <A HREF="Data-Map.html#t%3AMap"
921>Map</A
922> k a)</TD
923></TR
924><TR
925><TD CLASS="s8"
926></TD
927></TR
928><TR
929><TD CLASS="decl"
930><A HREF="#v%3Aalter"
931>alter</A
932> :: <A HREF="Prelude.html#t%3AOrd"
933>Ord</A
934> k =&gt; (<A HREF="Prelude.html#t%3AMaybe"
935>Maybe</A
936> a -&gt; <A HREF="Prelude.html#t%3AMaybe"
937>Maybe</A
938> a) -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
939>Map</A
940> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
941>Map</A
942> k a</TD
943></TR
944><TR
945><TD CLASS="s8"
946></TD
947></TR
948><TR
949><TD CLASS="decl"
950><A HREF="#v%3Aunion"
951>union</A
952> :: <A HREF="Prelude.html#t%3AOrd"
953>Ord</A
954> k =&gt; <A HREF="Data-Map.html#t%3AMap"
955>Map</A
956> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
957>Map</A
958> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
959>Map</A
960> k a</TD
961></TR
962><TR
963><TD CLASS="s8"
964></TD
965></TR
966><TR
967><TD CLASS="decl"
968><A HREF="#v%3AunionWith"
969>unionWith</A
970> :: <A HREF="Prelude.html#t%3AOrd"
971>Ord</A
972> k =&gt; (a -&gt; a -&gt; a) -&gt; <A HREF="Data-Map.html#t%3AMap"
973>Map</A
974> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
975>Map</A
976> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
977>Map</A
978> k a</TD
979></TR
980><TR
981><TD CLASS="s8"
982></TD
983></TR
984><TR
985><TD CLASS="decl"
986><A HREF="#v%3AunionWithKey"
987>unionWithKey</A
988> :: <A HREF="Prelude.html#t%3AOrd"
989>Ord</A
990> k =&gt; (k -&gt; a -&gt; a -&gt; a) -&gt; <A HREF="Data-Map.html#t%3AMap"
991>Map</A
992> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
993>Map</A
994> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
995>Map</A
996> k a</TD
997></TR
998><TR
999><TD CLASS="s8"
1000></TD
1001></TR
1002><TR
1003><TD CLASS="decl"
1004><A HREF="#v%3Aunions"
1005>unions</A
1006> :: <A HREF="Prelude.html#t%3AOrd"
1007>Ord</A
1008> k =&gt; [<A HREF="Data-Map.html#t%3AMap"
1009>Map</A
1010> k a] -&gt; <A HREF="Data-Map.html#t%3AMap"
1011>Map</A
1012> k a</TD
1013></TR
1014><TR
1015><TD CLASS="s8"
1016></TD
1017></TR
1018><TR
1019><TD CLASS="decl"
1020><A HREF="#v%3AunionsWith"
1021>unionsWith</A
1022> :: <A HREF="Prelude.html#t%3AOrd"
1023>Ord</A
1024> k =&gt; (a -&gt; a -&gt; a) -&gt; [<A HREF="Data-Map.html#t%3AMap"
1025>Map</A
1026> k a] -&gt; <A HREF="Data-Map.html#t%3AMap"
1027>Map</A
1028> k a</TD
1029></TR
1030><TR
1031><TD CLASS="s8"
1032></TD
1033></TR
1034><TR
1035><TD CLASS="decl"
1036><A HREF="#v%3Adifference"
1037>difference</A
1038> :: <A HREF="Prelude.html#t%3AOrd"
1039>Ord</A
1040> k =&gt; <A HREF="Data-Map.html#t%3AMap"
1041>Map</A
1042> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1043>Map</A
1044> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
1045>Map</A
1046> k a</TD
1047></TR
1048><TR
1049><TD CLASS="s8"
1050></TD
1051></TR
1052><TR
1053><TD CLASS="decl"
1054><A HREF="#v%3AdifferenceWith"
1055>differenceWith</A
1056> :: <A HREF="Prelude.html#t%3AOrd"
1057>Ord</A
1058> k =&gt; (a -&gt; b -&gt; <A HREF="Prelude.html#t%3AMaybe"
1059>Maybe</A
1060> a) -&gt; <A HREF="Data-Map.html#t%3AMap"
1061>Map</A
1062> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1063>Map</A
1064> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
1065>Map</A
1066> k a</TD
1067></TR
1068><TR
1069><TD CLASS="s8"
1070></TD
1071></TR
1072><TR
1073><TD CLASS="decl"
1074><A HREF="#v%3AdifferenceWithKey"
1075>differenceWithKey</A
1076> :: <A HREF="Prelude.html#t%3AOrd"
1077>Ord</A
1078> k =&gt; (k -&gt; a -&gt; b -&gt; <A HREF="Prelude.html#t%3AMaybe"
1079>Maybe</A
1080> a) -&gt; <A HREF="Data-Map.html#t%3AMap"
1081>Map</A
1082> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1083>Map</A
1084> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
1085>Map</A
1086> k a</TD
1087></TR
1088><TR
1089><TD CLASS="s8"
1090></TD
1091></TR
1092><TR
1093><TD CLASS="decl"
1094><A HREF="#v%3Aintersection"
1095>intersection</A
1096> :: <A HREF="Prelude.html#t%3AOrd"
1097>Ord</A
1098> k =&gt; <A HREF="Data-Map.html#t%3AMap"
1099>Map</A
1100> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1101>Map</A
1102> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
1103>Map</A
1104> k a</TD
1105></TR
1106><TR
1107><TD CLASS="s8"
1108></TD
1109></TR
1110><TR
1111><TD CLASS="decl"
1112><A HREF="#v%3AintersectionWith"
1113>intersectionWith</A
1114> :: <A HREF="Prelude.html#t%3AOrd"
1115>Ord</A
1116> k =&gt; (a -&gt; b -&gt; c) -&gt; <A HREF="Data-Map.html#t%3AMap"
1117>Map</A
1118> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1119>Map</A
1120> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
1121>Map</A
1122> k c</TD
1123></TR
1124><TR
1125><TD CLASS="s8"
1126></TD
1127></TR
1128><TR
1129><TD CLASS="decl"
1130><A HREF="#v%3AintersectionWithKey"
1131>intersectionWithKey</A
1132> :: <A HREF="Prelude.html#t%3AOrd"
1133>Ord</A
1134> k =&gt; (k -&gt; a -&gt; b -&gt; c) -&gt; <A HREF="Data-Map.html#t%3AMap"
1135>Map</A
1136> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1137>Map</A
1138> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
1139>Map</A
1140> k c</TD
1141></TR
1142><TR
1143><TD CLASS="s8"
1144></TD
1145></TR
1146><TR
1147><TD CLASS="decl"
1148><A HREF="#v%3Amap"
1149>map</A
1150> :: (a -&gt; b) -&gt; <A HREF="Data-Map.html#t%3AMap"
1151>Map</A
1152> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1153>Map</A
1154> k b</TD
1155></TR
1156><TR
1157><TD CLASS="s8"
1158></TD
1159></TR
1160><TR
1161><TD CLASS="decl"
1162><A HREF="#v%3AmapWithKey"
1163>mapWithKey</A
1164> :: (k -&gt; a -&gt; b) -&gt; <A HREF="Data-Map.html#t%3AMap"
1165>Map</A
1166> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1167>Map</A
1168> k b</TD
1169></TR
1170><TR
1171><TD CLASS="s8"
1172></TD
1173></TR
1174><TR
1175><TD CLASS="decl"
1176><A HREF="#v%3AmapAccum"
1177>mapAccum</A
1178> :: (a -&gt; b -&gt; (a, c)) -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
1179>Map</A
1180> k b -&gt; (a, <A HREF="Data-Map.html#t%3AMap"
1181>Map</A
1182> k c)</TD
1183></TR
1184><TR
1185><TD CLASS="s8"
1186></TD
1187></TR
1188><TR
1189><TD CLASS="decl"
1190><A HREF="#v%3AmapAccumWithKey"
1191>mapAccumWithKey</A
1192> :: (a -&gt; k -&gt; b -&gt; (a, c)) -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
1193>Map</A
1194> k b -&gt; (a, <A HREF="Data-Map.html#t%3AMap"
1195>Map</A
1196> k c)</TD
1197></TR
1198><TR
1199><TD CLASS="s8"
1200></TD
1201></TR
1202><TR
1203><TD CLASS="decl"
1204><A HREF="#v%3AmapKeys"
1205>mapKeys</A
1206> :: <A HREF="Prelude.html#t%3AOrd"
1207>Ord</A
1208> k2 =&gt; (k1 -&gt; k2) -&gt; <A HREF="Data-Map.html#t%3AMap"
1209>Map</A
1210> k1 a -&gt; <A HREF="Data-Map.html#t%3AMap"
1211>Map</A
1212> k2 a</TD
1213></TR
1214><TR
1215><TD CLASS="s8"
1216></TD
1217></TR
1218><TR
1219><TD CLASS="decl"
1220><A HREF="#v%3AmapKeysWith"
1221>mapKeysWith</A
1222> :: <A HREF="Prelude.html#t%3AOrd"
1223>Ord</A
1224> k2 =&gt; (a -&gt; a -&gt; a) -&gt; (k1 -&gt; k2) -&gt; <A HREF="Data-Map.html#t%3AMap"
1225>Map</A
1226> k1 a -&gt; <A HREF="Data-Map.html#t%3AMap"
1227>Map</A
1228> k2 a</TD
1229></TR
1230><TR
1231><TD CLASS="s8"
1232></TD
1233></TR
1234><TR
1235><TD CLASS="decl"
1236><A HREF="#v%3AmapKeysMonotonic"
1237>mapKeysMonotonic</A
1238> :: (k1 -&gt; k2) -&gt; <A HREF="Data-Map.html#t%3AMap"
1239>Map</A
1240> k1 a -&gt; <A HREF="Data-Map.html#t%3AMap"
1241>Map</A
1242> k2 a</TD
1243></TR
1244><TR
1245><TD CLASS="s8"
1246></TD
1247></TR
1248><TR
1249><TD CLASS="decl"
1250><A HREF="#v%3Afold"
1251>fold</A
1252> :: (a -&gt; b -&gt; b) -&gt; b -&gt; <A HREF="Data-Map.html#t%3AMap"
1253>Map</A
1254> k a -&gt; b</TD
1255></TR
1256><TR
1257><TD CLASS="s8"
1258></TD
1259></TR
1260><TR
1261><TD CLASS="decl"
1262><A HREF="#v%3AfoldWithKey"
1263>foldWithKey</A
1264> :: (k -&gt; a -&gt; b -&gt; b) -&gt; b -&gt; <A HREF="Data-Map.html#t%3AMap"
1265>Map</A
1266> k a -&gt; b</TD
1267></TR
1268><TR
1269><TD CLASS="s8"
1270></TD
1271></TR
1272><TR
1273><TD CLASS="decl"
1274><A HREF="#v%3Aelems"
1275>elems</A
1276> :: <A HREF="Data-Map.html#t%3AMap"
1277>Map</A
1278> k a -&gt; [a]</TD
1279></TR
1280><TR
1281><TD CLASS="s8"
1282></TD
1283></TR
1284><TR
1285><TD CLASS="decl"
1286><A HREF="#v%3Akeys"
1287>keys</A
1288> :: <A HREF="Data-Map.html#t%3AMap"
1289>Map</A
1290> k a -&gt; [k]</TD
1291></TR
1292><TR
1293><TD CLASS="s8"
1294></TD
1295></TR
1296><TR
1297><TD CLASS="decl"
1298><A HREF="#v%3AkeysSet"
1299>keysSet</A
1300> :: <A HREF="Data-Map.html#t%3AMap"
1301>Map</A
1302> k a -&gt; Set k</TD
1303></TR
1304><TR
1305><TD CLASS="s8"
1306></TD
1307></TR
1308><TR
1309><TD CLASS="decl"
1310><A HREF="#v%3Aassocs"
1311>assocs</A
1312> :: <A HREF="Data-Map.html#t%3AMap"
1313>Map</A
1314> k a -&gt; [(k, a)]</TD
1315></TR
1316><TR
1317><TD CLASS="s8"
1318></TD
1319></TR
1320><TR
1321><TD CLASS="decl"
1322><A HREF="#v%3AtoList"
1323>toList</A
1324> :: <A HREF="Data-Map.html#t%3AMap"
1325>Map</A
1326> k a -&gt; [(k, a)]</TD
1327></TR
1328><TR
1329><TD CLASS="s8"
1330></TD
1331></TR
1332><TR
1333><TD CLASS="decl"
1334><A HREF="#v%3AfromList"
1335>fromList</A
1336> :: <A HREF="Prelude.html#t%3AOrd"
1337>Ord</A
1338> k =&gt; [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
1339>Map</A
1340> k a</TD
1341></TR
1342><TR
1343><TD CLASS="s8"
1344></TD
1345></TR
1346><TR
1347><TD CLASS="decl"
1348><A HREF="#v%3AfromListWith"
1349>fromListWith</A
1350> :: <A HREF="Prelude.html#t%3AOrd"
1351>Ord</A
1352> k =&gt; (a -&gt; a -&gt; a) -&gt; [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
1353>Map</A
1354> k a</TD
1355></TR
1356><TR
1357><TD CLASS="s8"
1358></TD
1359></TR
1360><TR
1361><TD CLASS="decl"
1362><A HREF="#v%3AfromListWithKey"
1363>fromListWithKey</A
1364> :: <A HREF="Prelude.html#t%3AOrd"
1365>Ord</A
1366> k =&gt; (k -&gt; a -&gt; a -&gt; a) -&gt; [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
1367>Map</A
1368> k a</TD
1369></TR
1370><TR
1371><TD CLASS="s8"
1372></TD
1373></TR
1374><TR
1375><TD CLASS="decl"
1376><A HREF="#v%3AtoAscList"
1377>toAscList</A
1378> :: <A HREF="Data-Map.html#t%3AMap"
1379>Map</A
1380> k a -&gt; [(k, a)]</TD
1381></TR
1382><TR
1383><TD CLASS="s8"
1384></TD
1385></TR
1386><TR
1387><TD CLASS="decl"
1388><A HREF="#v%3AfromAscList"
1389>fromAscList</A
1390> :: <A HREF="Prelude.html#t%3AEq"
1391>Eq</A
1392> k =&gt; [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
1393>Map</A
1394> k a</TD
1395></TR
1396><TR
1397><TD CLASS="s8"
1398></TD
1399></TR
1400><TR
1401><TD CLASS="decl"
1402><A HREF="#v%3AfromAscListWith"
1403>fromAscListWith</A
1404> :: <A HREF="Prelude.html#t%3AEq"
1405>Eq</A
1406> k =&gt; (a -&gt; a -&gt; a) -&gt; [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
1407>Map</A
1408> k a</TD
1409></TR
1410><TR
1411><TD CLASS="s8"
1412></TD
1413></TR
1414><TR
1415><TD CLASS="decl"
1416><A HREF="#v%3AfromAscListWithKey"
1417>fromAscListWithKey</A
1418> :: <A HREF="Prelude.html#t%3AEq"
1419>Eq</A
1420> k =&gt; (k -&gt; a -&gt; a -&gt; a) -&gt; [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
1421>Map</A
1422> k a</TD
1423></TR
1424><TR
1425><TD CLASS="s8"
1426></TD
1427></TR
1428><TR
1429><TD CLASS="decl"
1430><A HREF="#v%3AfromDistinctAscList"
1431>fromDistinctAscList</A
1432> :: [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
1433>Map</A
1434> k a</TD
1435></TR
1436><TR
1437><TD CLASS="s8"
1438></TD
1439></TR
1440><TR
1441><TD CLASS="decl"
1442><A HREF="#v%3Afilter"
1443>filter</A
1444> :: <A HREF="Prelude.html#t%3AOrd"
1445>Ord</A
1446> k =&gt; (a -&gt; <A HREF="Prelude.html#t%3ABool"
1447>Bool</A
1448>) -&gt; <A HREF="Data-Map.html#t%3AMap"
1449>Map</A
1450> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1451>Map</A
1452> k a</TD
1453></TR
1454><TR
1455><TD CLASS="s8"
1456></TD
1457></TR
1458><TR
1459><TD CLASS="decl"
1460><A HREF="#v%3AfilterWithKey"
1461>filterWithKey</A
1462> :: <A HREF="Prelude.html#t%3AOrd"
1463>Ord</A
1464> k =&gt; (k -&gt; a -&gt; <A HREF="Prelude.html#t%3ABool"
1465>Bool</A
1466>) -&gt; <A HREF="Data-Map.html#t%3AMap"
1467>Map</A
1468> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1469>Map</A
1470> k a</TD
1471></TR
1472><TR
1473><TD CLASS="s8"
1474></TD
1475></TR
1476><TR
1477><TD CLASS="decl"
1478><A HREF="#v%3Apartition"
1479>partition</A
1480> :: <A HREF="Prelude.html#t%3AOrd"
1481>Ord</A
1482> k =&gt; (a -&gt; <A HREF="Prelude.html#t%3ABool"
1483>Bool</A
1484>) -&gt; <A HREF="Data-Map.html#t%3AMap"
1485>Map</A
1486> k a -&gt; (<A HREF="Data-Map.html#t%3AMap"
1487>Map</A
1488> k a, <A HREF="Data-Map.html#t%3AMap"
1489>Map</A
1490> k a)</TD
1491></TR
1492><TR
1493><TD CLASS="s8"
1494></TD
1495></TR
1496><TR
1497><TD CLASS="decl"
1498><A HREF="#v%3ApartitionWithKey"
1499>partitionWithKey</A
1500> :: <A HREF="Prelude.html#t%3AOrd"
1501>Ord</A
1502> k =&gt; (k -&gt; a -&gt; <A HREF="Prelude.html#t%3ABool"
1503>Bool</A
1504>) -&gt; <A HREF="Data-Map.html#t%3AMap"
1505>Map</A
1506> k a -&gt; (<A HREF="Data-Map.html#t%3AMap"
1507>Map</A
1508> k a, <A HREF="Data-Map.html#t%3AMap"
1509>Map</A
1510> k a)</TD
1511></TR
1512><TR
1513><TD CLASS="s8"
1514></TD
1515></TR
1516><TR
1517><TD CLASS="decl"
1518><A HREF="#v%3AmapMaybe"
1519>mapMaybe</A
1520> :: <A HREF="Prelude.html#t%3AOrd"
1521>Ord</A
1522> k =&gt; (a -&gt; <A HREF="Prelude.html#t%3AMaybe"
1523>Maybe</A
1524> b) -&gt; <A HREF="Data-Map.html#t%3AMap"
1525>Map</A
1526> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1527>Map</A
1528> k b</TD
1529></TR
1530><TR
1531><TD CLASS="s8"
1532></TD
1533></TR
1534><TR
1535><TD CLASS="decl"
1536><A HREF="#v%3AmapMaybeWithKey"
1537>mapMaybeWithKey</A
1538> :: <A HREF="Prelude.html#t%3AOrd"
1539>Ord</A
1540> k =&gt; (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
1541>Maybe</A
1542> b) -&gt; <A HREF="Data-Map.html#t%3AMap"
1543>Map</A
1544> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1545>Map</A
1546> k b</TD
1547></TR
1548><TR
1549><TD CLASS="s8"
1550></TD
1551></TR
1552><TR
1553><TD CLASS="decl"
1554><A HREF="#v%3AmapEither"
1555>mapEither</A
1556> :: <A HREF="Prelude.html#t%3AOrd"
1557>Ord</A
1558> k =&gt; (a -&gt; <A HREF="Prelude.html#t%3AEither"
1559>Either</A
1560> b c) -&gt; <A HREF="Data-Map.html#t%3AMap"
1561>Map</A
1562> k a -&gt; (<A HREF="Data-Map.html#t%3AMap"
1563>Map</A
1564> k b, <A HREF="Data-Map.html#t%3AMap"
1565>Map</A
1566> k c)</TD
1567></TR
1568><TR
1569><TD CLASS="s8"
1570></TD
1571></TR
1572><TR
1573><TD CLASS="decl"
1574><A HREF="#v%3AmapEitherWithKey"
1575>mapEitherWithKey</A
1576> :: <A HREF="Prelude.html#t%3AOrd"
1577>Ord</A
1578> k =&gt; (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AEither"
1579>Either</A
1580> b c) -&gt; <A HREF="Data-Map.html#t%3AMap"
1581>Map</A
1582> k a -&gt; (<A HREF="Data-Map.html#t%3AMap"
1583>Map</A
1584> k b, <A HREF="Data-Map.html#t%3AMap"
1585>Map</A
1586> k c)</TD
1587></TR
1588><TR
1589><TD CLASS="s8"
1590></TD
1591></TR
1592><TR
1593><TD CLASS="decl"
1594><A HREF="#v%3Asplit"
1595>split</A
1596> :: <A HREF="Prelude.html#t%3AOrd"
1597>Ord</A
1598> k =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
1599>Map</A
1600> k a -&gt; (<A HREF="Data-Map.html#t%3AMap"
1601>Map</A
1602> k a, <A HREF="Data-Map.html#t%3AMap"
1603>Map</A
1604> k a)</TD
1605></TR
1606><TR
1607><TD CLASS="s8"
1608></TD
1609></TR
1610><TR
1611><TD CLASS="decl"
1612><A HREF="#v%3AsplitLookup"
1613>splitLookup</A
1614> :: <A HREF="Prelude.html#t%3AOrd"
1615>Ord</A
1616> k =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
1617>Map</A
1618> k a -&gt; (<A HREF="Data-Map.html#t%3AMap"
1619>Map</A
1620> k a, <A HREF="Prelude.html#t%3AMaybe"
1621>Maybe</A
1622> a, <A HREF="Data-Map.html#t%3AMap"
1623>Map</A
1624> k a)</TD
1625></TR
1626><TR
1627><TD CLASS="s8"
1628></TD
1629></TR
1630><TR
1631><TD CLASS="decl"
1632><A HREF="#v%3AisSubmapOf"
1633>isSubmapOf</A
1634> :: (<A HREF="Prelude.html#t%3AOrd"
1635>Ord</A
1636> k, <A HREF="Prelude.html#t%3AEq"
1637>Eq</A
1638> a) =&gt; <A HREF="Data-Map.html#t%3AMap"
1639>Map</A
1640> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1641>Map</A
1642> k a -&gt; <A HREF="Prelude.html#t%3ABool"
1643>Bool</A
1644></TD
1645></TR
1646><TR
1647><TD CLASS="s8"
1648></TD
1649></TR
1650><TR
1651><TD CLASS="decl"
1652><A HREF="#v%3AisSubmapOfBy"
1653>isSubmapOfBy</A
1654> :: <A HREF="Prelude.html#t%3AOrd"
1655>Ord</A
1656> k =&gt; (a -&gt; b -&gt; <A HREF="Prelude.html#t%3ABool"
1657>Bool</A
1658>) -&gt; <A HREF="Data-Map.html#t%3AMap"
1659>Map</A
1660> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1661>Map</A
1662> k b -&gt; <A HREF="Prelude.html#t%3ABool"
1663>Bool</A
1664></TD
1665></TR
1666><TR
1667><TD CLASS="s8"
1668></TD
1669></TR
1670><TR
1671><TD CLASS="decl"
1672><A HREF="#v%3AisProperSubmapOf"
1673>isProperSubmapOf</A
1674> :: (<A HREF="Prelude.html#t%3AOrd"
1675>Ord</A
1676> k, <A HREF="Prelude.html#t%3AEq"
1677>Eq</A
1678> a) =&gt; <A HREF="Data-Map.html#t%3AMap"
1679>Map</A
1680> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1681>Map</A
1682> k a -&gt; <A HREF="Prelude.html#t%3ABool"
1683>Bool</A
1684></TD
1685></TR
1686><TR
1687><TD CLASS="s8"
1688></TD
1689></TR
1690><TR
1691><TD CLASS="decl"
1692><A HREF="#v%3AisProperSubmapOfBy"
1693>isProperSubmapOfBy</A
1694> :: <A HREF="Prelude.html#t%3AOrd"
1695>Ord</A
1696> k =&gt; (a -&gt; b -&gt; <A HREF="Prelude.html#t%3ABool"
1697>Bool</A
1698>) -&gt; <A HREF="Data-Map.html#t%3AMap"
1699>Map</A
1700> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1701>Map</A
1702> k b -&gt; <A HREF="Prelude.html#t%3ABool"
1703>Bool</A
1704></TD
1705></TR
1706><TR
1707><TD CLASS="s8"
1708></TD
1709></TR
1710><TR
1711><TD CLASS="decl"
1712><A HREF="#v%3AlookupIndex"
1713>lookupIndex</A
1714> :: (<A HREF="Prelude.html#t%3AMonad"
1715>Monad</A
1716> m, <A HREF="Prelude.html#t%3AOrd"
1717>Ord</A
1718> k) =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
1719>Map</A
1720> k a -&gt; m <A HREF="Prelude.html#t%3AInt"
1721>Int</A
1722></TD
1723></TR
1724><TR
1725><TD CLASS="s8"
1726></TD
1727></TR
1728><TR
1729><TD CLASS="decl"
1730><A HREF="#v%3AfindIndex"
1731>findIndex</A
1732> :: <A HREF="Prelude.html#t%3AOrd"
1733>Ord</A
1734> k =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
1735>Map</A
1736> k a -&gt; <A HREF="Prelude.html#t%3AInt"
1737>Int</A
1738></TD
1739></TR
1740><TR
1741><TD CLASS="s8"
1742></TD
1743></TR
1744><TR
1745><TD CLASS="decl"
1746><A HREF="#v%3AelemAt"
1747>elemAt</A
1748> :: <A HREF="Prelude.html#t%3AInt"
1749>Int</A
1750> -&gt; <A HREF="Data-Map.html#t%3AMap"
1751>Map</A
1752> k a -&gt; (k, a)</TD
1753></TR
1754><TR
1755><TD CLASS="s8"
1756></TD
1757></TR
1758><TR
1759><TD CLASS="decl"
1760><A HREF="#v%3AupdateAt"
1761>updateAt</A
1762> :: (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
1763>Maybe</A
1764> a) -&gt; <A HREF="Prelude.html#t%3AInt"
1765>Int</A
1766> -&gt; <A HREF="Data-Map.html#t%3AMap"
1767>Map</A
1768> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1769>Map</A
1770> k a</TD
1771></TR
1772><TR
1773><TD CLASS="s8"
1774></TD
1775></TR
1776><TR
1777><TD CLASS="decl"
1778><A HREF="#v%3AdeleteAt"
1779>deleteAt</A
1780> :: <A HREF="Prelude.html#t%3AInt"
1781>Int</A
1782> -&gt; <A HREF="Data-Map.html#t%3AMap"
1783>Map</A
1784> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1785>Map</A
1786> k a</TD
1787></TR
1788><TR
1789><TD CLASS="s8"
1790></TD
1791></TR
1792><TR
1793><TD CLASS="decl"
1794><A HREF="#v%3AfindMin"
1795>findMin</A
1796> :: <A HREF="Data-Map.html#t%3AMap"
1797>Map</A
1798> k a -&gt; (k, a)</TD
1799></TR
1800><TR
1801><TD CLASS="s8"
1802></TD
1803></TR
1804><TR
1805><TD CLASS="decl"
1806><A HREF="#v%3AfindMax"
1807>findMax</A
1808> :: <A HREF="Data-Map.html#t%3AMap"
1809>Map</A
1810> k a -&gt; (k, a)</TD
1811></TR
1812><TR
1813><TD CLASS="s8"
1814></TD
1815></TR
1816><TR
1817><TD CLASS="decl"
1818><A HREF="#v%3AdeleteMin"
1819>deleteMin</A
1820> :: <A HREF="Data-Map.html#t%3AMap"
1821>Map</A
1822> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1823>Map</A
1824> k a</TD
1825></TR
1826><TR
1827><TD CLASS="s8"
1828></TD
1829></TR
1830><TR
1831><TD CLASS="decl"
1832><A HREF="#v%3AdeleteMax"
1833>deleteMax</A
1834> :: <A HREF="Data-Map.html#t%3AMap"
1835>Map</A
1836> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1837>Map</A
1838> k a</TD
1839></TR
1840><TR
1841><TD CLASS="s8"
1842></TD
1843></TR
1844><TR
1845><TD CLASS="decl"
1846><A HREF="#v%3AdeleteFindMin"
1847>deleteFindMin</A
1848> :: <A HREF="Data-Map.html#t%3AMap"
1849>Map</A
1850> k a -&gt; ((k, a), <A HREF="Data-Map.html#t%3AMap"
1851>Map</A
1852> k a)</TD
1853></TR
1854><TR
1855><TD CLASS="s8"
1856></TD
1857></TR
1858><TR
1859><TD CLASS="decl"
1860><A HREF="#v%3AdeleteFindMax"
1861>deleteFindMax</A
1862> :: <A HREF="Data-Map.html#t%3AMap"
1863>Map</A
1864> k a -&gt; ((k, a), <A HREF="Data-Map.html#t%3AMap"
1865>Map</A
1866> k a)</TD
1867></TR
1868><TR
1869><TD CLASS="s8"
1870></TD
1871></TR
1872><TR
1873><TD CLASS="decl"
1874><A HREF="#v%3AupdateMin"
1875>updateMin</A
1876> :: (a -&gt; <A HREF="Prelude.html#t%3AMaybe"
1877>Maybe</A
1878> a) -&gt; <A HREF="Data-Map.html#t%3AMap"
1879>Map</A
1880> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1881>Map</A
1882> k a</TD
1883></TR
1884><TR
1885><TD CLASS="s8"
1886></TD
1887></TR
1888><TR
1889><TD CLASS="decl"
1890><A HREF="#v%3AupdateMax"
1891>updateMax</A
1892> :: (a -&gt; <A HREF="Prelude.html#t%3AMaybe"
1893>Maybe</A
1894> a) -&gt; <A HREF="Data-Map.html#t%3AMap"
1895>Map</A
1896> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1897>Map</A
1898> k a</TD
1899></TR
1900><TR
1901><TD CLASS="s8"
1902></TD
1903></TR
1904><TR
1905><TD CLASS="decl"
1906><A HREF="#v%3AupdateMinWithKey"
1907>updateMinWithKey</A
1908> :: (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
1909>Maybe</A
1910> a) -&gt; <A HREF="Data-Map.html#t%3AMap"
1911>Map</A
1912> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1913>Map</A
1914> k a</TD
1915></TR
1916><TR
1917><TD CLASS="s8"
1918></TD
1919></TR
1920><TR
1921><TD CLASS="decl"
1922><A HREF="#v%3AupdateMaxWithKey"
1923>updateMaxWithKey</A
1924> :: (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
1925>Maybe</A
1926> a) -&gt; <A HREF="Data-Map.html#t%3AMap"
1927>Map</A
1928> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
1929>Map</A
1930> k a</TD
1931></TR
1932><TR
1933><TD CLASS="s8"
1934></TD
1935></TR
1936><TR
1937><TD CLASS="decl"
1938><A HREF="#v%3AminView"
1939>minView</A
1940> :: <A HREF="Prelude.html#t%3AMonad"
1941>Monad</A
1942> m =&gt; <A HREF="Data-Map.html#t%3AMap"
1943>Map</A
1944> k a -&gt; m (a, <A HREF="Data-Map.html#t%3AMap"
1945>Map</A
1946> k a)</TD
1947></TR
1948><TR
1949><TD CLASS="s8"
1950></TD
1951></TR
1952><TR
1953><TD CLASS="decl"
1954><A HREF="#v%3AmaxView"
1955>maxView</A
1956> :: <A HREF="Prelude.html#t%3AMonad"
1957>Monad</A
1958> m =&gt; <A HREF="Data-Map.html#t%3AMap"
1959>Map</A
1960> k a -&gt; m (a, <A HREF="Data-Map.html#t%3AMap"
1961>Map</A
1962> k a)</TD
1963></TR
1964><TR
1965><TD CLASS="s8"
1966></TD
1967></TR
1968><TR
1969><TD CLASS="decl"
1970><A HREF="#v%3AminViewWithKey"
1971>minViewWithKey</A
1972> :: <A HREF="Prelude.html#t%3AMonad"
1973>Monad</A
1974> m =&gt; <A HREF="Data-Map.html#t%3AMap"
1975>Map</A
1976> k a -&gt; m ((k, a), <A HREF="Data-Map.html#t%3AMap"
1977>Map</A
1978> k a)</TD
1979></TR
1980><TR
1981><TD CLASS="s8"
1982></TD
1983></TR
1984><TR
1985><TD CLASS="decl"
1986><A HREF="#v%3AmaxViewWithKey"
1987>maxViewWithKey</A
1988> :: <A HREF="Prelude.html#t%3AMonad"
1989>Monad</A
1990> m =&gt; <A HREF="Data-Map.html#t%3AMap"
1991>Map</A
1992> k a -&gt; m ((k, a), <A HREF="Data-Map.html#t%3AMap"
1993>Map</A
1994> k a)</TD
1995></TR
1996><TR
1997><TD CLASS="s8"
1998></TD
1999></TR
2000><TR
2001><TD CLASS="decl"
2002><A HREF="#v%3AshowTree"
2003>showTree</A
2004> :: (<A HREF="Prelude.html#t%3AShow"
2005>Show</A
2006> k, <A HREF="Prelude.html#t%3AShow"
2007>Show</A
2008> a) =&gt; <A HREF="Data-Map.html#t%3AMap"
2009>Map</A
2010> k a -&gt; <A HREF="Prelude.html#t%3AString"
2011>String</A
2012></TD
2013></TR
2014><TR
2015><TD CLASS="s8"
2016></TD
2017></TR
2018><TR
2019><TD CLASS="decl"
2020><A HREF="#v%3AshowTreeWith"
2021>showTreeWith</A
2022> :: (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AString"
2023>String</A
2024>) -&gt; <A HREF="Prelude.html#t%3ABool"
2025>Bool</A
2026> -&gt; <A HREF="Prelude.html#t%3ABool"
2027>Bool</A
2028> -&gt; <A HREF="Data-Map.html#t%3AMap"
2029>Map</A
2030> k a -&gt; <A HREF="Prelude.html#t%3AString"
2031>String</A
2032></TD
2033></TR
2034><TR
2035><TD CLASS="s8"
2036></TD
2037></TR
2038><TR
2039><TD CLASS="decl"
2040><A HREF="#v%3Avalid"
2041>valid</A
2042> :: <A HREF="Prelude.html#t%3AOrd"
2043>Ord</A
2044> k =&gt; <A HREF="Data-Map.html#t%3AMap"
2045>Map</A
2046> k a -&gt; <A HREF="Prelude.html#t%3ABool"
2047>Bool</A
2048></TD
2049></TR
2050></TABLE
2051></TD
2052></TR
2053><TR
2054><TD CLASS="s15"
2055></TD
2056></TR
2057><TR
2058><TD CLASS="s15"
2059></TD
2060></TR
2061><TR
2062><TD CLASS="section1"
2063><A NAME="1"
2064>Map type
2065</A
2066></TD
2067></TR
2068><TR
2069><TD CLASS="s15"
2070></TD
2071></TR
2072><TR
2073><TD CLASS="decl"
2074><SPAN CLASS="keyword"
2075>data</SPAN
2076> <A NAME="t%3AMap"
2077></A
2078><B
2079>Map</B
2080> k a</TD
2081></TR
2082><TR
2083><TD CLASS="body"
2084><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
2085><TR
2086><TD CLASS="ndoc"
2087>A Map from keys <TT
2088>k</TT
2089> to values <TT
2090>a</TT
2091>.
2092</TD
2093></TR
2094><TR
2095><TD CLASS="section4"
2096><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:Map')" ALT="show/hide"
2097> Instances</TD
2098></TR
2099><TR
2100><TD CLASS="body"
2101><DIV ID="i:Map" STYLE="display:block;"
2102><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"
2103><TR
2104><TD CLASS="decl"
2105>Typeable2 <A HREF="Data-Map.html#t%3AMap"
2106>Map</A
2107></TD
2108></TR
2109><TR
2110><TD CLASS="decl"
2111>Foldable (<A HREF="Data-Map.html#t%3AMap"
2112>Map</A
2113> k)</TD
2114></TR
2115><TR
2116><TD CLASS="decl"
2117><A HREF="Prelude.html#t%3AFunctor"
2118>Functor</A
2119> (<A HREF="Data-Map.html#t%3AMap"
2120>Map</A
2121> k)</TD
2122></TR
2123><TR
2124><TD CLASS="decl"
2125>Traversable (<A HREF="Data-Map.html#t%3AMap"
2126>Map</A
2127> k)</TD
2128></TR
2129><TR
2130><TD CLASS="decl"
2131>(Data k, Data a, <A HREF="Prelude.html#t%3AOrd"
2132>Ord</A
2133> k) =&gt; Data (<A HREF="Data-Map.html#t%3AMap"
2134>Map</A
2135> k a)</TD
2136></TR
2137><TR
2138><TD CLASS="decl"
2139>(<A HREF="Prelude.html#t%3AEq"
2140>Eq</A
2141> k, <A HREF="Prelude.html#t%3AEq"
2142>Eq</A
2143> a) =&gt; <A HREF="Prelude.html#t%3AEq"
2144>Eq</A
2145> (<A HREF="Data-Map.html#t%3AMap"
2146>Map</A
2147> k a)</TD
2148></TR
2149><TR
2150><TD CLASS="decl"
2151><A HREF="Prelude.html#t%3AOrd"
2152>Ord</A
2153> k =&gt; Monoid (<A HREF="Data-Map.html#t%3AMap"
2154>Map</A
2155> k v)</TD
2156></TR
2157><TR
2158><TD CLASS="decl"
2159>(<A HREF="Prelude.html#t%3AOrd"
2160>Ord</A
2161> k, <A HREF="Prelude.html#t%3AOrd"
2162>Ord</A
2163> v) =&gt; <A HREF="Prelude.html#t%3AOrd"
2164>Ord</A
2165> (<A HREF="Data-Map.html#t%3AMap"
2166>Map</A
2167> k v)</TD
2168></TR
2169><TR
2170><TD CLASS="decl"
2171>(<A HREF="Prelude.html#t%3AOrd"
2172>Ord</A
2173> k, <A HREF="Prelude.html#t%3ARead"
2174>Read</A
2175> k, <A HREF="Prelude.html#t%3ARead"
2176>Read</A
2177> e) =&gt; <A HREF="Prelude.html#t%3ARead"
2178>Read</A
2179> (<A HREF="Data-Map.html#t%3AMap"
2180>Map</A
2181> k e)</TD
2182></TR
2183><TR
2184><TD CLASS="decl"
2185>(<A HREF="Prelude.html#t%3AShow"
2186>Show</A
2187> k, <A HREF="Prelude.html#t%3AShow"
2188>Show</A
2189> a) =&gt; <A HREF="Prelude.html#t%3AShow"
2190>Show</A
2191> (<A HREF="Data-Map.html#t%3AMap"
2192>Map</A
2193> k a)</TD
2194></TR
2195></TABLE
2196></DIV
2197></TD
2198></TR
2199></TABLE
2200></TD
2201></TR
2202><TR
2203><TD CLASS="s15"
2204></TD
2205></TR
2206><TR
2207><TD CLASS="section1"
2208><A NAME="2"
2209>Operators
2210</A
2211></TD
2212></TR
2213><TR
2214><TD CLASS="s15"
2215></TD
2216></TR
2217><TR
2218><TD CLASS="decl"
2219><A NAME="v%3A%21"
2220></A
2221><B
2222>(!)</B
2223> :: <A HREF="Prelude.html#t%3AOrd"
2224>Ord</A
2225> k =&gt; <A HREF="Data-Map.html#t%3AMap"
2226>Map</A
2227> k a -&gt; k -&gt; a</TD
2228></TR
2229><TR
2230><TD CLASS="doc"
2231><P
2232><EM
2233>O(log n)</EM
2234>. Find the value at a key.
2235 Calls <TT
2236><A HREF="Prelude.html#v%3Aerror"
2237>error</A
2238></TT
2239> when the element can not be found.
2240</P
2241><PRE
2242> fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map
2243 fromList [(5,'a'), (3,'b')] ! 5 == 'a'
2244</PRE
2245></TD
2246></TR
2247><TR
2248><TD CLASS="s15"
2249></TD
2250></TR
2251><TR
2252><TD CLASS="decl"
2253><A NAME="v%3A%5C%5C"
2254></A
2255><B
2256>(\\)</B
2257> :: <A HREF="Prelude.html#t%3AOrd"
2258>Ord</A
2259> k =&gt; <A HREF="Data-Map.html#t%3AMap"
2260>Map</A
2261> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
2262>Map</A
2263> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
2264>Map</A
2265> k a</TD
2266></TR
2267><TR
2268><TD CLASS="doc"
2269>Same as <TT
2270><A HREF="Data-Map.html#v%3Adifference"
2271>difference</A
2272></TT
2273>.
2274</TD
2275></TR
2276><TR
2277><TD CLASS="s15"
2278></TD
2279></TR
2280><TR
2281><TD CLASS="section1"
2282><A NAME="3"
2283>Query
2284</A
2285></TD
2286></TR
2287><TR
2288><TD CLASS="s15"
2289></TD
2290></TR
2291><TR
2292><TD CLASS="decl"
2293><A NAME="v%3Anull"
2294></A
2295><B
2296>null</B
2297> :: <A HREF="Data-Map.html#t%3AMap"
2298>Map</A
2299> k a -&gt; <A HREF="Prelude.html#t%3ABool"
2300>Bool</A
2301></TD
2302></TR
2303><TR
2304><TD CLASS="doc"
2305><P
2306><EM
2307>O(1)</EM
2308>. Is the map empty?
2309</P
2310><PRE
2311> Data.Map.null (empty)           == True
2312 Data.Map.null (singleton 1 'a') == False
2313</PRE
2314></TD
2315></TR
2316><TR
2317><TD CLASS="s15"
2318></TD
2319></TR
2320><TR
2321><TD CLASS="decl"
2322><A NAME="v%3Asize"
2323></A
2324><B
2325>size</B
2326> :: <A HREF="Data-Map.html#t%3AMap"
2327>Map</A
2328> k a -&gt; <A HREF="Prelude.html#t%3AInt"
2329>Int</A
2330></TD
2331></TR
2332><TR
2333><TD CLASS="doc"
2334><P
2335><EM
2336>O(1)</EM
2337>. The number of elements in the map.
2338</P
2339><PRE
2340> size empty                                   == 0
2341 size (singleton 1 'a')                       == 1
2342 size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
2343</PRE
2344></TD
2345></TR
2346><TR
2347><TD CLASS="s15"
2348></TD
2349></TR
2350><TR
2351><TD CLASS="decl"
2352><A NAME="v%3Amember"
2353></A
2354><B
2355>member</B
2356> :: <A HREF="Prelude.html#t%3AOrd"
2357>Ord</A
2358> k =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
2359>Map</A
2360> k a -&gt; <A HREF="Prelude.html#t%3ABool"
2361>Bool</A
2362></TD
2363></TR
2364><TR
2365><TD CLASS="doc"
2366><P
2367><EM
2368>O(log n)</EM
2369>. Is the key a member of the map? See also <TT
2370><A HREF="Data-Map.html#v%3AnotMember"
2371>notMember</A
2372></TT
2373>.
2374</P
2375><PRE
2376> member 5 (fromList [(5,'a'), (3,'b')]) == True
2377 member 1 (fromList [(5,'a'), (3,'b')]) == False
2378</PRE
2379></TD
2380></TR
2381><TR
2382><TD CLASS="s15"
2383></TD
2384></TR
2385><TR
2386><TD CLASS="decl"
2387><A NAME="v%3AnotMember"
2388></A
2389><B
2390>notMember</B
2391> :: <A HREF="Prelude.html#t%3AOrd"
2392>Ord</A
2393> k =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
2394>Map</A
2395> k a -&gt; <A HREF="Prelude.html#t%3ABool"
2396>Bool</A
2397></TD
2398></TR
2399><TR
2400><TD CLASS="doc"
2401><P
2402><EM
2403>O(log n)</EM
2404>. Is the key not a member of the map? See also <TT
2405><A HREF="Data-Map.html#v%3Amember"
2406>member</A
2407></TT
2408>.
2409</P
2410><PRE
2411> notMember 5 (fromList [(5,'a'), (3,'b')]) == False
2412 notMember 1 (fromList [(5,'a'), (3,'b')]) == True
2413</PRE
2414></TD
2415></TR
2416><TR
2417><TD CLASS="s15"
2418></TD
2419></TR
2420><TR
2421><TD CLASS="decl"
2422><A NAME="v%3Alookup"
2423></A
2424><B
2425>lookup</B
2426> :: (<A HREF="Prelude.html#t%3AMonad"
2427>Monad</A
2428> m, <A HREF="Prelude.html#t%3AOrd"
2429>Ord</A
2430> k) =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
2431>Map</A
2432> k a -&gt; m a</TD
2433></TR
2434><TR
2435><TD CLASS="doc"
2436><P
2437><EM
2438>O(log n)</EM
2439>. Lookup the value at a key in the map.
2440</P
2441><P
2442>The function will
2443 <TT
2444>return</TT
2445> the result in the monad or <TT
2446>fail</TT
2447> in it the key isn't in the
2448 map. Often, the monad to use is <TT
2449><A HREF="Prelude.html#t%3AMaybe"
2450>Maybe</A
2451></TT
2452>, so you get either
2453 <TT
2454>(<TT
2455><A HREF="Prelude.html#v%3AJust"
2456>Just</A
2457></TT
2458> result)</TT
2459> or <TT
2460><TT
2461><A HREF="Prelude.html#v%3ANothing"
2462>Nothing</A
2463></TT
2464></TT
2465>.
2466</P
2467><PRE
2468> let m = fromList [(5,'a'), (3,'b'), (7,'c')]
2469 value1 &lt;- Data.Map.lookup 5 m
2470 value1
2471   'a'
2472 value2 &lt;- Data.Map.lookup 1 m
2473   Error: Key not found
2474</PRE
2475><P
2476>An example of using <TT
2477>lookup</TT
2478> with <TT
2479>Maybe</TT
2480> monad:
2481</P
2482><PRE
2483> import Prelude hiding (lookup)
2484 import Data.Map
2485
2486 employeeDept = fromList([(&quot;John&quot;,&quot;Sales&quot;), (&quot;Bob&quot;,&quot;IT&quot;)])
2487 deptCountry = fromList([(&quot;IT&quot;,&quot;USA&quot;), (&quot;Sales&quot;,&quot;France&quot;)])
2488 countryCurrency = fromList([(&quot;USA&quot;, &quot;Dollar&quot;), (&quot;France&quot;, &quot;Euro&quot;)])
2489
2490 employeeCurrency :: String -&gt; Maybe String
2491 employeeCurrency name = do
2492     dept &lt;- lookup name employeeDept
2493     country &lt;- lookup dept deptCountry
2494     lookup country countryCurrency
2495
2496 main = do
2497     putStrLn $ &quot;John's currency: &quot; ++ (show (employeeCurrency &quot;John&quot;))
2498     putStrLn $ &quot;Pete's currency: &quot; ++ (show (employeeCurrency &quot;Pete&quot;))
2499</PRE
2500><P
2501>The output of this program:
2502</P
2503><PRE
2504>   John's currency: Just &quot;Euro&quot;
2505   Pete's currency: Nothing
2506</PRE
2507></TD
2508></TR
2509><TR
2510><TD CLASS="s15"
2511></TD
2512></TR
2513><TR
2514><TD CLASS="decl"
2515><A NAME="v%3AfindWithDefault"
2516></A
2517><B
2518>findWithDefault</B
2519> :: <A HREF="Prelude.html#t%3AOrd"
2520>Ord</A
2521> k =&gt; a -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
2522>Map</A
2523> k a -&gt; a</TD
2524></TR
2525><TR
2526><TD CLASS="doc"
2527><P
2528><EM
2529>O(log n)</EM
2530>. The expression <TT
2531>(<TT
2532><A HREF="Data-Map.html#v%3AfindWithDefault"
2533>findWithDefault</A
2534></TT
2535> def k map)</TT
2536> returns
2537 the value at key <TT
2538>k</TT
2539> or returns default value <TT
2540>def</TT
2541>
2542 when the key is not in the map.
2543</P
2544><PRE
2545> findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
2546 findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
2547</PRE
2548></TD
2549></TR
2550><TR
2551><TD CLASS="s15"
2552></TD
2553></TR
2554><TR
2555><TD CLASS="section1"
2556><A NAME="4"
2557>Construction
2558</A
2559></TD
2560></TR
2561><TR
2562><TD CLASS="s15"
2563></TD
2564></TR
2565><TR
2566><TD CLASS="decl"
2567><A NAME="v%3Aempty"
2568></A
2569><B
2570>empty</B
2571> :: <A HREF="Data-Map.html#t%3AMap"
2572>Map</A
2573> k a</TD
2574></TR
2575><TR
2576><TD CLASS="doc"
2577><P
2578><EM
2579>O(1)</EM
2580>. The empty map.
2581</P
2582><PRE
2583> empty      == fromList []
2584 size empty == 0
2585</PRE
2586></TD
2587></TR
2588><TR
2589><TD CLASS="s15"
2590></TD
2591></TR
2592><TR
2593><TD CLASS="decl"
2594><A NAME="v%3Asingleton"
2595></A
2596><B
2597>singleton</B
2598> :: k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
2599>Map</A
2600> k a</TD
2601></TR
2602><TR
2603><TD CLASS="doc"
2604><P
2605><EM
2606>O(1)</EM
2607>. A map with a single element.
2608</P
2609><PRE
2610> singleton 1 'a'        == fromList [(1, 'a')]
2611 size (singleton 1 'a') == 1
2612</PRE
2613></TD
2614></TR
2615><TR
2616><TD CLASS="s15"
2617></TD
2618></TR
2619><TR
2620><TD CLASS="section2"
2621><A NAME="5"
2622>Insertion
2623</A
2624></TD
2625></TR
2626><TR
2627><TD CLASS="s15"
2628></TD
2629></TR
2630><TR
2631><TD CLASS="decl"
2632><A NAME="v%3Ainsert"
2633></A
2634><B
2635>insert</B
2636> :: <A HREF="Prelude.html#t%3AOrd"
2637>Ord</A
2638> k =&gt; k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
2639>Map</A
2640> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
2641>Map</A
2642> k a</TD
2643></TR
2644><TR
2645><TD CLASS="doc"
2646><P
2647><EM
2648>O(log n)</EM
2649>. Insert a new key and value in the map.
2650 If the key is already present in the map, the associated value is
2651 replaced with the supplied value. <TT
2652><A HREF="Data-Map.html#v%3Ainsert"
2653>insert</A
2654></TT
2655> is equivalent to
2656 <TT
2657><TT
2658><A HREF="Data-Map.html#v%3AinsertWith"
2659>insertWith</A
2660></TT
2661> <TT
2662><A HREF="Prelude.html#v%3Aconst"
2663>const</A
2664></TT
2665></TT
2666>.
2667</P
2668><PRE
2669> insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]
2670 insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]
2671 insert 5 'x' empty                         == singleton 5 'x'
2672</PRE
2673></TD
2674></TR
2675><TR
2676><TD CLASS="s15"
2677></TD
2678></TR
2679><TR
2680><TD CLASS="decl"
2681><A NAME="v%3AinsertWith"
2682></A
2683><B
2684>insertWith</B
2685> :: <A HREF="Prelude.html#t%3AOrd"
2686>Ord</A
2687> k =&gt; (a -&gt; a -&gt; a) -&gt; k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
2688>Map</A
2689> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
2690>Map</A
2691> k a</TD
2692></TR
2693><TR
2694><TD CLASS="doc"
2695><P
2696><EM
2697>O(log n)</EM
2698>. Insert with a function, combining new value and old value.
2699 <TT
2700><TT
2701><A HREF="Data-Map.html#v%3AinsertWith"
2702>insertWith</A
2703></TT
2704> f key value mp</TT
2705> 
2706 will insert the pair (key, value) into <TT
2707>mp</TT
2708> if key does
2709 not exist in the map. If the key does exist, the function will
2710 insert the pair <TT
2711>(key, f new_value old_value)</TT
2712>.
2713</P
2714><PRE
2715> insertWith (++) 5 &quot;xxx&quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;xxxa&quot;)]
2716 insertWith (++) 7 &quot;xxx&quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;), (7, &quot;xxx&quot;)]
2717 insertWith (++) 5 &quot;xxx&quot; empty                         == singleton 5 &quot;xxx&quot;
2718</PRE
2719></TD
2720></TR
2721><TR
2722><TD CLASS="s15"
2723></TD
2724></TR
2725><TR
2726><TD CLASS="decl"
2727><A NAME="v%3AinsertWithKey"
2728></A
2729><B
2730>insertWithKey</B
2731> :: <A HREF="Prelude.html#t%3AOrd"
2732>Ord</A
2733> k =&gt; (k -&gt; a -&gt; a -&gt; a) -&gt; k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
2734>Map</A
2735> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
2736>Map</A
2737> k a</TD
2738></TR
2739><TR
2740><TD CLASS="doc"
2741><P
2742><EM
2743>O(log n)</EM
2744>. Insert with a function, combining key, new value and old value.
2745 <TT
2746><TT
2747><A HREF="Data-Map.html#v%3AinsertWithKey"
2748>insertWithKey</A
2749></TT
2750> f key value mp</TT
2751> 
2752 will insert the pair (key, value) into <TT
2753>mp</TT
2754> if key does
2755 not exist in the map. If the key does exist, the function will
2756 insert the pair <TT
2757>(key,f key new_value old_value)</TT
2758>.
2759 Note that the key passed to f is the same key passed to <TT
2760><A HREF="Data-Map.html#v%3AinsertWithKey"
2761>insertWithKey</A
2762></TT
2763>.
2764</P
2765><PRE
2766> let f key new_value old_value = (show key) ++ &quot;:&quot; ++ new_value ++ &quot;|&quot; ++ old_value
2767 insertWithKey f 5 &quot;xxx&quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;5:xxx|a&quot;)]
2768 insertWithKey f 7 &quot;xxx&quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;), (7, &quot;xxx&quot;)]
2769 insertWithKey f 5 &quot;xxx&quot; empty                         == singleton 5 &quot;xxx&quot;
2770</PRE
2771></TD
2772></TR
2773><TR
2774><TD CLASS="s15"
2775></TD
2776></TR
2777><TR
2778><TD CLASS="decl"
2779><A NAME="v%3AinsertLookupWithKey"
2780></A
2781><B
2782>insertLookupWithKey</B
2783> :: <A HREF="Prelude.html#t%3AOrd"
2784>Ord</A
2785> k =&gt; (k -&gt; a -&gt; a -&gt; a) -&gt; k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
2786>Map</A
2787> k a -&gt; (<A HREF="Prelude.html#t%3AMaybe"
2788>Maybe</A
2789> a, <A HREF="Data-Map.html#t%3AMap"
2790>Map</A
2791> k a)</TD
2792></TR
2793><TR
2794><TD CLASS="doc"
2795><P
2796><EM
2797>O(log n)</EM
2798>. Combines insert operation with old value retrieval.
2799 The expression (<TT
2800><TT
2801><A HREF="Data-Map.html#v%3AinsertLookupWithKey"
2802>insertLookupWithKey</A
2803></TT
2804> f k x map</TT
2805>)
2806 is a pair where the first element is equal to (<TT
2807><TT
2808><A HREF="Data-Map.html#v%3Alookup"
2809>lookup</A
2810></TT
2811> k map</TT
2812>)
2813 and the second element equal to (<TT
2814><TT
2815><A HREF="Data-Map.html#v%3AinsertWithKey"
2816>insertWithKey</A
2817></TT
2818> f k x map</TT
2819>).
2820</P
2821><PRE
2822> let f key new_value old_value = (show key) ++ &quot;:&quot; ++ new_value ++ &quot;|&quot; ++ old_value
2823 insertLookupWithKey f 5 &quot;xxx&quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (Just &quot;a&quot;, fromList [(3, &quot;b&quot;), (5, &quot;5:xxx|a&quot;)])
2824 insertLookupWithKey f 7 &quot;xxx&quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (Nothing,  fromList [(3, &quot;b&quot;), (5, &quot;a&quot;), (7, &quot;xxx&quot;)])
2825 insertLookupWithKey f 5 &quot;xxx&quot; empty                         == (Nothing,  singleton 5 &quot;xxx&quot;)
2826</PRE
2827><P
2828>This is how to define <TT
2829>insertLookup</TT
2830> using <TT
2831>insertLookupWithKey</TT
2832>:
2833</P
2834><PRE
2835> let insertLookup kx x t = insertLookupWithKey (\_ a _ -&gt; a) kx x t
2836 insertLookup 5 &quot;x&quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (Just &quot;a&quot;, fromList [(3, &quot;b&quot;), (5, &quot;x&quot;)])
2837 insertLookup 7 &quot;x&quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (Nothing,  fromList [(3, &quot;b&quot;), (5, &quot;a&quot;), (7, &quot;x&quot;)])
2838</PRE
2839></TD
2840></TR
2841><TR
2842><TD CLASS="s15"
2843></TD
2844></TR
2845><TR
2846><TD CLASS="decl"
2847><A NAME="v%3AinsertWith%27"
2848></A
2849><B
2850>insertWith'</B
2851> :: <A HREF="Prelude.html#t%3AOrd"
2852>Ord</A
2853> k =&gt; (a -&gt; a -&gt; a) -&gt; k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
2854>Map</A
2855> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
2856>Map</A
2857> k a</TD
2858></TR
2859><TR
2860><TD CLASS="doc"
2861>Same as <TT
2862><A HREF="Data-Map.html#v%3AinsertWith"
2863>insertWith</A
2864></TT
2865>, but the combining function is applied strictly.
2866</TD
2867></TR
2868><TR
2869><TD CLASS="s15"
2870></TD
2871></TR
2872><TR
2873><TD CLASS="decl"
2874><A NAME="v%3AinsertWithKey%27"
2875></A
2876><B
2877>insertWithKey'</B
2878> :: <A HREF="Prelude.html#t%3AOrd"
2879>Ord</A
2880> k =&gt; (k -&gt; a -&gt; a -&gt; a) -&gt; k -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
2881>Map</A
2882> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
2883>Map</A
2884> k a</TD
2885></TR
2886><TR
2887><TD CLASS="doc"
2888>Same as <TT
2889><A HREF="Data-Map.html#v%3AinsertWithKey"
2890>insertWithKey</A
2891></TT
2892>, but the combining function is applied strictly.
2893</TD
2894></TR
2895><TR
2896><TD CLASS="s15"
2897></TD
2898></TR
2899><TR
2900><TD CLASS="section2"
2901><A NAME="6"
2902>Delete/Update
2903</A
2904></TD
2905></TR
2906><TR
2907><TD CLASS="s15"
2908></TD
2909></TR
2910><TR
2911><TD CLASS="decl"
2912><A NAME="v%3Adelete"
2913></A
2914><B
2915>delete</B
2916> :: <A HREF="Prelude.html#t%3AOrd"
2917>Ord</A
2918> k =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
2919>Map</A
2920> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
2921>Map</A
2922> k a</TD
2923></TR
2924><TR
2925><TD CLASS="doc"
2926><P
2927><EM
2928>O(log n)</EM
2929>. Delete a key and its value from the map. When the key is not
2930 a member of the map, the original map is returned.
2931</P
2932><PRE
2933> delete 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;b&quot;
2934 delete 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
2935 delete 5 empty                         == empty
2936</PRE
2937></TD
2938></TR
2939><TR
2940><TD CLASS="s15"
2941></TD
2942></TR
2943><TR
2944><TD CLASS="decl"
2945><A NAME="v%3Aadjust"
2946></A
2947><B
2948>adjust</B
2949> :: <A HREF="Prelude.html#t%3AOrd"
2950>Ord</A
2951> k =&gt; (a -&gt; a) -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
2952>Map</A
2953> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
2954>Map</A
2955> k a</TD
2956></TR
2957><TR
2958><TD CLASS="doc"
2959><P
2960><EM
2961>O(log n)</EM
2962>. Update a value at a specific key with the result of the provided function.
2963 When the key is not
2964 a member of the map, the original map is returned.
2965</P
2966><PRE
2967> adjust (&quot;new &quot; ++) 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;new a&quot;)]
2968 adjust (&quot;new &quot; ++) 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
2969 adjust (&quot;new &quot; ++) 7 empty                         == empty
2970</PRE
2971></TD
2972></TR
2973><TR
2974><TD CLASS="s15"
2975></TD
2976></TR
2977><TR
2978><TD CLASS="decl"
2979><A NAME="v%3AadjustWithKey"
2980></A
2981><B
2982>adjustWithKey</B
2983> :: <A HREF="Prelude.html#t%3AOrd"
2984>Ord</A
2985> k =&gt; (k -&gt; a -&gt; a) -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
2986>Map</A
2987> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
2988>Map</A
2989> k a</TD
2990></TR
2991><TR
2992><TD CLASS="doc"
2993><P
2994><EM
2995>O(log n)</EM
2996>. Adjust a value at a specific key. When the key is not
2997 a member of the map, the original map is returned.
2998</P
2999><PRE
3000> let f key x = (show key) ++ &quot;:new &quot; ++ x
3001 adjustWithKey f 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;5:new a&quot;)]
3002 adjustWithKey f 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
3003 adjustWithKey f 7 empty                         == empty
3004</PRE
3005></TD
3006></TR
3007><TR
3008><TD CLASS="s15"
3009></TD
3010></TR
3011><TR
3012><TD CLASS="decl"
3013><A NAME="v%3Aupdate"
3014></A
3015><B
3016>update</B
3017> :: <A HREF="Prelude.html#t%3AOrd"
3018>Ord</A
3019> k =&gt; (a -&gt; <A HREF="Prelude.html#t%3AMaybe"
3020>Maybe</A
3021> a) -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
3022>Map</A
3023> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3024>Map</A
3025> k a</TD
3026></TR
3027><TR
3028><TD CLASS="doc"
3029><P
3030><EM
3031>O(log n)</EM
3032>. The expression (<TT
3033><TT
3034><A HREF="Data-Map.html#v%3Aupdate"
3035>update</A
3036></TT
3037> f k map</TT
3038>) updates the value <TT
3039>x</TT
3040>
3041 at <TT
3042>k</TT
3043> (if it is in the map). If (<TT
3044>f x</TT
3045>) is <TT
3046><A HREF="Prelude.html#v%3ANothing"
3047>Nothing</A
3048></TT
3049>, the element is
3050 deleted. If it is (<TT
3051><TT
3052><A HREF="Prelude.html#v%3AJust"
3053>Just</A
3054></TT
3055> y</TT
3056>), the key <TT
3057>k</TT
3058> is bound to the new value <TT
3059>y</TT
3060>.
3061</P
3062><PRE
3063> let f x = if x == &quot;a&quot; then Just &quot;new a&quot; else Nothing
3064 update f 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;new a&quot;)]
3065 update f 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
3066 update f 3 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;a&quot;
3067</PRE
3068></TD
3069></TR
3070><TR
3071><TD CLASS="s15"
3072></TD
3073></TR
3074><TR
3075><TD CLASS="decl"
3076><A NAME="v%3AupdateWithKey"
3077></A
3078><B
3079>updateWithKey</B
3080> :: <A HREF="Prelude.html#t%3AOrd"
3081>Ord</A
3082> k =&gt; (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
3083>Maybe</A
3084> a) -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
3085>Map</A
3086> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3087>Map</A
3088> k a</TD
3089></TR
3090><TR
3091><TD CLASS="doc"
3092><P
3093><EM
3094>O(log n)</EM
3095>. The expression (<TT
3096><TT
3097><A HREF="Data-Map.html#v%3AupdateWithKey"
3098>updateWithKey</A
3099></TT
3100> f k map</TT
3101>) updates the
3102 value <TT
3103>x</TT
3104> at <TT
3105>k</TT
3106> (if it is in the map). If (<TT
3107>f k x</TT
3108>) is <TT
3109><A HREF="Prelude.html#v%3ANothing"
3110>Nothing</A
3111></TT
3112>,
3113 the element is deleted. If it is (<TT
3114><TT
3115><A HREF="Prelude.html#v%3AJust"
3116>Just</A
3117></TT
3118> y</TT
3119>), the key <TT
3120>k</TT
3121> is bound
3122 to the new value <TT
3123>y</TT
3124>.
3125</P
3126><PRE
3127> let f k x = if x == &quot;a&quot; then Just ((show k) ++ &quot;:new a&quot;) else Nothing
3128 updateWithKey f 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;5:new a&quot;)]
3129 updateWithKey f 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
3130 updateWithKey f 3 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;a&quot;
3131</PRE
3132></TD
3133></TR
3134><TR
3135><TD CLASS="s15"
3136></TD
3137></TR
3138><TR
3139><TD CLASS="decl"
3140><A NAME="v%3AupdateLookupWithKey"
3141></A
3142><B
3143>updateLookupWithKey</B
3144> :: <A HREF="Prelude.html#t%3AOrd"
3145>Ord</A
3146> k =&gt; (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
3147>Maybe</A
3148> a) -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
3149>Map</A
3150> k a -&gt; (<A HREF="Prelude.html#t%3AMaybe"
3151>Maybe</A
3152> a, <A HREF="Data-Map.html#t%3AMap"
3153>Map</A
3154> k a)</TD
3155></TR
3156><TR
3157><TD CLASS="doc"
3158><P
3159><EM
3160>O(log n)</EM
3161>. Lookup and update. See also <TT
3162><A HREF="Data-Map.html#v%3AupdateWithKey"
3163>updateWithKey</A
3164></TT
3165>.
3166 The function returns changed value, if it is updated.
3167 Returns the original key value if the map entry is deleted.
3168</P
3169><PRE
3170> let f k x = if x == &quot;a&quot; then Just ((show k) ++ &quot;:new a&quot;) else Nothing
3171 updateLookupWithKey f 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (Just &quot;5:new a&quot;, fromList [(3, &quot;b&quot;), (5, &quot;5:new a&quot;)])
3172 updateLookupWithKey f 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (Nothing,  fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)])
3173 updateLookupWithKey f 3 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (Just &quot;b&quot;, singleton 5 &quot;a&quot;)
3174</PRE
3175></TD
3176></TR
3177><TR
3178><TD CLASS="s15"
3179></TD
3180></TR
3181><TR
3182><TD CLASS="decl"
3183><A NAME="v%3Aalter"
3184></A
3185><B
3186>alter</B
3187> :: <A HREF="Prelude.html#t%3AOrd"
3188>Ord</A
3189> k =&gt; (<A HREF="Prelude.html#t%3AMaybe"
3190>Maybe</A
3191> a -&gt; <A HREF="Prelude.html#t%3AMaybe"
3192>Maybe</A
3193> a) -&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
3194>Map</A
3195> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3196>Map</A
3197> k a</TD
3198></TR
3199><TR
3200><TD CLASS="doc"
3201><P
3202><EM
3203>O(log n)</EM
3204>. The expression (<TT
3205><TT
3206><A HREF="Data-Map.html#v%3Aalter"
3207>alter</A
3208></TT
3209> f k map</TT
3210>) alters the value <TT
3211>x</TT
3212> at <TT
3213>k</TT
3214>, or absence thereof.
3215 <TT
3216><A HREF="Data-Map.html#v%3Aalter"
3217>alter</A
3218></TT
3219> can be used to insert, delete, or update a value in a <TT
3220><A HREF="Data-Map.html#t%3AMap"
3221>Map</A
3222></TT
3223>.
3224 In short : <TT
3225><TT
3226><A HREF="Data-Map.html#v%3Alookup"
3227>lookup</A
3228></TT
3229> k (<TT
3230><A HREF="Data-Map.html#v%3Aalter"
3231>alter</A
3232></TT
3233> f k m) = f (<TT
3234><A HREF="Data-Map.html#v%3Alookup"
3235>lookup</A
3236></TT
3237> k m)</TT
3238>.
3239</P
3240><PRE
3241> let f _ = Nothing
3242 alter f 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
3243 alter f 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;b&quot;
3244
3245 let f _ = Just &quot;c&quot;
3246 alter f 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;), (7, &quot;c&quot;)]
3247 alter f 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;c&quot;)]
3248</PRE
3249></TD
3250></TR
3251><TR
3252><TD CLASS="s15"
3253></TD
3254></TR
3255><TR
3256><TD CLASS="section1"
3257><A NAME="7"
3258>Combine
3259</A
3260></TD
3261></TR
3262><TR
3263><TD CLASS="s15"
3264></TD
3265></TR
3266><TR
3267><TD CLASS="section2"
3268><A NAME="8"
3269>Union
3270</A
3271></TD
3272></TR
3273><TR
3274><TD CLASS="s15"
3275></TD
3276></TR
3277><TR
3278><TD CLASS="decl"
3279><A NAME="v%3Aunion"
3280></A
3281><B
3282>union</B
3283> :: <A HREF="Prelude.html#t%3AOrd"
3284>Ord</A
3285> k =&gt; <A HREF="Data-Map.html#t%3AMap"
3286>Map</A
3287> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3288>Map</A
3289> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3290>Map</A
3291> k a</TD
3292></TR
3293><TR
3294><TD CLASS="doc"
3295><P
3296><EM
3297>O(n+m)</EM
3298>.
3299 The expression (<TT
3300><TT
3301><A HREF="Data-Map.html#v%3Aunion"
3302>union</A
3303></TT
3304> t1 t2</TT
3305>) takes the left-biased union of <TT
3306>t1</TT
3307> and <TT
3308>t2</TT
3309>.
3310 It prefers <TT
3311>t1</TT
3312> when duplicate keys are encountered,
3313 i.e. (<TT
3314><TT
3315><A HREF="Data-Map.html#v%3Aunion"
3316>union</A
3317></TT
3318> == <TT
3319><A HREF="Data-Map.html#v%3AunionWith"
3320>unionWith</A
3321></TT
3322> <TT
3323><A HREF="Prelude.html#v%3Aconst"
3324>const</A
3325></TT
3326></TT
3327>).
3328 The implementation uses the efficient <EM
3329>hedge-union</EM
3330> algorithm.
3331 Hedge-union is more efficient on (bigset `<TT
3332><A HREF="Data-Map.html#v%3Aunion"
3333>union</A
3334></TT
3335>` smallset).
3336</P
3337><PRE
3338> union (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;), (7, &quot;C&quot;)]
3339</PRE
3340></TD
3341></TR
3342><TR
3343><TD CLASS="s15"
3344></TD
3345></TR
3346><TR
3347><TD CLASS="decl"
3348><A NAME="v%3AunionWith"
3349></A
3350><B
3351>unionWith</B
3352> :: <A HREF="Prelude.html#t%3AOrd"
3353>Ord</A
3354> k =&gt; (a -&gt; a -&gt; a) -&gt; <A HREF="Data-Map.html#t%3AMap"
3355>Map</A
3356> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3357>Map</A
3358> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3359>Map</A
3360> k a</TD
3361></TR
3362><TR
3363><TD CLASS="doc"
3364><P
3365><EM
3366>O(n+m)</EM
3367>. Union with a combining function. The implementation uses the efficient <EM
3368>hedge-union</EM
3369> algorithm.
3370</P
3371><PRE
3372> unionWith (++) (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;aA&quot;), (7, &quot;C&quot;)]
3373</PRE
3374></TD
3375></TR
3376><TR
3377><TD CLASS="s15"
3378></TD
3379></TR
3380><TR
3381><TD CLASS="decl"
3382><A NAME="v%3AunionWithKey"
3383></A
3384><B
3385>unionWithKey</B
3386> :: <A HREF="Prelude.html#t%3AOrd"
3387>Ord</A
3388> k =&gt; (k -&gt; a -&gt; a -&gt; a) -&gt; <A HREF="Data-Map.html#t%3AMap"
3389>Map</A
3390> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3391>Map</A
3392> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3393>Map</A
3394> k a</TD
3395></TR
3396><TR
3397><TD CLASS="doc"
3398><P
3399><EM
3400>O(n+m)</EM
3401>.
3402 Union with a combining function. The implementation uses the efficient <EM
3403>hedge-union</EM
3404> algorithm.
3405 Hedge-union is more efficient on (bigset `<TT
3406><A HREF="Data-Map.html#v%3Aunion"
3407>union</A
3408></TT
3409>` smallset).
3410</P
3411><PRE
3412> let f key new_value old_value = (show key) ++ &quot;:&quot; ++ new_value ++ &quot;|&quot; ++ old_value
3413 unionWithKey f (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;5:a|A&quot;), (7, &quot;C&quot;)]
3414</PRE
3415></TD
3416></TR
3417><TR
3418><TD CLASS="s15"
3419></TD
3420></TR
3421><TR
3422><TD CLASS="decl"
3423><A NAME="v%3Aunions"
3424></A
3425><B
3426>unions</B
3427> :: <A HREF="Prelude.html#t%3AOrd"
3428>Ord</A
3429> k =&gt; [<A HREF="Data-Map.html#t%3AMap"
3430>Map</A
3431> k a] -&gt; <A HREF="Data-Map.html#t%3AMap"
3432>Map</A
3433> k a</TD
3434></TR
3435><TR
3436><TD CLASS="doc"
3437><P
3438>The union of a list of maps:
3439   (<TT
3440><TT
3441><A HREF="Data-Map.html#v%3Aunions"
3442>unions</A
3443></TT
3444> == <TT
3445><A HREF="Prelude.html#v%3Afoldl"
3446>foldl</A
3447></TT
3448> <TT
3449><A HREF="Data-Map.html#v%3Aunion"
3450>union</A
3451></TT
3452> <TT
3453><A HREF="Data-Map.html#v%3Aempty"
3454>empty</A
3455></TT
3456></TT
3457>).
3458</P
3459><PRE
3460> unions [(fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]), (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]), (fromList [(5, &quot;A3&quot;), (3, &quot;B3&quot;)])]
3461     == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;), (7, &quot;C&quot;)]
3462 unions [(fromList [(5, &quot;A3&quot;), (3, &quot;B3&quot;)]), (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]), (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)])]
3463     == fromList [(3, &quot;B3&quot;), (5, &quot;A3&quot;), (7, &quot;C&quot;)]
3464</PRE
3465></TD
3466></TR
3467><TR
3468><TD CLASS="s15"
3469></TD
3470></TR
3471><TR
3472><TD CLASS="decl"
3473><A NAME="v%3AunionsWith"
3474></A
3475><B
3476>unionsWith</B
3477> :: <A HREF="Prelude.html#t%3AOrd"
3478>Ord</A
3479> k =&gt; (a -&gt; a -&gt; a) -&gt; [<A HREF="Data-Map.html#t%3AMap"
3480>Map</A
3481> k a] -&gt; <A HREF="Data-Map.html#t%3AMap"
3482>Map</A
3483> k a</TD
3484></TR
3485><TR
3486><TD CLASS="doc"
3487><P
3488>The union of a list of maps, with a combining operation:
3489   (<TT
3490><TT
3491><A HREF="Data-Map.html#v%3AunionsWith"
3492>unionsWith</A
3493></TT
3494> f == <TT
3495><A HREF="Prelude.html#v%3Afoldl"
3496>foldl</A
3497></TT
3498> (<TT
3499><A HREF="Data-Map.html#v%3AunionWith"
3500>unionWith</A
3501></TT
3502> f) <TT
3503><A HREF="Data-Map.html#v%3Aempty"
3504>empty</A
3505></TT
3506></TT
3507>).
3508</P
3509><PRE
3510> unionsWith (++) [(fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]), (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]), (fromList [(5, &quot;A3&quot;), (3, &quot;B3&quot;)])]
3511     == fromList [(3, &quot;bB3&quot;), (5, &quot;aAA3&quot;), (7, &quot;C&quot;)]
3512</PRE
3513></TD
3514></TR
3515><TR
3516><TD CLASS="s15"
3517></TD
3518></TR
3519><TR
3520><TD CLASS="section2"
3521><A NAME="9"
3522>Difference
3523</A
3524></TD
3525></TR
3526><TR
3527><TD CLASS="s15"
3528></TD
3529></TR
3530><TR
3531><TD CLASS="decl"
3532><A NAME="v%3Adifference"
3533></A
3534><B
3535>difference</B
3536> :: <A HREF="Prelude.html#t%3AOrd"
3537>Ord</A
3538> k =&gt; <A HREF="Data-Map.html#t%3AMap"
3539>Map</A
3540> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3541>Map</A
3542> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
3543>Map</A
3544> k a</TD
3545></TR
3546><TR
3547><TD CLASS="doc"
3548><P
3549><EM
3550>O(n+m)</EM
3551>. Difference of two maps.
3552 Return elements of the first map not existing in the second map.
3553 The implementation uses an efficient <EM
3554>hedge</EM
3555> algorithm comparable with <EM
3556>hedge-union</EM
3557>.
3558</P
3559><PRE
3560> difference (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]) == singleton 3 &quot;b&quot;
3561</PRE
3562></TD
3563></TR
3564><TR
3565><TD CLASS="s15"
3566></TD
3567></TR
3568><TR
3569><TD CLASS="decl"
3570><A NAME="v%3AdifferenceWith"
3571></A
3572><B
3573>differenceWith</B
3574> :: <A HREF="Prelude.html#t%3AOrd"
3575>Ord</A
3576> k =&gt; (a -&gt; b -&gt; <A HREF="Prelude.html#t%3AMaybe"
3577>Maybe</A
3578> a) -&gt; <A HREF="Data-Map.html#t%3AMap"
3579>Map</A
3580> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3581>Map</A
3582> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
3583>Map</A
3584> k a</TD
3585></TR
3586><TR
3587><TD CLASS="doc"
3588><P
3589><EM
3590>O(n+m)</EM
3591>. Difference with a combining function.
3592 When two equal keys are
3593 encountered, the combining function is applied to the values of these keys.
3594 If it returns <TT
3595><A HREF="Prelude.html#v%3ANothing"
3596>Nothing</A
3597></TT
3598>, the element is discarded (proper set difference). If
3599 it returns (<TT
3600><TT
3601><A HREF="Prelude.html#v%3AJust"
3602>Just</A
3603></TT
3604> y</TT
3605>), the element is updated with a new value <TT
3606>y</TT
3607>.
3608 The implementation uses an efficient <EM
3609>hedge</EM
3610> algorithm comparable with <EM
3611>hedge-union</EM
3612>.
3613</P
3614><PRE
3615> let f al ar = if al == &quot;b&quot; then Just (al ++ &quot;:&quot; ++ ar) else Nothing
3616 differenceWith f (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (3, &quot;B&quot;), (7, &quot;C&quot;)])
3617     == singleton 3 &quot;b:B&quot;
3618</PRE
3619></TD
3620></TR
3621><TR
3622><TD CLASS="s15"
3623></TD
3624></TR
3625><TR
3626><TD CLASS="decl"
3627><A NAME="v%3AdifferenceWithKey"
3628></A
3629><B
3630>differenceWithKey</B
3631> :: <A HREF="Prelude.html#t%3AOrd"
3632>Ord</A
3633> k =&gt; (k -&gt; a -&gt; b -&gt; <A HREF="Prelude.html#t%3AMaybe"
3634>Maybe</A
3635> a) -&gt; <A HREF="Data-Map.html#t%3AMap"
3636>Map</A
3637> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3638>Map</A
3639> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
3640>Map</A
3641> k a</TD
3642></TR
3643><TR
3644><TD CLASS="doc"
3645><P
3646><EM
3647>O(n+m)</EM
3648>. Difference with a combining function. When two equal keys are
3649 encountered, the combining function is applied to the key and both values.
3650 If it returns <TT
3651><A HREF="Prelude.html#v%3ANothing"
3652>Nothing</A
3653></TT
3654>, the element is discarded (proper set difference). If
3655 it returns (<TT
3656><TT
3657><A HREF="Prelude.html#v%3AJust"
3658>Just</A
3659></TT
3660> y</TT
3661>), the element is updated with a new value <TT
3662>y</TT
3663>.
3664 The implementation uses an efficient <EM
3665>hedge</EM
3666> algorithm comparable with <EM
3667>hedge-union</EM
3668>.
3669</P
3670><PRE
3671> let f k al ar = if al == &quot;b&quot; then Just ((show k) ++ &quot;:&quot; ++ al ++ &quot;|&quot; ++ ar) else Nothing
3672 differenceWithKey f (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (3, &quot;B&quot;), (10, &quot;C&quot;)])
3673     == singleton 3 &quot;3:b|B&quot;
3674</PRE
3675></TD
3676></TR
3677><TR
3678><TD CLASS="s15"
3679></TD
3680></TR
3681><TR
3682><TD CLASS="section2"
3683><A NAME="10"
3684>Intersection
3685</A
3686></TD
3687></TR
3688><TR
3689><TD CLASS="s15"
3690></TD
3691></TR
3692><TR
3693><TD CLASS="decl"
3694><A NAME="v%3Aintersection"
3695></A
3696><B
3697>intersection</B
3698> :: <A HREF="Prelude.html#t%3AOrd"
3699>Ord</A
3700> k =&gt; <A HREF="Data-Map.html#t%3AMap"
3701>Map</A
3702> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3703>Map</A
3704> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
3705>Map</A
3706> k a</TD
3707></TR
3708><TR
3709><TD CLASS="doc"
3710><P
3711><EM
3712>O(n+m)</EM
3713>. Intersection of two maps.
3714 Return data in the first map for the keys existing in both maps.
3715 (<TT
3716><TT
3717><A HREF="Data-Map.html#v%3Aintersection"
3718>intersection</A
3719></TT
3720> m1 m2 == <TT
3721><A HREF="Data-Map.html#v%3AintersectionWith"
3722>intersectionWith</A
3723></TT
3724> <TT
3725><A HREF="Prelude.html#v%3Aconst"
3726>const</A
3727></TT
3728> m1 m2</TT
3729>).
3730</P
3731><PRE
3732> intersection (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]) == singleton 5 &quot;a&quot;
3733</PRE
3734></TD
3735></TR
3736><TR
3737><TD CLASS="s15"
3738></TD
3739></TR
3740><TR
3741><TD CLASS="decl"
3742><A NAME="v%3AintersectionWith"
3743></A
3744><B
3745>intersectionWith</B
3746> :: <A HREF="Prelude.html#t%3AOrd"
3747>Ord</A
3748> k =&gt; (a -&gt; b -&gt; c) -&gt; <A HREF="Data-Map.html#t%3AMap"
3749>Map</A
3750> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3751>Map</A
3752> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
3753>Map</A
3754> k c</TD
3755></TR
3756><TR
3757><TD CLASS="doc"
3758><P
3759><EM
3760>O(n+m)</EM
3761>. Intersection with a combining function.
3762</P
3763><PRE
3764> intersectionWith (++) (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]) == singleton 5 &quot;aA&quot;
3765</PRE
3766></TD
3767></TR
3768><TR
3769><TD CLASS="s15"
3770></TD
3771></TR
3772><TR
3773><TD CLASS="decl"
3774><A NAME="v%3AintersectionWithKey"
3775></A
3776><B
3777>intersectionWithKey</B
3778> :: <A HREF="Prelude.html#t%3AOrd"
3779>Ord</A
3780> k =&gt; (k -&gt; a -&gt; b -&gt; c) -&gt; <A HREF="Data-Map.html#t%3AMap"
3781>Map</A
3782> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3783>Map</A
3784> k b -&gt; <A HREF="Data-Map.html#t%3AMap"
3785>Map</A
3786> k c</TD
3787></TR
3788><TR
3789><TD CLASS="doc"
3790><P
3791><EM
3792>O(n+m)</EM
3793>. Intersection with a combining function.
3794 Intersection is more efficient on (bigset `<TT
3795><A HREF="Data-Map.html#v%3Aintersection"
3796>intersection</A
3797></TT
3798>` smallset).
3799</P
3800><PRE
3801> let f k al ar = (show k) ++ &quot;:&quot; ++ al ++ &quot;|&quot; ++ ar
3802 intersectionWithKey f (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]) == singleton 5 &quot;5:a|A&quot;
3803</PRE
3804></TD
3805></TR
3806><TR
3807><TD CLASS="s15"
3808></TD
3809></TR
3810><TR
3811><TD CLASS="section1"
3812><A NAME="11"
3813>Traversal
3814</A
3815></TD
3816></TR
3817><TR
3818><TD CLASS="s15"
3819></TD
3820></TR
3821><TR
3822><TD CLASS="section2"
3823><A NAME="12"
3824>Map
3825</A
3826></TD
3827></TR
3828><TR
3829><TD CLASS="s15"
3830></TD
3831></TR
3832><TR
3833><TD CLASS="decl"
3834><A NAME="v%3Amap"
3835></A
3836><B
3837>map</B
3838> :: (a -&gt; b) -&gt; <A HREF="Data-Map.html#t%3AMap"
3839>Map</A
3840> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3841>Map</A
3842> k b</TD
3843></TR
3844><TR
3845><TD CLASS="doc"
3846><P
3847><EM
3848>O(n)</EM
3849>. Map a function over all values in the map.
3850</P
3851><PRE
3852> map (++ &quot;x&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;bx&quot;), (5, &quot;ax&quot;)]
3853</PRE
3854></TD
3855></TR
3856><TR
3857><TD CLASS="s15"
3858></TD
3859></TR
3860><TR
3861><TD CLASS="decl"
3862><A NAME="v%3AmapWithKey"
3863></A
3864><B
3865>mapWithKey</B
3866> :: (k -&gt; a -&gt; b) -&gt; <A HREF="Data-Map.html#t%3AMap"
3867>Map</A
3868> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
3869>Map</A
3870> k b</TD
3871></TR
3872><TR
3873><TD CLASS="doc"
3874><P
3875><EM
3876>O(n)</EM
3877>. Map a function over all values in the map.
3878</P
3879><PRE
3880> let f key x = (show key) ++ &quot;:&quot; ++ x
3881 mapWithKey f (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;3:b&quot;), (5, &quot;5:a&quot;)]
3882</PRE
3883></TD
3884></TR
3885><TR
3886><TD CLASS="s15"
3887></TD
3888></TR
3889><TR
3890><TD CLASS="decl"
3891><A NAME="v%3AmapAccum"
3892></A
3893><B
3894>mapAccum</B
3895> :: (a -&gt; b -&gt; (a, c)) -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
3896>Map</A
3897> k b -&gt; (a, <A HREF="Data-Map.html#t%3AMap"
3898>Map</A
3899> k c)</TD
3900></TR
3901><TR
3902><TD CLASS="doc"
3903><P
3904><EM
3905>O(n)</EM
3906>. The function <TT
3907><A HREF="Data-Map.html#v%3AmapAccum"
3908>mapAccum</A
3909></TT
3910> threads an accumulating
3911 argument through the map in ascending order of keys.
3912</P
3913><PRE
3914> let f a b = (a ++ b, b ++ &quot;X&quot;)
3915 mapAccum f &quot;Everything: &quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (&quot;Everything: ba&quot;, fromList [(3, &quot;bX&quot;), (5, &quot;aX&quot;)])
3916</PRE
3917></TD
3918></TR
3919><TR
3920><TD CLASS="s15"
3921></TD
3922></TR
3923><TR
3924><TD CLASS="decl"
3925><A NAME="v%3AmapAccumWithKey"
3926></A
3927><B
3928>mapAccumWithKey</B
3929> :: (a -&gt; k -&gt; b -&gt; (a, c)) -&gt; a -&gt; <A HREF="Data-Map.html#t%3AMap"
3930>Map</A
3931> k b -&gt; (a, <A HREF="Data-Map.html#t%3AMap"
3932>Map</A
3933> k c)</TD
3934></TR
3935><TR
3936><TD CLASS="doc"
3937><P
3938><EM
3939>O(n)</EM
3940>. The function <TT
3941><A HREF="Data-Map.html#v%3AmapAccumWithKey"
3942>mapAccumWithKey</A
3943></TT
3944> threads an accumulating
3945 argument through the map in ascending order of keys.
3946</P
3947><PRE
3948> let f a k b = (a ++ &quot; &quot; ++ (show k) ++ &quot;-&quot; ++ b, b ++ &quot;X&quot;)
3949 mapAccumWithKey f &quot;Everything:&quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (&quot;Everything: 3-b 5-a&quot;, fromList [(3, &quot;bX&quot;), (5, &quot;aX&quot;)])
3950</PRE
3951></TD
3952></TR
3953><TR
3954><TD CLASS="s15"
3955></TD
3956></TR
3957><TR
3958><TD CLASS="decl"
3959><A NAME="v%3AmapKeys"
3960></A
3961><B
3962>mapKeys</B
3963> :: <A HREF="Prelude.html#t%3AOrd"
3964>Ord</A
3965> k2 =&gt; (k1 -&gt; k2) -&gt; <A HREF="Data-Map.html#t%3AMap"
3966>Map</A
3967> k1 a -&gt; <A HREF="Data-Map.html#t%3AMap"
3968>Map</A
3969> k2 a</TD
3970></TR
3971><TR
3972><TD CLASS="doc"
3973><P
3974><EM
3975>O(n*log n)</EM
3976>.
3977 <TT
3978><TT
3979><A HREF="Data-Map.html#v%3AmapKeys"
3980>mapKeys</A
3981></TT
3982> f s</TT
3983> is the map obtained by applying <TT
3984>f</TT
3985> to each key of <TT
3986>s</TT
3987>.
3988</P
3989><P
3990>The size of the result may be smaller if <TT
3991>f</TT
3992> maps two or more distinct
3993 keys to the same new key.  In this case the value at the smallest of
3994 these keys is retained.
3995</P
3996><PRE
3997> mapKeys (+ 1) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])                        == fromList [(4, &quot;b&quot;), (6, &quot;a&quot;)]
3998 mapKeys (\ _ -&gt; 1) (fromList [(1,&quot;b&quot;), (2,&quot;a&quot;), (3,&quot;d&quot;), (4,&quot;c&quot;)]) == singleton 1 &quot;c&quot;
3999 mapKeys (\ _ -&gt; 3) (fromList [(1,&quot;b&quot;), (2,&quot;a&quot;), (3,&quot;d&quot;), (4,&quot;c&quot;)]) == singleton 3 &quot;c&quot;
4000</PRE
4001></TD
4002></TR
4003><TR
4004><TD CLASS="s15"
4005></TD
4006></TR
4007><TR
4008><TD CLASS="decl"
4009><A NAME="v%3AmapKeysWith"
4010></A
4011><B
4012>mapKeysWith</B
4013> :: <A HREF="Prelude.html#t%3AOrd"
4014>Ord</A
4015> k2 =&gt; (a -&gt; a -&gt; a) -&gt; (k1 -&gt; k2) -&gt; <A HREF="Data-Map.html#t%3AMap"
4016>Map</A
4017> k1 a -&gt; <A HREF="Data-Map.html#t%3AMap"
4018>Map</A
4019> k2 a</TD
4020></TR
4021><TR
4022><TD CLASS="doc"
4023><P
4024><EM
4025>O(n*log n)</EM
4026>.
4027 <TT
4028><TT
4029><A HREF="Data-Map.html#v%3AmapKeysWith"
4030>mapKeysWith</A
4031></TT
4032> c f s</TT
4033> is the map obtained by applying <TT
4034>f</TT
4035> to each key of <TT
4036>s</TT
4037>.
4038</P
4039><P
4040>The size of the result may be smaller if <TT
4041>f</TT
4042> maps two or more distinct
4043 keys to the same new key.  In this case the associated values will be
4044 combined using <TT
4045>c</TT
4046>.
4047</P
4048><PRE
4049> mapKeysWith (++) (\ _ -&gt; 1) (fromList [(1,&quot;b&quot;), (2,&quot;a&quot;), (3,&quot;d&quot;), (4,&quot;c&quot;)]) == singleton 1 &quot;cdab&quot;
4050 mapKeysWith (++) (\ _ -&gt; 3) (fromList [(1,&quot;b&quot;), (2,&quot;a&quot;), (3,&quot;d&quot;), (4,&quot;c&quot;)]) == singleton 3 &quot;cdab&quot;
4051</PRE
4052></TD
4053></TR
4054><TR
4055><TD CLASS="s15"
4056></TD
4057></TR
4058><TR
4059><TD CLASS="decl"
4060><A NAME="v%3AmapKeysMonotonic"
4061></A
4062><B
4063>mapKeysMonotonic</B
4064> :: (k1 -&gt; k2) -&gt; <A HREF="Data-Map.html#t%3AMap"
4065>Map</A
4066> k1 a -&gt; <A HREF="Data-Map.html#t%3AMap"
4067>Map</A
4068> k2 a</TD
4069></TR
4070><TR
4071><TD CLASS="doc"
4072><P
4073><EM
4074>O(n)</EM
4075>.
4076 <TT
4077><TT
4078><A HREF="Data-Map.html#v%3AmapKeysMonotonic"
4079>mapKeysMonotonic</A
4080></TT
4081> f s == <TT
4082><A HREF="Data-Map.html#v%3AmapKeys"
4083>mapKeys</A
4084></TT
4085> f s</TT
4086>, but works only when <TT
4087>f</TT
4088>
4089 is strictly monotonic.
4090 That is, for any values <TT
4091>x</TT
4092> and <TT
4093>y</TT
4094>, if <TT
4095>x</TT
4096> &lt; <TT
4097>y</TT
4098> then <TT
4099>f x</TT
4100> &lt; <TT
4101>f y</TT
4102>.
4103 <EM
4104>The precondition is not checked.</EM
4105>
4106 Semi-formally, we have:
4107</P
4108><PRE
4109> and [x &lt; y ==&gt; f x &lt; f y | x &lt;- ls, y &lt;- ls]
4110                     ==&gt; mapKeysMonotonic f s == mapKeys f s
4111     where ls = keys s
4112</PRE
4113><P
4114>This means that <TT
4115>f</TT
4116> maps distinct original keys to distinct resulting keys.
4117 This function has better performance than <TT
4118><A HREF="Data-Map.html#v%3AmapKeys"
4119>mapKeys</A
4120></TT
4121>.
4122</P
4123><PRE
4124> mapKeysMonotonic (\ k -&gt; k * 2) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(6, &quot;b&quot;), (10, &quot;a&quot;)]
4125 valid (mapKeysMonotonic (\ k -&gt; k * 2) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])) == True
4126 valid (mapKeysMonotonic (\ _ -&gt; 1)     (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])) == False
4127</PRE
4128></TD
4129></TR
4130><TR
4131><TD CLASS="s15"
4132></TD
4133></TR
4134><TR
4135><TD CLASS="section2"
4136><A NAME="13"
4137>Fold
4138</A
4139></TD
4140></TR
4141><TR
4142><TD CLASS="s15"
4143></TD
4144></TR
4145><TR
4146><TD CLASS="decl"
4147><A NAME="v%3Afold"
4148></A
4149><B
4150>fold</B
4151> :: (a -&gt; b -&gt; b) -&gt; b -&gt; <A HREF="Data-Map.html#t%3AMap"
4152>Map</A
4153> k a -&gt; b</TD
4154></TR
4155><TR
4156><TD CLASS="doc"
4157><P
4158><EM
4159>O(n)</EM
4160>. Fold the values in the map, such that
4161 <TT
4162><TT
4163><A HREF="Data-Map.html#v%3Afold"
4164>fold</A
4165></TT
4166> f z == <TT
4167><A HREF="Prelude.html#v%3Afoldr"
4168>foldr</A
4169></TT
4170> f z . <TT
4171><A HREF="Data-Map.html#v%3Aelems"
4172>elems</A
4173></TT
4174></TT
4175>.
4176 For example,
4177</P
4178><PRE
4179> elems map = fold (:) [] map
4180</PRE
4181><PRE
4182> let f a len = len + (length a)
4183 fold f 0 (fromList [(5,&quot;a&quot;), (3,&quot;bbb&quot;)]) == 4
4184</PRE
4185></TD
4186></TR
4187><TR
4188><TD CLASS="s15"
4189></TD
4190></TR
4191><TR
4192><TD CLASS="decl"
4193><A NAME="v%3AfoldWithKey"
4194></A
4195><B
4196>foldWithKey</B
4197> :: (k -&gt; a -&gt; b -&gt; b) -&gt; b -&gt; <A HREF="Data-Map.html#t%3AMap"
4198>Map</A
4199> k a -&gt; b</TD
4200></TR
4201><TR
4202><TD CLASS="doc"
4203><P
4204><EM
4205>O(n)</EM
4206>. Fold the keys and values in the map, such that
4207 <TT
4208><TT
4209><A HREF="Data-Map.html#v%3AfoldWithKey"
4210>foldWithKey</A
4211></TT
4212> f z == <TT
4213><A HREF="Prelude.html#v%3Afoldr"
4214>foldr</A
4215></TT
4216> (<TT
4217><A HREF="Prelude.html#v%3Auncurry"
4218>uncurry</A
4219></TT
4220> f) z . <TT
4221><A HREF="Data-Map.html#v%3AtoAscList"
4222>toAscList</A
4223></TT
4224></TT
4225>.
4226 For example,
4227</P
4228><PRE
4229> keys map = foldWithKey (\k x ks -&gt; k:ks) [] map
4230</PRE
4231><PRE
4232> let f k a result = result ++ &quot;(&quot; ++ (show k) ++ &quot;:&quot; ++ a ++ &quot;)&quot;
4233 foldWithKey f &quot;Map: &quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == &quot;Map: (5:a)(3:b)&quot;
4234</PRE
4235></TD
4236></TR
4237><TR
4238><TD CLASS="s15"
4239></TD
4240></TR
4241><TR
4242><TD CLASS="section1"
4243><A NAME="14"
4244>Conversion
4245</A
4246></TD
4247></TR
4248><TR
4249><TD CLASS="s15"
4250></TD
4251></TR
4252><TR
4253><TD CLASS="decl"
4254><A NAME="v%3Aelems"
4255></A
4256><B
4257>elems</B
4258> :: <A HREF="Data-Map.html#t%3AMap"
4259>Map</A
4260> k a -&gt; [a]</TD
4261></TR
4262><TR
4263><TD CLASS="doc"
4264><P
4265><EM
4266>O(n)</EM
4267>.
4268 Return all elements of the map in the ascending order of their keys.
4269</P
4270><PRE
4271> elems (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == [&quot;b&quot;,&quot;a&quot;]
4272 elems empty == []
4273</PRE
4274></TD
4275></TR
4276><TR
4277><TD CLASS="s15"
4278></TD
4279></TR
4280><TR
4281><TD CLASS="decl"
4282><A NAME="v%3Akeys"
4283></A
4284><B
4285>keys</B
4286> :: <A HREF="Data-Map.html#t%3AMap"
4287>Map</A
4288> k a -&gt; [k]</TD
4289></TR
4290><TR
4291><TD CLASS="doc"
4292><P
4293><EM
4294>O(n)</EM
4295>. Return all keys of the map in ascending order.
4296</P
4297><PRE
4298> keys (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == [3,5]
4299 keys empty == []
4300</PRE
4301></TD
4302></TR
4303><TR
4304><TD CLASS="s15"
4305></TD
4306></TR
4307><TR
4308><TD CLASS="decl"
4309><A NAME="v%3AkeysSet"
4310></A
4311><B
4312>keysSet</B
4313> :: <A HREF="Data-Map.html#t%3AMap"
4314>Map</A
4315> k a -&gt; Set k</TD
4316></TR
4317><TR
4318><TD CLASS="doc"
4319><P
4320><EM
4321>O(n)</EM
4322>. The set of all keys of the map.
4323</P
4324><PRE
4325> keysSet (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == Data.Set.fromList [3,5]
4326 keysSet empty == Data.Set.empty
4327</PRE
4328></TD
4329></TR
4330><TR
4331><TD CLASS="s15"
4332></TD
4333></TR
4334><TR
4335><TD CLASS="decl"
4336><A NAME="v%3Aassocs"
4337></A
4338><B
4339>assocs</B
4340> :: <A HREF="Data-Map.html#t%3AMap"
4341>Map</A
4342> k a -&gt; [(k, a)]</TD
4343></TR
4344><TR
4345><TD CLASS="doc"
4346><P
4347><EM
4348>O(n)</EM
4349>. Return all key/value pairs in the map in ascending key order.
4350</P
4351><PRE
4352> assocs (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == [(3,&quot;b&quot;), (5,&quot;a&quot;)]
4353 assocs empty == []
4354</PRE
4355></TD
4356></TR
4357><TR
4358><TD CLASS="s15"
4359></TD
4360></TR
4361><TR
4362><TD CLASS="section2"
4363><A NAME="15"
4364>Lists
4365</A
4366></TD
4367></TR
4368><TR
4369><TD CLASS="s15"
4370></TD
4371></TR
4372><TR
4373><TD CLASS="decl"
4374><A NAME="v%3AtoList"
4375></A
4376><B
4377>toList</B
4378> :: <A HREF="Data-Map.html#t%3AMap"
4379>Map</A
4380> k a -&gt; [(k, a)]</TD
4381></TR
4382><TR
4383><TD CLASS="doc"
4384><P
4385><EM
4386>O(n)</EM
4387>. Convert to a list of key/value pairs.
4388</P
4389><PRE
4390> toList (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == [(3,&quot;b&quot;), (5,&quot;a&quot;)]
4391 toList empty == []
4392</PRE
4393></TD
4394></TR
4395><TR
4396><TD CLASS="s15"
4397></TD
4398></TR
4399><TR
4400><TD CLASS="decl"
4401><A NAME="v%3AfromList"
4402></A
4403><B
4404>fromList</B
4405> :: <A HREF="Prelude.html#t%3AOrd"
4406>Ord</A
4407> k =&gt; [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
4408>Map</A
4409> k a</TD
4410></TR
4411><TR
4412><TD CLASS="doc"
4413><P
4414><EM
4415>O(n*log n)</EM
4416>. Build a map from a list of key/value pairs. See also <TT
4417><A HREF="Data-Map.html#v%3AfromAscList"
4418>fromAscList</A
4419></TT
4420>.
4421 If the list contains more than one value for the same key, the last value
4422 for the key is retained.
4423</P
4424><PRE
4425> fromList [] == empty
4426 fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (5, &quot;c&quot;)] == fromList [(5,&quot;c&quot;), (3,&quot;b&quot;)]
4427 fromList [(5,&quot;c&quot;), (3,&quot;b&quot;), (5, &quot;a&quot;)] == fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]
4428</PRE
4429></TD
4430></TR
4431><TR
4432><TD CLASS="s15"
4433></TD
4434></TR
4435><TR
4436><TD CLASS="decl"
4437><A NAME="v%3AfromListWith"
4438></A
4439><B
4440>fromListWith</B
4441> :: <A HREF="Prelude.html#t%3AOrd"
4442>Ord</A
4443> k =&gt; (a -&gt; a -&gt; a) -&gt; [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
4444>Map</A
4445> k a</TD
4446></TR
4447><TR
4448><TD CLASS="doc"
4449><P
4450><EM
4451>O(n*log n)</EM
4452>. Build a map from a list of key/value pairs with a combining function. See also <TT
4453><A HREF="Data-Map.html#v%3AfromAscListWith"
4454>fromAscListWith</A
4455></TT
4456>.
4457</P
4458><PRE
4459> fromListWith (++) [(5,&quot;a&quot;), (5,&quot;b&quot;), (3,&quot;b&quot;), (3,&quot;a&quot;), (5,&quot;a&quot;)] == fromList [(3, &quot;ab&quot;), (5, &quot;aba&quot;)]
4460 fromListWith (++) [] == empty
4461</PRE
4462></TD
4463></TR
4464><TR
4465><TD CLASS="s15"
4466></TD
4467></TR
4468><TR
4469><TD CLASS="decl"
4470><A NAME="v%3AfromListWithKey"
4471></A
4472><B
4473>fromListWithKey</B
4474> :: <A HREF="Prelude.html#t%3AOrd"
4475>Ord</A
4476> k =&gt; (k -&gt; a -&gt; a -&gt; a) -&gt; [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
4477>Map</A
4478> k a</TD
4479></TR
4480><TR
4481><TD CLASS="doc"
4482><P
4483><EM
4484>O(n*log n)</EM
4485>. Build a map from a list of key/value pairs with a combining function. See also <TT
4486><A HREF="Data-Map.html#v%3AfromAscListWithKey"
4487>fromAscListWithKey</A
4488></TT
4489>.
4490</P
4491><PRE
4492> let f k a1 a2 = (show k) ++ a1 ++ a2
4493 fromListWithKey f [(5,&quot;a&quot;), (5,&quot;b&quot;), (3,&quot;b&quot;), (3,&quot;a&quot;), (5,&quot;a&quot;)] == fromList [(3, &quot;3ab&quot;), (5, &quot;5a5ba&quot;)]
4494 fromListWithKey f [] == empty
4495</PRE
4496></TD
4497></TR
4498><TR
4499><TD CLASS="s15"
4500></TD
4501></TR
4502><TR
4503><TD CLASS="section2"
4504><A NAME="16"
4505>Ordered lists
4506</A
4507></TD
4508></TR
4509><TR
4510><TD CLASS="s15"
4511></TD
4512></TR
4513><TR
4514><TD CLASS="decl"
4515><A NAME="v%3AtoAscList"
4516></A
4517><B
4518>toAscList</B
4519> :: <A HREF="Data-Map.html#t%3AMap"
4520>Map</A
4521> k a -&gt; [(k, a)]</TD
4522></TR
4523><TR
4524><TD CLASS="doc"
4525><P
4526><EM
4527>O(n)</EM
4528>. Convert to an ascending list.
4529</P
4530><PRE
4531> toAscList (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == [(3,&quot;b&quot;), (5,&quot;a&quot;)]
4532</PRE
4533></TD
4534></TR
4535><TR
4536><TD CLASS="s15"
4537></TD
4538></TR
4539><TR
4540><TD CLASS="decl"
4541><A NAME="v%3AfromAscList"
4542></A
4543><B
4544>fromAscList</B
4545> :: <A HREF="Prelude.html#t%3AEq"
4546>Eq</A
4547> k =&gt; [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
4548>Map</A
4549> k a</TD
4550></TR
4551><TR
4552><TD CLASS="doc"
4553><P
4554><EM
4555>O(n)</EM
4556>. Build a map from an ascending list in linear time.
4557 <EM
4558>The precondition (input list is ascending) is not checked.</EM
4559>
4560</P
4561><PRE
4562> fromAscList [(3,&quot;b&quot;), (5,&quot;a&quot;)]          == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
4563 fromAscList [(3,&quot;b&quot;), (5,&quot;a&quot;), (5,&quot;b&quot;)] == fromList [(3, &quot;b&quot;), (5, &quot;b&quot;)]
4564 valid (fromAscList [(3,&quot;b&quot;), (5,&quot;a&quot;), (5,&quot;b&quot;)]) == True
4565 valid (fromAscList [(5,&quot;a&quot;), (3,&quot;b&quot;), (5,&quot;b&quot;)]) == False
4566</PRE
4567></TD
4568></TR
4569><TR
4570><TD CLASS="s15"
4571></TD
4572></TR
4573><TR
4574><TD CLASS="decl"
4575><A NAME="v%3AfromAscListWith"
4576></A
4577><B
4578>fromAscListWith</B
4579> :: <A HREF="Prelude.html#t%3AEq"
4580>Eq</A
4581> k =&gt; (a -&gt; a -&gt; a) -&gt; [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
4582>Map</A
4583> k a</TD
4584></TR
4585><TR
4586><TD CLASS="doc"
4587><P
4588><EM
4589>O(n)</EM
4590>. Build a map from an ascending list in linear time with a combining function for equal keys.
4591 <EM
4592>The precondition (input list is ascending) is not checked.</EM
4593>
4594</P
4595><PRE
4596> fromAscListWith (++) [(3,&quot;b&quot;), (5,&quot;a&quot;), (5,&quot;b&quot;)] == fromList [(3, &quot;b&quot;), (5, &quot;ba&quot;)]
4597 valid (fromAscListWith (++) [(3,&quot;b&quot;), (5,&quot;a&quot;), (5,&quot;b&quot;)]) == True
4598 valid (fromAscListWith (++) [(5,&quot;a&quot;), (3,&quot;b&quot;), (5,&quot;b&quot;)]) == False
4599</PRE
4600></TD
4601></TR
4602><TR
4603><TD CLASS="s15"
4604></TD
4605></TR
4606><TR
4607><TD CLASS="decl"
4608><A NAME="v%3AfromAscListWithKey"
4609></A
4610><B
4611>fromAscListWithKey</B
4612> :: <A HREF="Prelude.html#t%3AEq"
4613>Eq</A
4614> k =&gt; (k -&gt; a -&gt; a -&gt; a) -&gt; [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
4615>Map</A
4616> k a</TD
4617></TR
4618><TR
4619><TD CLASS="doc"
4620><P
4621><EM
4622>O(n)</EM
4623>. Build a map from an ascending list in linear time with a
4624 combining function for equal keys.
4625 <EM
4626>The precondition (input list is ascending) is not checked.</EM
4627>
4628</P
4629><PRE
4630> let f k a1 a2 = (show k) ++ &quot;:&quot; ++ a1 ++ a2
4631 fromAscListWithKey f [(3,&quot;b&quot;), (5,&quot;a&quot;), (5,&quot;b&quot;), (5,&quot;b&quot;)] == fromList [(3, &quot;b&quot;), (5, &quot;5:b5:ba&quot;)]
4632 valid (fromAscListWithKey f [(3,&quot;b&quot;), (5,&quot;a&quot;), (5,&quot;b&quot;), (5,&quot;b&quot;)]) == True
4633 valid (fromAscListWithKey f [(5,&quot;a&quot;), (3,&quot;b&quot;), (5,&quot;b&quot;), (5,&quot;b&quot;)]) == False
4634</PRE
4635></TD
4636></TR
4637><TR
4638><TD CLASS="s15"
4639></TD
4640></TR
4641><TR
4642><TD CLASS="decl"
4643><A NAME="v%3AfromDistinctAscList"
4644></A
4645><B
4646>fromDistinctAscList</B
4647> :: [(k, a)] -&gt; <A HREF="Data-Map.html#t%3AMap"
4648>Map</A
4649> k a</TD
4650></TR
4651><TR
4652><TD CLASS="doc"
4653><P
4654><EM
4655>O(n)</EM
4656>. Build a map from an ascending list of distinct elements in linear time.
4657 <EM
4658>The precondition is not checked.</EM
4659>
4660</P
4661><PRE
4662> fromDistinctAscList [(3,&quot;b&quot;), (5,&quot;a&quot;)] == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
4663 valid (fromDistinctAscList [(3,&quot;b&quot;), (5,&quot;a&quot;)])          == True
4664 valid (fromDistinctAscList [(3,&quot;b&quot;), (5,&quot;a&quot;), (5,&quot;b&quot;)]) == False
4665</PRE
4666></TD
4667></TR
4668><TR
4669><TD CLASS="s15"
4670></TD
4671></TR
4672><TR
4673><TD CLASS="section1"
4674><A NAME="17"
4675>Filter
4676</A
4677></TD
4678></TR
4679><TR
4680><TD CLASS="s15"
4681></TD
4682></TR
4683><TR
4684><TD CLASS="decl"
4685><A NAME="v%3Afilter"
4686></A
4687><B
4688>filter</B
4689> :: <A HREF="Prelude.html#t%3AOrd"
4690>Ord</A
4691> k =&gt; (a -&gt; <A HREF="Prelude.html#t%3ABool"
4692>Bool</A
4693>) -&gt; <A HREF="Data-Map.html#t%3AMap"
4694>Map</A
4695> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
4696>Map</A
4697> k a</TD
4698></TR
4699><TR
4700><TD CLASS="doc"
4701><P
4702><EM
4703>O(n)</EM
4704>. Filter all values that satisfy the predicate.
4705</P
4706><PRE
4707> filter (&gt; &quot;a&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;b&quot;
4708 filter (&gt; &quot;x&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == empty
4709 filter (&lt; &quot;a&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == empty
4710</PRE
4711></TD
4712></TR
4713><TR
4714><TD CLASS="s15"
4715></TD
4716></TR
4717><TR
4718><TD CLASS="decl"
4719><A NAME="v%3AfilterWithKey"
4720></A
4721><B
4722>filterWithKey</B
4723> :: <A HREF="Prelude.html#t%3AOrd"
4724>Ord</A
4725> k =&gt; (k -&gt; a -&gt; <A HREF="Prelude.html#t%3ABool"
4726>Bool</A
4727>) -&gt; <A HREF="Data-Map.html#t%3AMap"
4728>Map</A
4729> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
4730>Map</A
4731> k a</TD
4732></TR
4733><TR
4734><TD CLASS="doc"
4735><P
4736><EM
4737>O(n)</EM
4738>. Filter all keys/values that satisfy the predicate.
4739</P
4740><PRE
4741> filterWithKey (\k _ -&gt; k &gt; 4) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;a&quot;
4742</PRE
4743></TD
4744></TR
4745><TR
4746><TD CLASS="s15"
4747></TD
4748></TR
4749><TR
4750><TD CLASS="decl"
4751><A NAME="v%3Apartition"
4752></A
4753><B
4754>partition</B
4755> :: <A HREF="Prelude.html#t%3AOrd"
4756>Ord</A
4757> k =&gt; (a -&gt; <A HREF="Prelude.html#t%3ABool"
4758>Bool</A
4759>) -&gt; <A HREF="Data-Map.html#t%3AMap"
4760>Map</A
4761> k a -&gt; (<A HREF="Data-Map.html#t%3AMap"
4762>Map</A
4763> k a, <A HREF="Data-Map.html#t%3AMap"
4764>Map</A
4765> k a)</TD
4766></TR
4767><TR
4768><TD CLASS="doc"
4769><P
4770><EM
4771>O(n)</EM
4772>. Partition the map according to a predicate. The first
4773 map contains all elements that satisfy the predicate, the second all
4774 elements that fail the predicate. See also <TT
4775><A HREF="Data-Map.html#v%3Asplit"
4776>split</A
4777></TT
4778>.
4779</P
4780><PRE
4781> partition (&gt; &quot;a&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (singleton 3 &quot;b&quot;, singleton 5 &quot;a&quot;)
4782 partition (&lt; &quot;x&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)], empty)
4783 partition (&gt; &quot;x&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (empty, fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)])
4784</PRE
4785></TD
4786></TR
4787><TR
4788><TD CLASS="s15"
4789></TD
4790></TR
4791><TR
4792><TD CLASS="decl"
4793><A NAME="v%3ApartitionWithKey"
4794></A
4795><B
4796>partitionWithKey</B
4797> :: <A HREF="Prelude.html#t%3AOrd"
4798>Ord</A
4799> k =&gt; (k -&gt; a -&gt; <A HREF="Prelude.html#t%3ABool"
4800>Bool</A
4801>) -&gt; <A HREF="Data-Map.html#t%3AMap"
4802>Map</A
4803> k a -&gt; (<A HREF="Data-Map.html#t%3AMap"
4804>Map</A
4805> k a, <A HREF="Data-Map.html#t%3AMap"
4806>Map</A
4807> k a)</TD
4808></TR
4809><TR
4810><TD CLASS="doc"
4811><P
4812><EM
4813>O(n)</EM
4814>. Partition the map according to a predicate. The first
4815 map contains all elements that satisfy the predicate, the second all
4816 elements that fail the predicate. See also <TT
4817><A HREF="Data-Map.html#v%3Asplit"
4818>split</A
4819></TT
4820>.
4821</P
4822><PRE
4823> partitionWithKey (\ k _ -&gt; k &gt; 3) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (singleton 5 &quot;a&quot;, singleton 3 &quot;b&quot;)
4824 partitionWithKey (\ k _ -&gt; k &lt; 7) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)], empty)
4825 partitionWithKey (\ k _ -&gt; k &gt; 7) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (empty, fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)])
4826</PRE
4827></TD
4828></TR
4829><TR
4830><TD CLASS="s15"
4831></TD
4832></TR
4833><TR
4834><TD CLASS="decl"
4835><A NAME="v%3AmapMaybe"
4836></A
4837><B
4838>mapMaybe</B
4839> :: <A HREF="Prelude.html#t%3AOrd"
4840>Ord</A
4841> k =&gt; (a -&gt; <A HREF="Prelude.html#t%3AMaybe"
4842>Maybe</A
4843> b) -&gt; <A HREF="Data-Map.html#t%3AMap"
4844>Map</A
4845> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
4846>Map</A
4847> k b</TD
4848></TR
4849><TR
4850><TD CLASS="doc"
4851><P
4852><EM
4853>O(n)</EM
4854>. Map values and collect the <TT
4855><A HREF="Prelude.html#v%3AJust"
4856>Just</A
4857></TT
4858> results.
4859</P
4860><PRE
4861> let f x = if x == &quot;a&quot; then Just &quot;new a&quot; else Nothing
4862 mapMaybe f (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;new a&quot;
4863</PRE
4864></TD
4865></TR
4866><TR
4867><TD CLASS="s15"
4868></TD
4869></TR
4870><TR
4871><TD CLASS="decl"
4872><A NAME="v%3AmapMaybeWithKey"
4873></A
4874><B
4875>mapMaybeWithKey</B
4876> :: <A HREF="Prelude.html#t%3AOrd"
4877>Ord</A
4878> k =&gt; (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
4879>Maybe</A
4880> b) -&gt; <A HREF="Data-Map.html#t%3AMap"
4881>Map</A
4882> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
4883>Map</A
4884> k b</TD
4885></TR
4886><TR
4887><TD CLASS="doc"
4888><P
4889><EM
4890>O(n)</EM
4891>. Map keys/values and collect the <TT
4892><A HREF="Prelude.html#v%3AJust"
4893>Just</A
4894></TT
4895> results.
4896</P
4897><PRE
4898> let f k _ = if k &lt; 5 then Just (&quot;key : &quot; ++ (show k)) else Nothing
4899 mapMaybeWithKey f (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;key : 3&quot;
4900</PRE
4901></TD
4902></TR
4903><TR
4904><TD CLASS="s15"
4905></TD
4906></TR
4907><TR
4908><TD CLASS="decl"
4909><A NAME="v%3AmapEither"
4910></A
4911><B
4912>mapEither</B
4913> :: <A HREF="Prelude.html#t%3AOrd"
4914>Ord</A
4915> k =&gt; (a -&gt; <A HREF="Prelude.html#t%3AEither"
4916>Either</A
4917> b c) -&gt; <A HREF="Data-Map.html#t%3AMap"
4918>Map</A
4919> k a -&gt; (<A HREF="Data-Map.html#t%3AMap"
4920>Map</A
4921> k b, <A HREF="Data-Map.html#t%3AMap"
4922>Map</A
4923> k c)</TD
4924></TR
4925><TR
4926><TD CLASS="doc"
4927><P
4928><EM
4929>O(n)</EM
4930>. Map values and separate the <TT
4931><A HREF="Prelude.html#v%3ALeft"
4932>Left</A
4933></TT
4934> and <TT
4935><A HREF="Prelude.html#v%3ARight"
4936>Right</A
4937></TT
4938> results.
4939</P
4940><PRE
4941> let f a = if a &lt; &quot;c&quot; then Left a else Right a
4942 mapEither f (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (1,&quot;x&quot;), (7,&quot;z&quot;)])
4943     == (fromList [(3,&quot;b&quot;), (5,&quot;a&quot;)], fromList [(1,&quot;x&quot;), (7,&quot;z&quot;)])
4944
4945 mapEither (\ a -&gt; Right a) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (1,&quot;x&quot;), (7,&quot;z&quot;)])
4946     == (empty, fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (1,&quot;x&quot;), (7,&quot;z&quot;)])
4947</PRE
4948></TD
4949></TR
4950><TR
4951><TD CLASS="s15"
4952></TD
4953></TR
4954><TR
4955><TD CLASS="decl"
4956><A NAME="v%3AmapEitherWithKey"
4957></A
4958><B
4959>mapEitherWithKey</B
4960> :: <A HREF="Prelude.html#t%3AOrd"
4961>Ord</A
4962> k =&gt; (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AEither"
4963>Either</A
4964> b c) -&gt; <A HREF="Data-Map.html#t%3AMap"
4965>Map</A
4966> k a -&gt; (<A HREF="Data-Map.html#t%3AMap"
4967>Map</A
4968> k b, <A HREF="Data-Map.html#t%3AMap"
4969>Map</A
4970> k c)</TD
4971></TR
4972><TR
4973><TD CLASS="doc"
4974><P
4975><EM
4976>O(n)</EM
4977>. Map keys/values and separate the <TT
4978><A HREF="Prelude.html#v%3ALeft"
4979>Left</A
4980></TT
4981> and <TT
4982><A HREF="Prelude.html#v%3ARight"
4983>Right</A
4984></TT
4985> results.
4986</P
4987><PRE
4988> let f k a = if k &lt; 5 then Left (k * 2) else Right (a ++ a)
4989 mapEitherWithKey f (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (1,&quot;x&quot;), (7,&quot;z&quot;)])
4990     == (fromList [(1,2), (3,6)], fromList [(5,&quot;aa&quot;), (7,&quot;zz&quot;)])
4991
4992 mapEitherWithKey (\_ a -&gt; Right a) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (1,&quot;x&quot;), (7,&quot;z&quot;)])
4993     == (empty, fromList [(1,&quot;x&quot;), (3,&quot;b&quot;), (5,&quot;a&quot;), (7,&quot;z&quot;)])
4994</PRE
4995></TD
4996></TR
4997><TR
4998><TD CLASS="s15"
4999></TD
5000></TR
5001><TR
5002><TD CLASS="decl"
5003><A NAME="v%3Asplit"
5004></A
5005><B
5006>split</B
5007> :: <A HREF="Prelude.html#t%3AOrd"
5008>Ord</A
5009> k =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
5010>Map</A
5011> k a -&gt; (<A HREF="Data-Map.html#t%3AMap"
5012>Map</A
5013> k a, <A HREF="Data-Map.html#t%3AMap"
5014>Map</A
5015> k a)</TD
5016></TR
5017><TR
5018><TD CLASS="doc"
5019><P
5020><EM
5021>O(log n)</EM
5022>. The expression (<TT
5023><TT
5024><A HREF="Data-Map.html#v%3Asplit"
5025>split</A
5026></TT
5027> k map</TT
5028>) is a pair <TT
5029>(map1,map2)</TT
5030> where
5031 the keys in <TT
5032>map1</TT
5033> are smaller than <TT
5034>k</TT
5035> and the keys in <TT
5036>map2</TT
5037> larger than <TT
5038>k</TT
5039>.
5040 Any key equal to <TT
5041>k</TT
5042> is found in neither <TT
5043>map1</TT
5044> nor <TT
5045>map2</TT
5046>.
5047</P
5048><PRE
5049> split 2 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (empty, fromList [(3,&quot;b&quot;), (5,&quot;a&quot;)])
5050 split 3 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (empty, singleton 5 &quot;a&quot;)
5051 split 4 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (singleton 3 &quot;b&quot;, singleton 5 &quot;a&quot;)
5052 split 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (singleton 3 &quot;b&quot;, empty)
5053 split 6 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (fromList [(3,&quot;b&quot;), (5,&quot;a&quot;)], empty)
5054</PRE
5055></TD
5056></TR
5057><TR
5058><TD CLASS="s15"
5059></TD
5060></TR
5061><TR
5062><TD CLASS="decl"
5063><A NAME="v%3AsplitLookup"
5064></A
5065><B
5066>splitLookup</B
5067> :: <A HREF="Prelude.html#t%3AOrd"
5068>Ord</A
5069> k =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
5070>Map</A
5071> k a -&gt; (<A HREF="Data-Map.html#t%3AMap"
5072>Map</A
5073> k a, <A HREF="Prelude.html#t%3AMaybe"
5074>Maybe</A
5075> a, <A HREF="Data-Map.html#t%3AMap"
5076>Map</A
5077> k a)</TD
5078></TR
5079><TR
5080><TD CLASS="doc"
5081><P
5082><EM
5083>O(log n)</EM
5084>. The expression (<TT
5085><TT
5086><A HREF="Data-Map.html#v%3AsplitLookup"
5087>splitLookup</A
5088></TT
5089> k map</TT
5090>) splits a map just
5091 like <TT
5092><A HREF="Data-Map.html#v%3Asplit"
5093>split</A
5094></TT
5095> but also returns <TT
5096><TT
5097><A HREF="Data-Map.html#v%3Alookup"
5098>lookup</A
5099></TT
5100> k map</TT
5101>.
5102</P
5103><PRE
5104> splitLookup 2 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (empty, Nothing, fromList [(3,&quot;b&quot;), (5,&quot;a&quot;)])
5105 splitLookup 3 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (empty, Just &quot;b&quot;, singleton 5 &quot;a&quot;)
5106 splitLookup 4 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (singleton 3 &quot;b&quot;, Nothing, singleton 5 &quot;a&quot;)
5107 splitLookup 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (singleton 3 &quot;b&quot;, Just &quot;a&quot;, empty)
5108 splitLookup 6 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (fromList [(3,&quot;b&quot;), (5,&quot;a&quot;)], Nothing, empty)
5109</PRE
5110></TD
5111></TR
5112><TR
5113><TD CLASS="s15"
5114></TD
5115></TR
5116><TR
5117><TD CLASS="section1"
5118><A NAME="18"
5119>Submap
5120</A
5121></TD
5122></TR
5123><TR
5124><TD CLASS="s15"
5125></TD
5126></TR
5127><TR
5128><TD CLASS="decl"
5129><A NAME="v%3AisSubmapOf"
5130></A
5131><B
5132>isSubmapOf</B
5133> :: (<A HREF="Prelude.html#t%3AOrd"
5134>Ord</A
5135> k, <A HREF="Prelude.html#t%3AEq"
5136>Eq</A
5137> a) =&gt; <A HREF="Data-Map.html#t%3AMap"
5138>Map</A
5139> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
5140>Map</A
5141> k a -&gt; <A HREF="Prelude.html#t%3ABool"
5142>Bool</A
5143></TD
5144></TR
5145><TR
5146><TD CLASS="doc"
5147><EM
5148>O(n+m)</EM
5149>.
5150 This function is defined as (<TT
5151><TT
5152><A HREF="Data-Map.html#v%3AisSubmapOf"
5153>isSubmapOf</A
5154></TT
5155> = <TT
5156><A HREF="Data-Map.html#v%3AisSubmapOfBy"
5157>isSubmapOfBy</A
5158></TT
5159> (==)</TT
5160>).
5161</TD
5162></TR
5163><TR
5164><TD CLASS="s15"
5165></TD
5166></TR
5167><TR
5168><TD CLASS="decl"
5169><A NAME="v%3AisSubmapOfBy"
5170></A
5171><B
5172>isSubmapOfBy</B
5173> :: <A HREF="Prelude.html#t%3AOrd"
5174>Ord</A
5175> k =&gt; (a -&gt; b -&gt; <A HREF="Prelude.html#t%3ABool"
5176>Bool</A
5177>) -&gt; <A HREF="Data-Map.html#t%3AMap"
5178>Map</A
5179> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
5180>Map</A
5181> k b -&gt; <A HREF="Prelude.html#t%3ABool"
5182>Bool</A
5183></TD
5184></TR
5185><TR
5186><TD CLASS="doc"
5187><P
5188><EM
5189>O(n+m)</EM
5190>.
5191 The expression (<TT
5192><TT
5193><A HREF="Data-Map.html#v%3AisSubmapOfBy"
5194>isSubmapOfBy</A
5195></TT
5196> f t1 t2</TT
5197>) returns <TT
5198><A HREF="Prelude.html#v%3ATrue"
5199>True</A
5200></TT
5201> if
5202 all keys in <TT
5203>t1</TT
5204> are in tree <TT
5205>t2</TT
5206>, and when <TT
5207>f</TT
5208> returns <TT
5209><A HREF="Prelude.html#v%3ATrue"
5210>True</A
5211></TT
5212> when
5213 applied to their respective values. For example, the following
5214 expressions are all <TT
5215><A HREF="Prelude.html#v%3ATrue"
5216>True</A
5217></TT
5218>:
5219</P
5220><PRE
5221> isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
5222 isSubmapOfBy (&lt;=) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
5223 isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)])
5224</PRE
5225><P
5226>But the following are all <TT
5227><A HREF="Prelude.html#v%3AFalse"
5228>False</A
5229></TT
5230>:
5231</P
5232><PRE
5233> isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)])
5234 isSubmapOfBy (&lt;)  (fromList [('a',1)]) (fromList [('a',1),('b',2)])
5235 isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)])
5236</PRE
5237></TD
5238></TR
5239><TR
5240><TD CLASS="s15"
5241></TD
5242></TR
5243><TR
5244><TD CLASS="decl"
5245><A NAME="v%3AisProperSubmapOf"
5246></A
5247><B
5248>isProperSubmapOf</B
5249> :: (<A HREF="Prelude.html#t%3AOrd"
5250>Ord</A
5251> k, <A HREF="Prelude.html#t%3AEq"
5252>Eq</A
5253> a) =&gt; <A HREF="Data-Map.html#t%3AMap"
5254>Map</A
5255> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
5256>Map</A
5257> k a -&gt; <A HREF="Prelude.html#t%3ABool"
5258>Bool</A
5259></TD
5260></TR
5261><TR
5262><TD CLASS="doc"
5263><EM
5264>O(n+m)</EM
5265>. Is this a proper submap? (ie. a submap but not equal).
5266 Defined as (<TT
5267><TT
5268><A HREF="Data-Map.html#v%3AisProperSubmapOf"
5269>isProperSubmapOf</A
5270></TT
5271> = <TT
5272><A HREF="Data-Map.html#v%3AisProperSubmapOfBy"
5273>isProperSubmapOfBy</A
5274></TT
5275> (==)</TT
5276>).
5277</TD
5278></TR
5279><TR
5280><TD CLASS="s15"
5281></TD
5282></TR
5283><TR
5284><TD CLASS="decl"
5285><A NAME="v%3AisProperSubmapOfBy"
5286></A
5287><B
5288>isProperSubmapOfBy</B
5289> :: <A HREF="Prelude.html#t%3AOrd"
5290>Ord</A
5291> k =&gt; (a -&gt; b -&gt; <A HREF="Prelude.html#t%3ABool"
5292>Bool</A
5293>) -&gt; <A HREF="Data-Map.html#t%3AMap"
5294>Map</A
5295> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
5296>Map</A
5297> k b -&gt; <A HREF="Prelude.html#t%3ABool"
5298>Bool</A
5299></TD
5300></TR
5301><TR
5302><TD CLASS="doc"
5303><P
5304><EM
5305>O(n+m)</EM
5306>. Is this a proper submap? (ie. a submap but not equal).
5307 The expression (<TT
5308><TT
5309><A HREF="Data-Map.html#v%3AisProperSubmapOfBy"
5310>isProperSubmapOfBy</A
5311></TT
5312> f m1 m2</TT
5313>) returns <TT
5314><A HREF="Prelude.html#v%3ATrue"
5315>True</A
5316></TT
5317> when
5318 <TT
5319>m1</TT
5320> and <TT
5321>m2</TT
5322> are not equal,
5323 all keys in <TT
5324>m1</TT
5325> are in <TT
5326>m2</TT
5327>, and when <TT
5328>f</TT
5329> returns <TT
5330><A HREF="Prelude.html#v%3ATrue"
5331>True</A
5332></TT
5333> when
5334 applied to their respective values. For example, the following
5335 expressions are all <TT
5336><A HREF="Prelude.html#v%3ATrue"
5337>True</A
5338></TT
5339>:
5340</P
5341><PRE
5342> isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
5343 isProperSubmapOfBy (&lt;=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
5344</PRE
5345><P
5346>But the following are all <TT
5347><A HREF="Prelude.html#v%3AFalse"
5348>False</A
5349></TT
5350>:
5351</P
5352><PRE
5353> isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
5354 isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
5355 isProperSubmapOfBy (&lt;)  (fromList [(1,1)])       (fromList [(1,1),(2,2)])
5356</PRE
5357></TD
5358></TR
5359><TR
5360><TD CLASS="s15"
5361></TD
5362></TR
5363><TR
5364><TD CLASS="section1"
5365><A NAME="19"
5366>Indexed
5367</A
5368></TD
5369></TR
5370><TR
5371><TD CLASS="s15"
5372></TD
5373></TR
5374><TR
5375><TD CLASS="decl"
5376><A NAME="v%3AlookupIndex"
5377></A
5378><B
5379>lookupIndex</B
5380> :: (<A HREF="Prelude.html#t%3AMonad"
5381>Monad</A
5382> m, <A HREF="Prelude.html#t%3AOrd"
5383>Ord</A
5384> k) =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
5385>Map</A
5386> k a -&gt; m <A HREF="Prelude.html#t%3AInt"
5387>Int</A
5388></TD
5389></TR
5390><TR
5391><TD CLASS="doc"
5392><P
5393><EM
5394>O(log n)</EM
5395>. Lookup the <EM
5396>index</EM
5397> of a key. The index is a number from
5398 <EM
5399>0</EM
5400> up to, but not including, the <TT
5401><A HREF="Data-Map.html#v%3Asize"
5402>size</A
5403></TT
5404> of the map.
5405</P
5406><PRE
5407> isJust (lookupIndex 2 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]))   == False
5408 fromJust (lookupIndex 3 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])) == 0
5409 fromJust (lookupIndex 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])) == 1
5410 isJust (lookupIndex 6 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]))   == False
5411</PRE
5412></TD
5413></TR
5414><TR
5415><TD CLASS="s15"
5416></TD
5417></TR
5418><TR
5419><TD CLASS="decl"
5420><A NAME="v%3AfindIndex"
5421></A
5422><B
5423>findIndex</B
5424> :: <A HREF="Prelude.html#t%3AOrd"
5425>Ord</A
5426> k =&gt; k -&gt; <A HREF="Data-Map.html#t%3AMap"
5427>Map</A
5428> k a -&gt; <A HREF="Prelude.html#t%3AInt"
5429>Int</A
5430></TD
5431></TR
5432><TR
5433><TD CLASS="doc"
5434><P
5435><EM
5436>O(log n)</EM
5437>. Return the <EM
5438>index</EM
5439> of a key. The index is a number from
5440 <EM
5441>0</EM
5442> up to, but not including, the <TT
5443><A HREF="Data-Map.html#v%3Asize"
5444>size</A
5445></TT
5446> of the map. Calls <TT
5447><A HREF="Prelude.html#v%3Aerror"
5448>error</A
5449></TT
5450> when
5451 the key is not a <TT
5452><A HREF="Data-Map.html#v%3Amember"
5453>member</A
5454></TT
5455> of the map.
5456</P
5457><PRE
5458> findIndex 2 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])    Error: element is not in the map
5459 findIndex 3 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == 0
5460 findIndex 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == 1
5461 findIndex 6 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])    Error: element is not in the map
5462</PRE
5463></TD
5464></TR
5465><TR
5466><TD CLASS="s15"
5467></TD
5468></TR
5469><TR
5470><TD CLASS="decl"
5471><A NAME="v%3AelemAt"
5472></A
5473><B
5474>elemAt</B
5475> :: <A HREF="Prelude.html#t%3AInt"
5476>Int</A
5477> -&gt; <A HREF="Data-Map.html#t%3AMap"
5478>Map</A
5479> k a -&gt; (k, a)</TD
5480></TR
5481><TR
5482><TD CLASS="doc"
5483><P
5484><EM
5485>O(log n)</EM
5486>. Retrieve an element by <EM
5487>index</EM
5488>. Calls <TT
5489><A HREF="Prelude.html#v%3Aerror"
5490>error</A
5491></TT
5492> when an
5493 invalid index is used.
5494</P
5495><PRE
5496> elemAt 0 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (3,&quot;b&quot;)
5497 elemAt 1 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (5, &quot;a&quot;)
5498 elemAt 2 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])    Error: index out of range
5499</PRE
5500></TD
5501></TR
5502><TR
5503><TD CLASS="s15"
5504></TD
5505></TR
5506><TR
5507><TD CLASS="decl"
5508><A NAME="v%3AupdateAt"
5509></A
5510><B
5511>updateAt</B
5512> :: (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
5513>Maybe</A
5514> a) -&gt; <A HREF="Prelude.html#t%3AInt"
5515>Int</A
5516> -&gt; <A HREF="Data-Map.html#t%3AMap"
5517>Map</A
5518> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
5519>Map</A
5520> k a</TD
5521></TR
5522><TR
5523><TD CLASS="doc"
5524><P
5525><EM
5526>O(log n)</EM
5527>. Update the element at <EM
5528>index</EM
5529>. Calls <TT
5530><A HREF="Prelude.html#v%3Aerror"
5531>error</A
5532></TT
5533> when an
5534 invalid index is used.
5535</P
5536><PRE
5537> updateAt (\ _ _ -&gt; Just &quot;x&quot;) 0    (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;x&quot;), (5, &quot;a&quot;)]
5538 updateAt (\ _ _ -&gt; Just &quot;x&quot;) 1    (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;x&quot;)]
5539 updateAt (\ _ _ -&gt; Just &quot;x&quot;) 2    (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])    Error: index out of range
5540 updateAt (\ _ _ -&gt; Just &quot;x&quot;) (-1) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])    Error: index out of range
5541 updateAt (\_ _  -&gt; Nothing)  0    (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;a&quot;
5542 updateAt (\_ _  -&gt; Nothing)  1    (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;b&quot;
5543 updateAt (\_ _  -&gt; Nothing)  2    (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])    Error: index out of range
5544 updateAt (\_ _  -&gt; Nothing)  (-1) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])    Error: index out of range
5545</PRE
5546></TD
5547></TR
5548><TR
5549><TD CLASS="s15"
5550></TD
5551></TR
5552><TR
5553><TD CLASS="decl"
5554><A NAME="v%3AdeleteAt"
5555></A
5556><B
5557>deleteAt</B
5558> :: <A HREF="Prelude.html#t%3AInt"
5559>Int</A
5560> -&gt; <A HREF="Data-Map.html#t%3AMap"
5561>Map</A
5562> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
5563>Map</A
5564> k a</TD
5565></TR
5566><TR
5567><TD CLASS="doc"
5568><P
5569><EM
5570>O(log n)</EM
5571>. Delete the element at <EM
5572>index</EM
5573>.
5574 Defined as (<TT
5575><TT
5576><A HREF="Data-Map.html#v%3AdeleteAt"
5577>deleteAt</A
5578></TT
5579> i map = <TT
5580><A HREF="Data-Map.html#v%3AupdateAt"
5581>updateAt</A
5582></TT
5583> (k x -&gt; <TT
5584><A HREF="Prelude.html#v%3ANothing"
5585>Nothing</A
5586></TT
5587>) i map</TT
5588>).
5589</P
5590><PRE
5591> deleteAt 0  (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;a&quot;
5592 deleteAt 1  (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;b&quot;
5593 deleteAt 2 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])     Error: index out of range
5594 deleteAt (-1) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])  Error: index out of range
5595</PRE
5596></TD
5597></TR
5598><TR
5599><TD CLASS="s15"
5600></TD
5601></TR
5602><TR
5603><TD CLASS="section1"
5604><A NAME="20"
5605>Min/Max
5606</A
5607></TD
5608></TR
5609><TR
5610><TD CLASS="s15"
5611></TD
5612></TR
5613><TR
5614><TD CLASS="decl"
5615><A NAME="v%3AfindMin"
5616></A
5617><B
5618>findMin</B
5619> :: <A HREF="Data-Map.html#t%3AMap"
5620>Map</A
5621> k a -&gt; (k, a)</TD
5622></TR
5623><TR
5624><TD CLASS="doc"
5625><P
5626><EM
5627>O(log n)</EM
5628>. The minimal key of the map. Calls <TT
5629><A HREF="Prelude.html#v%3Aerror"
5630>error</A
5631></TT
5632> is the map is empty.
5633</P
5634><PRE
5635> findMin (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (3,&quot;b&quot;)
5636 findMin empty                            Error: empty map has no minimal element
5637</PRE
5638></TD
5639></TR
5640><TR
5641><TD CLASS="s15"
5642></TD
5643></TR
5644><TR
5645><TD CLASS="decl"
5646><A NAME="v%3AfindMax"
5647></A
5648><B
5649>findMax</B
5650> :: <A HREF="Data-Map.html#t%3AMap"
5651>Map</A
5652> k a -&gt; (k, a)</TD
5653></TR
5654><TR
5655><TD CLASS="doc"
5656><P
5657><EM
5658>O(log n)</EM
5659>. The maximal key of the map. Calls <TT
5660><A HREF="Prelude.html#v%3Aerror"
5661>error</A
5662></TT
5663> is the map is empty.
5664</P
5665><PRE
5666> findMax (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (5,&quot;a&quot;)
5667 findMax empty                            Error: empty map has no maximal element
5668</PRE
5669></TD
5670></TR
5671><TR
5672><TD CLASS="s15"
5673></TD
5674></TR
5675><TR
5676><TD CLASS="decl"
5677><A NAME="v%3AdeleteMin"
5678></A
5679><B
5680>deleteMin</B
5681> :: <A HREF="Data-Map.html#t%3AMap"
5682>Map</A
5683> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
5684>Map</A
5685> k a</TD
5686></TR
5687><TR
5688><TD CLASS="doc"
5689><P
5690><EM
5691>O(log n)</EM
5692>. Delete the minimal key. Returns an empty map if the map is empty.
5693</P
5694><PRE
5695> deleteMin (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (7,&quot;c&quot;)]) == fromList [(5,&quot;a&quot;), (7,&quot;c&quot;)]
5696 deleteMin empty == empty
5697</PRE
5698></TD
5699></TR
5700><TR
5701><TD CLASS="s15"
5702></TD
5703></TR
5704><TR
5705><TD CLASS="decl"
5706><A NAME="v%3AdeleteMax"
5707></A
5708><B
5709>deleteMax</B
5710> :: <A HREF="Data-Map.html#t%3AMap"
5711>Map</A
5712> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
5713>Map</A
5714> k a</TD
5715></TR
5716><TR
5717><TD CLASS="doc"
5718><P
5719><EM
5720>O(log n)</EM
5721>. Delete the maximal key. Returns an empty map if the map is empty.
5722</P
5723><PRE
5724> deleteMax (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (7,&quot;c&quot;)]) == fromList [(3,&quot;b&quot;), (5,&quot;a&quot;)]
5725 deleteMax empty == empty
5726</PRE
5727></TD
5728></TR
5729><TR
5730><TD CLASS="s15"
5731></TD
5732></TR
5733><TR
5734><TD CLASS="decl"
5735><A NAME="v%3AdeleteFindMin"
5736></A
5737><B
5738>deleteFindMin</B
5739> :: <A HREF="Data-Map.html#t%3AMap"
5740>Map</A
5741> k a -&gt; ((k, a), <A HREF="Data-Map.html#t%3AMap"
5742>Map</A
5743> k a)</TD
5744></TR
5745><TR
5746><TD CLASS="doc"
5747><P
5748><EM
5749>O(log n)</EM
5750>. Delete and find the minimal element.
5751</P
5752><PRE
5753> deleteFindMin (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (10,&quot;c&quot;)]) == ((3,&quot;b&quot;), fromList[(5,&quot;a&quot;), (10,&quot;c&quot;)])
5754 deleteFindMin                                            Error: can not return the minimal element of an empty map
5755</PRE
5756></TD
5757></TR
5758><TR
5759><TD CLASS="s15"
5760></TD
5761></TR
5762><TR
5763><TD CLASS="decl"
5764><A NAME="v%3AdeleteFindMax"
5765></A
5766><B
5767>deleteFindMax</B
5768> :: <A HREF="Data-Map.html#t%3AMap"
5769>Map</A
5770> k a -&gt; ((k, a), <A HREF="Data-Map.html#t%3AMap"
5771>Map</A
5772> k a)</TD
5773></TR
5774><TR
5775><TD CLASS="doc"
5776><P
5777><EM
5778>O(log n)</EM
5779>. Delete and find the maximal element.
5780</P
5781><PRE
5782> deleteFindMax (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (10,&quot;c&quot;)]) == ((10,&quot;c&quot;), fromList [(3,&quot;b&quot;), (5,&quot;a&quot;)])
5783 deleteFindMax empty                                      Error: can not return the maximal element of an empty map
5784</PRE
5785></TD
5786></TR
5787><TR
5788><TD CLASS="s15"
5789></TD
5790></TR
5791><TR
5792><TD CLASS="decl"
5793><A NAME="v%3AupdateMin"
5794></A
5795><B
5796>updateMin</B
5797> :: (a -&gt; <A HREF="Prelude.html#t%3AMaybe"
5798>Maybe</A
5799> a) -&gt; <A HREF="Data-Map.html#t%3AMap"
5800>Map</A
5801> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
5802>Map</A
5803> k a</TD
5804></TR
5805><TR
5806><TD CLASS="doc"
5807><P
5808><EM
5809>O(log n)</EM
5810>. Update the value at the minimal key.
5811</P
5812><PRE
5813> updateMin (\ a -&gt; Just (&quot;X&quot; ++ a)) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;Xb&quot;), (5, &quot;a&quot;)]
5814 updateMin (\ _ -&gt; Nothing)         (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;a&quot;
5815</PRE
5816></TD
5817></TR
5818><TR
5819><TD CLASS="s15"
5820></TD
5821></TR
5822><TR
5823><TD CLASS="decl"
5824><A NAME="v%3AupdateMax"
5825></A
5826><B
5827>updateMax</B
5828> :: (a -&gt; <A HREF="Prelude.html#t%3AMaybe"
5829>Maybe</A
5830> a) -&gt; <A HREF="Data-Map.html#t%3AMap"
5831>Map</A
5832> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
5833>Map</A
5834> k a</TD
5835></TR
5836><TR
5837><TD CLASS="doc"
5838><P
5839><EM
5840>O(log n)</EM
5841>. Update the value at the maximal key.
5842</P
5843><PRE
5844> updateMax (\ a -&gt; Just (&quot;X&quot; ++ a)) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;Xa&quot;)]
5845 updateMax (\ _ -&gt; Nothing)         (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;b&quot;
5846</PRE
5847></TD
5848></TR
5849><TR
5850><TD CLASS="s15"
5851></TD
5852></TR
5853><TR
5854><TD CLASS="decl"
5855><A NAME="v%3AupdateMinWithKey"
5856></A
5857><B
5858>updateMinWithKey</B
5859> :: (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
5860>Maybe</A
5861> a) -&gt; <A HREF="Data-Map.html#t%3AMap"
5862>Map</A
5863> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
5864>Map</A
5865> k a</TD
5866></TR
5867><TR
5868><TD CLASS="doc"
5869><P
5870><EM
5871>O(log n)</EM
5872>. Update the value at the minimal key.
5873</P
5874><PRE
5875> updateMinWithKey (\ k a -&gt; Just ((show k) ++ &quot;:&quot; ++ a)) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3,&quot;3:b&quot;), (5,&quot;a&quot;)]
5876 updateMinWithKey (\ _ _ -&gt; Nothing)                     (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;a&quot;
5877</PRE
5878></TD
5879></TR
5880><TR
5881><TD CLASS="s15"
5882></TD
5883></TR
5884><TR
5885><TD CLASS="decl"
5886><A NAME="v%3AupdateMaxWithKey"
5887></A
5888><B
5889>updateMaxWithKey</B
5890> :: (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
5891>Maybe</A
5892> a) -&gt; <A HREF="Data-Map.html#t%3AMap"
5893>Map</A
5894> k a -&gt; <A HREF="Data-Map.html#t%3AMap"
5895>Map</A
5896> k a</TD
5897></TR
5898><TR
5899><TD CLASS="doc"
5900><P
5901><EM
5902>O(log n)</EM
5903>. Update the value at the maximal key.
5904</P
5905><PRE
5906> updateMaxWithKey (\ k a -&gt; Just ((show k) ++ &quot;:&quot; ++ a)) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3,&quot;b&quot;), (5,&quot;5:a&quot;)]
5907 updateMaxWithKey (\ _ _ -&gt; Nothing)                     (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;b&quot;
5908</PRE
5909></TD
5910></TR
5911><TR
5912><TD CLASS="s15"
5913></TD
5914></TR
5915><TR
5916><TD CLASS="decl"
5917><A NAME="v%3AminView"
5918></A
5919><B
5920>minView</B
5921> :: <A HREF="Prelude.html#t%3AMonad"
5922>Monad</A
5923> m =&gt; <A HREF="Data-Map.html#t%3AMap"
5924>Map</A
5925> k a -&gt; m (a, <A HREF="Data-Map.html#t%3AMap"
5926>Map</A
5927> k a)</TD
5928></TR
5929><TR
5930><TD CLASS="doc"
5931><P
5932><EM
5933>O(log n)</EM
5934>. Retrieves the minimal key's value of the map, and the map stripped from that element
5935 <TT
5936>fail</TT
5937>s (in the monad) when passed an empty map.
5938</P
5939><PRE
5940> v &lt;- minView (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])
5941 v == (&quot;b&quot;, singleton 5 &quot;a&quot;)
5942 minView empty                     Error: empty map
5943</PRE
5944></TD
5945></TR
5946><TR
5947><TD CLASS="s15"
5948></TD
5949></TR
5950><TR
5951><TD CLASS="decl"
5952><A NAME="v%3AmaxView"
5953></A
5954><B
5955>maxView</B
5956> :: <A HREF="Prelude.html#t%3AMonad"
5957>Monad</A
5958> m =&gt; <A HREF="Data-Map.html#t%3AMap"
5959>Map</A
5960> k a -&gt; m (a, <A HREF="Data-Map.html#t%3AMap"
5961>Map</A
5962> k a)</TD
5963></TR
5964><TR
5965><TD CLASS="doc"
5966><P
5967><EM
5968>O(log n)</EM
5969>. Retrieves the maximal key's value of the map, and the map stripped from that element
5970 <TT
5971>fail</TT
5972>s (in the monad) when passed an empty map.
5973</P
5974><PRE
5975> v &lt;- maxView (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])
5976 v == (&quot;a&quot;, singleton 3 &quot;b&quot;)
5977 maxView empty                     Error: empty map
5978</PRE
5979></TD
5980></TR
5981><TR
5982><TD CLASS="s15"
5983></TD
5984></TR
5985><TR
5986><TD CLASS="decl"
5987><A NAME="v%3AminViewWithKey"
5988></A
5989><B
5990>minViewWithKey</B
5991> :: <A HREF="Prelude.html#t%3AMonad"
5992>Monad</A
5993> m =&gt; <A HREF="Data-Map.html#t%3AMap"
5994>Map</A
5995> k a -&gt; m ((k, a), <A HREF="Data-Map.html#t%3AMap"
5996>Map</A
5997> k a)</TD
5998></TR
5999><TR
6000><TD CLASS="doc"
6001><P
6002><EM
6003>O(log n)</EM
6004>. Retrieves the minimal (key,value) pair of the map, and the map stripped from that element
6005 <TT
6006>fail</TT
6007>s (in the monad) when passed an empty map.
6008</P
6009><PRE
6010> v &lt;- minViewWithKey (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])
6011 v ==  ((3,&quot;b&quot;), singleton 5 &quot;a&quot;)
6012 minViewWithKey empty              Error: empty map
6013</PRE
6014></TD
6015></TR
6016><TR
6017><TD CLASS="s15"
6018></TD
6019></TR
6020><TR
6021><TD CLASS="decl"
6022><A NAME="v%3AmaxViewWithKey"
6023></A
6024><B
6025>maxViewWithKey</B
6026> :: <A HREF="Prelude.html#t%3AMonad"
6027>Monad</A
6028> m =&gt; <A HREF="Data-Map.html#t%3AMap"
6029>Map</A
6030> k a -&gt; m ((k, a), <A HREF="Data-Map.html#t%3AMap"
6031>Map</A
6032> k a)</TD
6033></TR
6034><TR
6035><TD CLASS="doc"
6036><P
6037><EM
6038>O(log n)</EM
6039>. Retrieves the maximal (key,value) pair of the map, and the map stripped from that element
6040 <TT
6041>fail</TT
6042>s (in the monad) when passed an empty map.
6043</P
6044><PRE
6045> v &lt;- maxViewWithKey (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])
6046 v == ((5,&quot;a&quot;), singleton 3 &quot;b&quot;)
6047 maxViewWithKey empty              Error: empty map
6048</PRE
6049></TD
6050></TR
6051><TR
6052><TD CLASS="s15"
6053></TD
6054></TR
6055><TR
6056><TD CLASS="section1"
6057><A NAME="21"
6058>Debugging
6059</A
6060></TD
6061></TR
6062><TR
6063><TD CLASS="s15"
6064></TD
6065></TR
6066><TR
6067><TD CLASS="decl"
6068><A NAME="v%3AshowTree"
6069></A
6070><B
6071>showTree</B
6072> :: (<A HREF="Prelude.html#t%3AShow"
6073>Show</A
6074> k, <A HREF="Prelude.html#t%3AShow"
6075>Show</A
6076> a) =&gt; <A HREF="Data-Map.html#t%3AMap"
6077>Map</A
6078> k a -&gt; <A HREF="Prelude.html#t%3AString"
6079>String</A
6080></TD
6081></TR
6082><TR
6083><TD CLASS="doc"
6084><EM
6085>O(n)</EM
6086>. Show the tree that implements the map. The tree is shown
6087 in a compressed, hanging format. See <TT
6088><A HREF="Data-Map.html#v%3AshowTreeWith"
6089>showTreeWith</A
6090></TT
6091>.
6092</TD
6093></TR
6094><TR
6095><TD CLASS="s15"
6096></TD
6097></TR
6098><TR
6099><TD CLASS="decl"
6100><A NAME="v%3AshowTreeWith"
6101></A
6102><B
6103>showTreeWith</B
6104> :: (k -&gt; a -&gt; <A HREF="Prelude.html#t%3AString"
6105>String</A
6106>) -&gt; <A HREF="Prelude.html#t%3ABool"
6107>Bool</A
6108> -&gt; <A HREF="Prelude.html#t%3ABool"
6109>Bool</A
6110> -&gt; <A HREF="Data-Map.html#t%3AMap"
6111>Map</A
6112> k a -&gt; <A HREF="Prelude.html#t%3AString"
6113>String</A
6114></TD
6115></TR
6116><TR
6117><TD CLASS="doc"
6118><P
6119><EM
6120>O(n)</EM
6121>. The expression (<TT
6122><TT
6123><A HREF="Data-Map.html#v%3AshowTreeWith"
6124>showTreeWith</A
6125></TT
6126> showelem hang wide map</TT
6127>) shows
6128 the tree that implements the map. Elements are shown using the <TT
6129>showElem</TT
6130> function. If <TT
6131>hang</TT
6132> is
6133 <TT
6134><A HREF="Prelude.html#v%3ATrue"
6135>True</A
6136></TT
6137>, a <EM
6138>hanging</EM
6139> tree is shown otherwise a rotated tree is shown. If
6140 <TT
6141>wide</TT
6142> is <TT
6143><A HREF="Prelude.html#v%3ATrue"
6144>True</A
6145></TT
6146>, an extra wide version is shown.
6147</P
6148><PRE
6149>  Map&gt; let t = fromDistinctAscList [(x,()) | x &lt;- [1..5]]
6150  Map&gt; putStrLn $ showTreeWith (\k x -&gt; show (k,x)) True False t
6151  (4,())
6152  +--(2,())
6153  |  +--(1,())
6154  |  +--(3,())
6155  +--(5,())
6156
6157  Map&gt; putStrLn $ showTreeWith (\k x -&gt; show (k,x)) True True t
6158  (4,())
6159  |
6160  +--(2,())
6161  |  |
6162  |  +--(1,())
6163  |  |
6164  |  +--(3,())
6165  |
6166  +--(5,())
6167
6168  Map&gt; putStrLn $ showTreeWith (\k x -&gt; show (k,x)) False True t
6169  +--(5,())
6170  |
6171  (4,())
6172  |
6173  |  +--(3,())
6174  |  |
6175  +--(2,())
6176     |
6177     +--(1,())
6178</PRE
6179></TD
6180></TR
6181><TR
6182><TD CLASS="s15"
6183></TD
6184></TR
6185><TR
6186><TD CLASS="decl"
6187><A NAME="v%3Avalid"
6188></A
6189><B
6190>valid</B
6191> :: <A HREF="Prelude.html#t%3AOrd"
6192>Ord</A
6193> k =&gt; <A HREF="Data-Map.html#t%3AMap"
6194>Map</A
6195> k a -&gt; <A HREF="Prelude.html#t%3ABool"
6196>Bool</A
6197></TD
6198></TR
6199><TR
6200><TD CLASS="doc"
6201><P
6202><EM
6203>O(n)</EM
6204>. Test if the internal map structure is valid.
6205</P
6206><PRE
6207> valid (fromAscList [(3,&quot;b&quot;), (5,&quot;a&quot;)]) == True
6208 valid (fromAscList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == False
6209</PRE
6210></TD
6211></TR
6212><TR
6213><TD CLASS="s15"
6214></TD
6215></TR
6216><TR
6217><TD CLASS="botbar"
6218>Produced by <A HREF="http://www.haskell.org/haddock/"
6219>Haddock</A
6220> version 0.8</TD
6221></TR
6222></TABLE
6223></BODY
6224></HTML
6225>