Ticket #1611: Data-IntMap.html

File Data-IntMap.html, 87.2 KB (added by guest, 6 years ago)

Data.IntMap? 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.IntMap</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
273
274<SCRIPT SRC="haddock.js" TYPE="text/javascript"
275></SCRIPT
276></HEAD
277><BODY
278><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
279><TR
280><TD CLASS="topbar"
281><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
282><TR
283><TD
284><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "
285></TD
286><TD CLASS="title"
287></TD
288><TD CLASS="topbut"
289><A HREF="index.html"
290>Contents</A
291></TD
292><TD CLASS="topbut"
293><A HREF="doc-index.html"
294>Index</A
295></TD
296></TR
297></TABLE
298></TD
299></TR
300><TR
301><TD CLASS="modulebar"
302><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
303><TR
304><TD
305><FONT SIZE="6"
306>Data.IntMap</FONT
307></TD
308><TD ALIGN="right"
309><TABLE CLASS="narrow" CELLSPACING="0" CELLPADDING="0"
310><TR
311><TD CLASS="infohead"
312>Portability</TD
313><TD CLASS="infoval"
314>portable</TD
315></TR
316><TR
317><TD CLASS="infohead"
318>Stability</TD
319><TD CLASS="infoval"
320>provisional</TD
321></TR
322><TR
323><TD CLASS="infohead"
324>Maintainer</TD
325><TD CLASS="infoval"
326>libraries@haskell.org</TD
327></TR
328></TABLE
329></TD
330></TR
331></TABLE
332></TD
333></TR
334><TR
335><TD CLASS="s15"
336></TD
337></TR
338><TR
339><TD
340><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
341><TR
342><TD CLASS="section4"
343><B
344>Contents</B
345></TD
346></TR
347><TR
348><TD
349><DL
350><DT
351><A HREF="#1"
352>Map type
353</A
354></DT
355><DT
356><A HREF="#2"
357>Operators
358</A
359></DT
360><DT
361><A HREF="#3"
362>Query
363</A
364></DT
365><DT
366><A HREF="#4"
367>Construction
368</A
369></DT
370><DD
371><DL
372><DT
373><A HREF="#5"
374>Insertion
375</A
376></DT
377><DT
378><A HREF="#6"
379>Delete/Update
380</A
381></DT
382></DL
383></DD
384><DT
385><A HREF="#7"
386>Combine
387</A
388></DT
389><DD
390><DL
391><DT
392><A HREF="#8"
393>Union
394</A
395></DT
396><DT
397><A HREF="#9"
398>Difference
399</A
400></DT
401><DT
402><A HREF="#10"
403>Intersection
404</A
405></DT
406></DL
407></DD
408><DT
409><A HREF="#11"
410>Traversal
411</A
412></DT
413><DD
414><DL
415><DT
416><A HREF="#12"
417>Map
418</A
419></DT
420><DT
421><A HREF="#13"
422>Fold
423</A
424></DT
425></DL
426></DD
427><DT
428><A HREF="#14"
429>Conversion
430</A
431></DT
432><DD
433><DL
434><DT
435><A HREF="#15"
436>Lists
437</A
438></DT
439><DT
440><A HREF="#16"
441>Ordered lists
442</A
443></DT
444></DL
445></DD
446><DT
447><A HREF="#17"
448>Filter
449</A
450></DT
451><DT
452><A HREF="#18"
453>Submap
454</A
455></DT
456><DT
457><A HREF="#19"
458>Min/Max
459</A
460></DT
461><DT
462><A HREF="#20"
463>Debugging
464</A
465></DT
466></DL
467></TD
468></TR
469></TABLE
470></TD
471></TR
472><TR
473><TD CLASS="s15"
474></TD
475></TR
476><TR
477><TD CLASS="section1"
478>Description</TD
479></TR
480><TR
481><TD CLASS="doc"
482><P
483>An efficient implementation of maps from integer keys to values.
484</P
485><P
486>Since many function names (but not the type name) clash with
487 <A HREF="Prelude.html"
488>Prelude</A
489> names, this module is usually imported <TT
490>qualified</TT
491>, e.g.
492</P
493><PRE
494>  import Data.IntMap (IntMap)
495  import qualified Data.IntMap as IntMap
496</PRE
497><P
498>The implementation is based on <EM
499>big-endian patricia trees</EM
500>.  This data
501 structure performs especially well on binary operations like <TT
502><A HREF="Data-IntMap.html#v%3Aunion"
503>union</A
504></TT
505>
506 and <TT
507><A HREF="Data-IntMap.html#v%3Aintersection"
508>intersection</A
509></TT
510>.  However, my benchmarks show that it is also
511 (much) faster on insertions and deletions when compared to a generic
512 size-balanced map implementation (see <A HREF="Data-Map.html"
513>Data.Map</A
514> and <A HREF="Data-FiniteMap.html"
515>Data.FiniteMap</A
516>).
517</P
518><UL
519><LI
520> Chris Okasaki and Andy Gill,  &quot;<EM
521>Fast Mergeable Integer Maps</EM
522>&quot;,
523        Workshop on ML, September 1998, pages 77-86,
524        <A HREF="http://www.cse.ogi.edu/~andy/pub/finite.htm"
525>http://www.cse.ogi.edu/~andy/pub/finite.htm</A
526>
527</LI
528><LI
529> D.R. Morrison, &quot;<EM
530>PATRICIA -- Practical Algorithm To Retrieve
531        Information Coded In Alphanumeric</EM
532>&quot;, Journal of the ACM, 15(4),
533        October 1968, pages 514-534.
534</LI
535></UL
536><P
537>Operation comments contain the operation time complexity in
538 the Big-O notation <A HREF="http://en.wikipedia.org/wiki/Big_O_notation"
539>http://en.wikipedia.org/wiki/Big_O_notation</A
540>.
541 Many operations have a worst-case complexity of <EM
542>O(min(n,W))</EM
543>.
544 This means that the operation can become linear in the number of
545 elements with a maximum of <EM
546>W</EM
547> -- the number of bits in an <TT
548><A HREF="Prelude.html#t%3AInt"
549>Int</A
550></TT
551>
552 (32 or 64).
553</P
554></TD
555></TR
556><TR
557><TD CLASS="s15"
558></TD
559></TR
560><TR
561><TD CLASS="section1"
562>Synopsis</TD
563></TR
564><TR
565><TD CLASS="s15"
566></TD
567></TR
568><TR
569><TD CLASS="body"
570><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
571><TR
572><TD CLASS="decl"
573><SPAN CLASS="keyword"
574>data</SPAN
575> <A HREF="#t%3AIntMap"
576>IntMap</A
577> a</TD
578></TR
579><TR
580><TD CLASS="s8"
581></TD
582></TR
583><TR
584><TD CLASS="decl"
585><SPAN CLASS="keyword"
586>type</SPAN
587> <A HREF="#t%3AKey"
588>Key</A
589> = <A HREF="Prelude.html#t%3AInt"
590>Int</A
591></TD
592></TR
593><TR
594><TD CLASS="s8"
595></TD
596></TR
597><TR
598><TD CLASS="decl"
599><A HREF="#v%3A%21"
600>(!)</A
601> :: <A HREF="Data-IntMap.html#t%3AIntMap"
602>IntMap</A
603> a -&gt; <A HREF="Data-IntMap.html#t%3AKey"
604>Key</A
605> -&gt; a</TD
606></TR
607><TR
608><TD CLASS="s8"
609></TD
610></TR
611><TR
612><TD CLASS="decl"
613><A HREF="#v%3A%5C%5C"
614>(\\)</A
615> :: <A HREF="Data-IntMap.html#t%3AIntMap"
616>IntMap</A
617> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
618>IntMap</A
619> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
620>IntMap</A
621> a</TD
622></TR
623><TR
624><TD CLASS="s8"
625></TD
626></TR
627><TR
628><TD CLASS="decl"
629><A HREF="#v%3Anull"
630>null</A
631> :: <A HREF="Data-IntMap.html#t%3AIntMap"
632>IntMap</A
633> a -&gt; <A HREF="Prelude.html#t%3ABool"
634>Bool</A
635></TD
636></TR
637><TR
638><TD CLASS="s8"
639></TD
640></TR
641><TR
642><TD CLASS="decl"
643><A HREF="#v%3Asize"
644>size</A
645> :: <A HREF="Data-IntMap.html#t%3AIntMap"
646>IntMap</A
647> a -&gt; <A HREF="Prelude.html#t%3AInt"
648>Int</A
649></TD
650></TR
651><TR
652><TD CLASS="s8"
653></TD
654></TR
655><TR
656><TD CLASS="decl"
657><A HREF="#v%3Amember"
658>member</A
659> :: <A HREF="Data-IntMap.html#t%3AKey"
660>Key</A
661> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
662>IntMap</A
663> a -&gt; <A HREF="Prelude.html#t%3ABool"
664>Bool</A
665></TD
666></TR
667><TR
668><TD CLASS="s8"
669></TD
670></TR
671><TR
672><TD CLASS="decl"
673><A HREF="#v%3AnotMember"
674>notMember</A
675> :: <A HREF="Data-IntMap.html#t%3AKey"
676>Key</A
677> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
678>IntMap</A
679> a -&gt; <A HREF="Prelude.html#t%3ABool"
680>Bool</A
681></TD
682></TR
683><TR
684><TD CLASS="s8"
685></TD
686></TR
687><TR
688><TD CLASS="decl"
689><A HREF="#v%3Alookup"
690>lookup</A
691> :: <A HREF="Prelude.html#t%3AMonad"
692>Monad</A
693> m =&gt; <A HREF="Data-IntMap.html#t%3AKey"
694>Key</A
695> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
696>IntMap</A
697> a -&gt; m a</TD
698></TR
699><TR
700><TD CLASS="s8"
701></TD
702></TR
703><TR
704><TD CLASS="decl"
705><A HREF="#v%3AfindWithDefault"
706>findWithDefault</A
707> :: a -&gt; <A HREF="Data-IntMap.html#t%3AKey"
708>Key</A
709> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
710>IntMap</A
711> a -&gt; a</TD
712></TR
713><TR
714><TD CLASS="s8"
715></TD
716></TR
717><TR
718><TD CLASS="decl"
719><A HREF="#v%3Aempty"
720>empty</A
721> :: <A HREF="Data-IntMap.html#t%3AIntMap"
722>IntMap</A
723> a</TD
724></TR
725><TR
726><TD CLASS="s8"
727></TD
728></TR
729><TR
730><TD CLASS="decl"
731><A HREF="#v%3Asingleton"
732>singleton</A
733> :: <A HREF="Data-IntMap.html#t%3AKey"
734>Key</A
735> -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
736>IntMap</A
737> a</TD
738></TR
739><TR
740><TD CLASS="s8"
741></TD
742></TR
743><TR
744><TD CLASS="decl"
745><A HREF="#v%3Ainsert"
746>insert</A
747> :: <A HREF="Data-IntMap.html#t%3AKey"
748>Key</A
749> -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
750>IntMap</A
751> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
752>IntMap</A
753> a</TD
754></TR
755><TR
756><TD CLASS="s8"
757></TD
758></TR
759><TR
760><TD CLASS="decl"
761><A HREF="#v%3AinsertWith"
762>insertWith</A
763> :: (a -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
764>Key</A
765> -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
766>IntMap</A
767> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
768>IntMap</A
769> a</TD
770></TR
771><TR
772><TD CLASS="s8"
773></TD
774></TR
775><TR
776><TD CLASS="decl"
777><A HREF="#v%3AinsertWithKey"
778>insertWithKey</A
779> :: (<A HREF="Data-IntMap.html#t%3AKey"
780>Key</A
781> -&gt; a -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
782>Key</A
783> -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
784>IntMap</A
785> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
786>IntMap</A
787> a</TD
788></TR
789><TR
790><TD CLASS="s8"
791></TD
792></TR
793><TR
794><TD CLASS="decl"
795><A HREF="#v%3AinsertLookupWithKey"
796>insertLookupWithKey</A
797> :: (<A HREF="Data-IntMap.html#t%3AKey"
798>Key</A
799> -&gt; a -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
800>Key</A
801> -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
802>IntMap</A
803> a -&gt; (<A HREF="Prelude.html#t%3AMaybe"
804>Maybe</A
805> a, <A HREF="Data-IntMap.html#t%3AIntMap"
806>IntMap</A
807> a)</TD
808></TR
809><TR
810><TD CLASS="s8"
811></TD
812></TR
813><TR
814><TD CLASS="decl"
815><A HREF="#v%3Adelete"
816>delete</A
817> :: <A HREF="Data-IntMap.html#t%3AKey"
818>Key</A
819> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
820>IntMap</A
821> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
822>IntMap</A
823> a</TD
824></TR
825><TR
826><TD CLASS="s8"
827></TD
828></TR
829><TR
830><TD CLASS="decl"
831><A HREF="#v%3Aadjust"
832>adjust</A
833> :: (a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
834>Key</A
835> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
836>IntMap</A
837> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
838>IntMap</A
839> a</TD
840></TR
841><TR
842><TD CLASS="s8"
843></TD
844></TR
845><TR
846><TD CLASS="decl"
847><A HREF="#v%3AadjustWithKey"
848>adjustWithKey</A
849> :: (<A HREF="Data-IntMap.html#t%3AKey"
850>Key</A
851> -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
852>Key</A
853> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
854>IntMap</A
855> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
856>IntMap</A
857> a</TD
858></TR
859><TR
860><TD CLASS="s8"
861></TD
862></TR
863><TR
864><TD CLASS="decl"
865><A HREF="#v%3Aupdate"
866>update</A
867> :: (a -&gt; <A HREF="Prelude.html#t%3AMaybe"
868>Maybe</A
869> a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
870>Key</A
871> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
872>IntMap</A
873> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
874>IntMap</A
875> a</TD
876></TR
877><TR
878><TD CLASS="s8"
879></TD
880></TR
881><TR
882><TD CLASS="decl"
883><A HREF="#v%3AupdateWithKey"
884>updateWithKey</A
885> :: (<A HREF="Data-IntMap.html#t%3AKey"
886>Key</A
887> -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
888>Maybe</A
889> a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
890>Key</A
891> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
892>IntMap</A
893> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
894>IntMap</A
895> a</TD
896></TR
897><TR
898><TD CLASS="s8"
899></TD
900></TR
901><TR
902><TD CLASS="decl"
903><A HREF="#v%3AupdateLookupWithKey"
904>updateLookupWithKey</A
905> :: (<A HREF="Data-IntMap.html#t%3AKey"
906>Key</A
907> -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
908>Maybe</A
909> a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
910>Key</A
911> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
912>IntMap</A
913> a -&gt; (<A HREF="Prelude.html#t%3AMaybe"
914>Maybe</A
915> a, <A HREF="Data-IntMap.html#t%3AIntMap"
916>IntMap</A
917> a)</TD
918></TR
919><TR
920><TD CLASS="s8"
921></TD
922></TR
923><TR
924><TD CLASS="decl"
925><A HREF="#v%3Aunion"
926>union</A
927> :: <A HREF="Data-IntMap.html#t%3AIntMap"
928>IntMap</A
929> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
930>IntMap</A
931> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
932>IntMap</A
933> a</TD
934></TR
935><TR
936><TD CLASS="s8"
937></TD
938></TR
939><TR
940><TD CLASS="decl"
941><A HREF="#v%3AunionWith"
942>unionWith</A
943> :: (a -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
944>IntMap</A
945> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
946>IntMap</A
947> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
948>IntMap</A
949> a</TD
950></TR
951><TR
952><TD CLASS="s8"
953></TD
954></TR
955><TR
956><TD CLASS="decl"
957><A HREF="#v%3AunionWithKey"
958>unionWithKey</A
959> :: (<A HREF="Data-IntMap.html#t%3AKey"
960>Key</A
961> -&gt; a -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
962>IntMap</A
963> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
964>IntMap</A
965> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
966>IntMap</A
967> a</TD
968></TR
969><TR
970><TD CLASS="s8"
971></TD
972></TR
973><TR
974><TD CLASS="decl"
975><A HREF="#v%3Aunions"
976>unions</A
977> :: [<A HREF="Data-IntMap.html#t%3AIntMap"
978>IntMap</A
979> a] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
980>IntMap</A
981> a</TD
982></TR
983><TR
984><TD CLASS="s8"
985></TD
986></TR
987><TR
988><TD CLASS="decl"
989><A HREF="#v%3AunionsWith"
990>unionsWith</A
991> :: (a -&gt; a -&gt; a) -&gt; [<A HREF="Data-IntMap.html#t%3AIntMap"
992>IntMap</A
993> a] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
994>IntMap</A
995> a</TD
996></TR
997><TR
998><TD CLASS="s8"
999></TD
1000></TR
1001><TR
1002><TD CLASS="decl"
1003><A HREF="#v%3Adifference"
1004>difference</A
1005> :: <A HREF="Data-IntMap.html#t%3AIntMap"
1006>IntMap</A
1007> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1008>IntMap</A
1009> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1010>IntMap</A
1011> a</TD
1012></TR
1013><TR
1014><TD CLASS="s8"
1015></TD
1016></TR
1017><TR
1018><TD CLASS="decl"
1019><A HREF="#v%3AdifferenceWith"
1020>differenceWith</A
1021> :: (a -&gt; b -&gt; <A HREF="Prelude.html#t%3AMaybe"
1022>Maybe</A
1023> a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1024>IntMap</A
1025> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1026>IntMap</A
1027> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1028>IntMap</A
1029> a</TD
1030></TR
1031><TR
1032><TD CLASS="s8"
1033></TD
1034></TR
1035><TR
1036><TD CLASS="decl"
1037><A HREF="#v%3AdifferenceWithKey"
1038>differenceWithKey</A
1039> :: (<A HREF="Data-IntMap.html#t%3AKey"
1040>Key</A
1041> -&gt; a -&gt; b -&gt; <A HREF="Prelude.html#t%3AMaybe"
1042>Maybe</A
1043> a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1044>IntMap</A
1045> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1046>IntMap</A
1047> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1048>IntMap</A
1049> a</TD
1050></TR
1051><TR
1052><TD CLASS="s8"
1053></TD
1054></TR
1055><TR
1056><TD CLASS="decl"
1057><A HREF="#v%3Aintersection"
1058>intersection</A
1059> :: <A HREF="Data-IntMap.html#t%3AIntMap"
1060>IntMap</A
1061> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1062>IntMap</A
1063> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1064>IntMap</A
1065> a</TD
1066></TR
1067><TR
1068><TD CLASS="s8"
1069></TD
1070></TR
1071><TR
1072><TD CLASS="decl"
1073><A HREF="#v%3AintersectionWith"
1074>intersectionWith</A
1075> :: (a -&gt; b -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1076>IntMap</A
1077> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1078>IntMap</A
1079> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1080>IntMap</A
1081> a</TD
1082></TR
1083><TR
1084><TD CLASS="s8"
1085></TD
1086></TR
1087><TR
1088><TD CLASS="decl"
1089><A HREF="#v%3AintersectionWithKey"
1090>intersectionWithKey</A
1091> :: (<A HREF="Data-IntMap.html#t%3AKey"
1092>Key</A
1093> -&gt; a -&gt; b -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1094>IntMap</A
1095> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1096>IntMap</A
1097> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1098>IntMap</A
1099> a</TD
1100></TR
1101><TR
1102><TD CLASS="s8"
1103></TD
1104></TR
1105><TR
1106><TD CLASS="decl"
1107><A HREF="#v%3Amap"
1108>map</A
1109> :: (a -&gt; b) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1110>IntMap</A
1111> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1112>IntMap</A
1113> b</TD
1114></TR
1115><TR
1116><TD CLASS="s8"
1117></TD
1118></TR
1119><TR
1120><TD CLASS="decl"
1121><A HREF="#v%3AmapWithKey"
1122>mapWithKey</A
1123> :: (<A HREF="Data-IntMap.html#t%3AKey"
1124>Key</A
1125> -&gt; a -&gt; b) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1126>IntMap</A
1127> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1128>IntMap</A
1129> b</TD
1130></TR
1131><TR
1132><TD CLASS="s8"
1133></TD
1134></TR
1135><TR
1136><TD CLASS="decl"
1137><A HREF="#v%3AmapAccum"
1138>mapAccum</A
1139> :: (a -&gt; b -&gt; (a, c)) -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1140>IntMap</A
1141> b -&gt; (a, <A HREF="Data-IntMap.html#t%3AIntMap"
1142>IntMap</A
1143> c)</TD
1144></TR
1145><TR
1146><TD CLASS="s8"
1147></TD
1148></TR
1149><TR
1150><TD CLASS="decl"
1151><A HREF="#v%3AmapAccumWithKey"
1152>mapAccumWithKey</A
1153> :: (a -&gt; <A HREF="Data-IntMap.html#t%3AKey"
1154>Key</A
1155> -&gt; b -&gt; (a, c)) -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1156>IntMap</A
1157> b -&gt; (a, <A HREF="Data-IntMap.html#t%3AIntMap"
1158>IntMap</A
1159> c)</TD
1160></TR
1161><TR
1162><TD CLASS="s8"
1163></TD
1164></TR
1165><TR
1166><TD CLASS="decl"
1167><A HREF="#v%3Afold"
1168>fold</A
1169> :: (a -&gt; b -&gt; b) -&gt; b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1170>IntMap</A
1171> a -&gt; b</TD
1172></TR
1173><TR
1174><TD CLASS="s8"
1175></TD
1176></TR
1177><TR
1178><TD CLASS="decl"
1179><A HREF="#v%3AfoldWithKey"
1180>foldWithKey</A
1181> :: (<A HREF="Data-IntMap.html#t%3AKey"
1182>Key</A
1183> -&gt; a -&gt; b -&gt; b) -&gt; b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1184>IntMap</A
1185> a -&gt; b</TD
1186></TR
1187><TR
1188><TD CLASS="s8"
1189></TD
1190></TR
1191><TR
1192><TD CLASS="decl"
1193><A HREF="#v%3Aelems"
1194>elems</A
1195> :: <A HREF="Data-IntMap.html#t%3AIntMap"
1196>IntMap</A
1197> a -&gt; [a]</TD
1198></TR
1199><TR
1200><TD CLASS="s8"
1201></TD
1202></TR
1203><TR
1204><TD CLASS="decl"
1205><A HREF="#v%3Akeys"
1206>keys</A
1207> :: <A HREF="Data-IntMap.html#t%3AIntMap"
1208>IntMap</A
1209> a -&gt; [<A HREF="Data-IntMap.html#t%3AKey"
1210>Key</A
1211>]</TD
1212></TR
1213><TR
1214><TD CLASS="s8"
1215></TD
1216></TR
1217><TR
1218><TD CLASS="decl"
1219><A HREF="#v%3AkeysSet"
1220>keysSet</A
1221> :: <A HREF="Data-IntMap.html#t%3AIntMap"
1222>IntMap</A
1223> a -&gt; IntSet</TD
1224></TR
1225><TR
1226><TD CLASS="s8"
1227></TD
1228></TR
1229><TR
1230><TD CLASS="decl"
1231><A HREF="#v%3Aassocs"
1232>assocs</A
1233> :: <A HREF="Data-IntMap.html#t%3AIntMap"
1234>IntMap</A
1235> a -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
1236>Key</A
1237>, a)]</TD
1238></TR
1239><TR
1240><TD CLASS="s8"
1241></TD
1242></TR
1243><TR
1244><TD CLASS="decl"
1245><A HREF="#v%3AtoList"
1246>toList</A
1247> :: <A HREF="Data-IntMap.html#t%3AIntMap"
1248>IntMap</A
1249> a -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
1250>Key</A
1251>, a)]</TD
1252></TR
1253><TR
1254><TD CLASS="s8"
1255></TD
1256></TR
1257><TR
1258><TD CLASS="decl"
1259><A HREF="#v%3AfromList"
1260>fromList</A
1261> :: [(<A HREF="Data-IntMap.html#t%3AKey"
1262>Key</A
1263>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1264>IntMap</A
1265> a</TD
1266></TR
1267><TR
1268><TD CLASS="s8"
1269></TD
1270></TR
1271><TR
1272><TD CLASS="decl"
1273><A HREF="#v%3AfromListWith"
1274>fromListWith</A
1275> :: (a -&gt; a -&gt; a) -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
1276>Key</A
1277>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1278>IntMap</A
1279> a</TD
1280></TR
1281><TR
1282><TD CLASS="s8"
1283></TD
1284></TR
1285><TR
1286><TD CLASS="decl"
1287><A HREF="#v%3AfromListWithKey"
1288>fromListWithKey</A
1289> :: (<A HREF="Data-IntMap.html#t%3AKey"
1290>Key</A
1291> -&gt; a -&gt; a -&gt; a) -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
1292>Key</A
1293>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1294>IntMap</A
1295> a</TD
1296></TR
1297><TR
1298><TD CLASS="s8"
1299></TD
1300></TR
1301><TR
1302><TD CLASS="decl"
1303><A HREF="#v%3AtoAscList"
1304>toAscList</A
1305> :: <A HREF="Data-IntMap.html#t%3AIntMap"
1306>IntMap</A
1307> a -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
1308>Key</A
1309>, a)]</TD
1310></TR
1311><TR
1312><TD CLASS="s8"
1313></TD
1314></TR
1315><TR
1316><TD CLASS="decl"
1317><A HREF="#v%3AfromAscList"
1318>fromAscList</A
1319> :: [(<A HREF="Data-IntMap.html#t%3AKey"
1320>Key</A
1321>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1322>IntMap</A
1323> a</TD
1324></TR
1325><TR
1326><TD CLASS="s8"
1327></TD
1328></TR
1329><TR
1330><TD CLASS="decl"
1331><A HREF="#v%3AfromAscListWith"
1332>fromAscListWith</A
1333> :: (a -&gt; a -&gt; a) -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
1334>Key</A
1335>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1336>IntMap</A
1337> a</TD
1338></TR
1339><TR
1340><TD CLASS="s8"
1341></TD
1342></TR
1343><TR
1344><TD CLASS="decl"
1345><A HREF="#v%3AfromAscListWithKey"
1346>fromAscListWithKey</A
1347> :: (<A HREF="Data-IntMap.html#t%3AKey"
1348>Key</A
1349> -&gt; a -&gt; a -&gt; a) -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
1350>Key</A
1351>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1352>IntMap</A
1353> a</TD
1354></TR
1355><TR
1356><TD CLASS="s8"
1357></TD
1358></TR
1359><TR
1360><TD CLASS="decl"
1361><A HREF="#v%3AfromDistinctAscList"
1362>fromDistinctAscList</A
1363> :: [(<A HREF="Data-IntMap.html#t%3AKey"
1364>Key</A
1365>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1366>IntMap</A
1367> a</TD
1368></TR
1369><TR
1370><TD CLASS="s8"
1371></TD
1372></TR
1373><TR
1374><TD CLASS="decl"
1375><A HREF="#v%3Afilter"
1376>filter</A
1377> :: (a -&gt; <A HREF="Prelude.html#t%3ABool"
1378>Bool</A
1379>) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1380>IntMap</A
1381> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1382>IntMap</A
1383> a</TD
1384></TR
1385><TR
1386><TD CLASS="s8"
1387></TD
1388></TR
1389><TR
1390><TD CLASS="decl"
1391><A HREF="#v%3AfilterWithKey"
1392>filterWithKey</A
1393> :: (<A HREF="Data-IntMap.html#t%3AKey"
1394>Key</A
1395> -&gt; a -&gt; <A HREF="Prelude.html#t%3ABool"
1396>Bool</A
1397>) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1398>IntMap</A
1399> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1400>IntMap</A
1401> a</TD
1402></TR
1403><TR
1404><TD CLASS="s8"
1405></TD
1406></TR
1407><TR
1408><TD CLASS="decl"
1409><A HREF="#v%3Apartition"
1410>partition</A
1411> :: (a -&gt; <A HREF="Prelude.html#t%3ABool"
1412>Bool</A
1413>) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1414>IntMap</A
1415> a -&gt; (<A HREF="Data-IntMap.html#t%3AIntMap"
1416>IntMap</A
1417> a, <A HREF="Data-IntMap.html#t%3AIntMap"
1418>IntMap</A
1419> a)</TD
1420></TR
1421><TR
1422><TD CLASS="s8"
1423></TD
1424></TR
1425><TR
1426><TD CLASS="decl"
1427><A HREF="#v%3ApartitionWithKey"
1428>partitionWithKey</A
1429> :: (<A HREF="Data-IntMap.html#t%3AKey"
1430>Key</A
1431> -&gt; a -&gt; <A HREF="Prelude.html#t%3ABool"
1432>Bool</A
1433>) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1434>IntMap</A
1435> a -&gt; (<A HREF="Data-IntMap.html#t%3AIntMap"
1436>IntMap</A
1437> a, <A HREF="Data-IntMap.html#t%3AIntMap"
1438>IntMap</A
1439> a)</TD
1440></TR
1441><TR
1442><TD CLASS="s8"
1443></TD
1444></TR
1445><TR
1446><TD CLASS="decl"
1447><A HREF="#v%3AmapMaybe"
1448>mapMaybe</A
1449> :: (a -&gt; <A HREF="Prelude.html#t%3AMaybe"
1450>Maybe</A
1451> b) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1452>IntMap</A
1453> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1454>IntMap</A
1455> b</TD
1456></TR
1457><TR
1458><TD CLASS="s8"
1459></TD
1460></TR
1461><TR
1462><TD CLASS="decl"
1463><A HREF="#v%3AmapMaybeWithKey"
1464>mapMaybeWithKey</A
1465> :: (<A HREF="Data-IntMap.html#t%3AKey"
1466>Key</A
1467> -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
1468>Maybe</A
1469> b) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1470>IntMap</A
1471> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1472>IntMap</A
1473> b</TD
1474></TR
1475><TR
1476><TD CLASS="s8"
1477></TD
1478></TR
1479><TR
1480><TD CLASS="decl"
1481><A HREF="#v%3AmapEither"
1482>mapEither</A
1483> :: (a -&gt; <A HREF="Prelude.html#t%3AEither"
1484>Either</A
1485> b c) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1486>IntMap</A
1487> a -&gt; (<A HREF="Data-IntMap.html#t%3AIntMap"
1488>IntMap</A
1489> b, <A HREF="Data-IntMap.html#t%3AIntMap"
1490>IntMap</A
1491> c)</TD
1492></TR
1493><TR
1494><TD CLASS="s8"
1495></TD
1496></TR
1497><TR
1498><TD CLASS="decl"
1499><A HREF="#v%3AmapEitherWithKey"
1500>mapEitherWithKey</A
1501> :: (<A HREF="Data-IntMap.html#t%3AKey"
1502>Key</A
1503> -&gt; a -&gt; <A HREF="Prelude.html#t%3AEither"
1504>Either</A
1505> b c) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1506>IntMap</A
1507> a -&gt; (<A HREF="Data-IntMap.html#t%3AIntMap"
1508>IntMap</A
1509> b, <A HREF="Data-IntMap.html#t%3AIntMap"
1510>IntMap</A
1511> c)</TD
1512></TR
1513><TR
1514><TD CLASS="s8"
1515></TD
1516></TR
1517><TR
1518><TD CLASS="decl"
1519><A HREF="#v%3Asplit"
1520>split</A
1521> :: <A HREF="Data-IntMap.html#t%3AKey"
1522>Key</A
1523> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1524>IntMap</A
1525> a -&gt; (<A HREF="Data-IntMap.html#t%3AIntMap"
1526>IntMap</A
1527> a, <A HREF="Data-IntMap.html#t%3AIntMap"
1528>IntMap</A
1529> a)</TD
1530></TR
1531><TR
1532><TD CLASS="s8"
1533></TD
1534></TR
1535><TR
1536><TD CLASS="decl"
1537><A HREF="#v%3AsplitLookup"
1538>splitLookup</A
1539> :: <A HREF="Data-IntMap.html#t%3AKey"
1540>Key</A
1541> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1542>IntMap</A
1543> a -&gt; (<A HREF="Data-IntMap.html#t%3AIntMap"
1544>IntMap</A
1545> a, <A HREF="Prelude.html#t%3AMaybe"
1546>Maybe</A
1547> a, <A HREF="Data-IntMap.html#t%3AIntMap"
1548>IntMap</A
1549> a)</TD
1550></TR
1551><TR
1552><TD CLASS="s8"
1553></TD
1554></TR
1555><TR
1556><TD CLASS="decl"
1557><A HREF="#v%3AisSubmapOf"
1558>isSubmapOf</A
1559> :: <A HREF="Prelude.html#t%3AEq"
1560>Eq</A
1561> a =&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1562>IntMap</A
1563> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1564>IntMap</A
1565> a -&gt; <A HREF="Prelude.html#t%3ABool"
1566>Bool</A
1567></TD
1568></TR
1569><TR
1570><TD CLASS="s8"
1571></TD
1572></TR
1573><TR
1574><TD CLASS="decl"
1575><A HREF="#v%3AisSubmapOfBy"
1576>isSubmapOfBy</A
1577> :: (a -&gt; b -&gt; <A HREF="Prelude.html#t%3ABool"
1578>Bool</A
1579>) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1580>IntMap</A
1581> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1582>IntMap</A
1583> b -&gt; <A HREF="Prelude.html#t%3ABool"
1584>Bool</A
1585></TD
1586></TR
1587><TR
1588><TD CLASS="s8"
1589></TD
1590></TR
1591><TR
1592><TD CLASS="decl"
1593><A HREF="#v%3AisProperSubmapOf"
1594>isProperSubmapOf</A
1595> :: <A HREF="Prelude.html#t%3AEq"
1596>Eq</A
1597> a =&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1598>IntMap</A
1599> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1600>IntMap</A
1601> a -&gt; <A HREF="Prelude.html#t%3ABool"
1602>Bool</A
1603></TD
1604></TR
1605><TR
1606><TD CLASS="s8"
1607></TD
1608></TR
1609><TR
1610><TD CLASS="decl"
1611><A HREF="#v%3AisProperSubmapOfBy"
1612>isProperSubmapOfBy</A
1613> :: (a -&gt; b -&gt; <A HREF="Prelude.html#t%3ABool"
1614>Bool</A
1615>) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1616>IntMap</A
1617> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1618>IntMap</A
1619> b -&gt; <A HREF="Prelude.html#t%3ABool"
1620>Bool</A
1621></TD
1622></TR
1623><TR
1624><TD CLASS="s8"
1625></TD
1626></TR
1627><TR
1628><TD CLASS="decl"
1629><A HREF="#v%3AupdateMin"
1630>updateMin</A
1631> :: (a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1632>IntMap</A
1633> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1634>IntMap</A
1635> a</TD
1636></TR
1637><TR
1638><TD CLASS="s8"
1639></TD
1640></TR
1641><TR
1642><TD CLASS="decl"
1643><A HREF="#v%3AupdateMax"
1644>updateMax</A
1645> :: (a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1646>IntMap</A
1647> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1648>IntMap</A
1649> a</TD
1650></TR
1651><TR
1652><TD CLASS="s8"
1653></TD
1654></TR
1655><TR
1656><TD CLASS="decl"
1657><A HREF="#v%3AupdateMinWithKey"
1658>updateMinWithKey</A
1659> :: (<A HREF="Data-IntMap.html#t%3AKey"
1660>Key</A
1661> -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1662>IntMap</A
1663> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1664>IntMap</A
1665> a</TD
1666></TR
1667><TR
1668><TD CLASS="s8"
1669></TD
1670></TR
1671><TR
1672><TD CLASS="decl"
1673><A HREF="#v%3AupdateMaxWithKey"
1674>updateMaxWithKey</A
1675> :: (<A HREF="Data-IntMap.html#t%3AKey"
1676>Key</A
1677> -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1678>IntMap</A
1679> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1680>IntMap</A
1681> a</TD
1682></TR
1683><TR
1684><TD CLASS="s8"
1685></TD
1686></TR
1687><TR
1688><TD CLASS="decl"
1689><A HREF="#v%3AminViewWithKey"
1690>minViewWithKey</A
1691> :: <A HREF="Prelude.html#t%3AMonad"
1692>Monad</A
1693> m =&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1694>IntMap</A
1695> a -&gt; m ((<A HREF="Data-IntMap.html#t%3AKey"
1696>Key</A
1697>, a), <A HREF="Data-IntMap.html#t%3AIntMap"
1698>IntMap</A
1699> a)</TD
1700></TR
1701><TR
1702><TD CLASS="s8"
1703></TD
1704></TR
1705><TR
1706><TD CLASS="decl"
1707><A HREF="#v%3AmaxViewWithKey"
1708>maxViewWithKey</A
1709> :: <A HREF="Prelude.html#t%3AMonad"
1710>Monad</A
1711> m =&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1712>IntMap</A
1713> a -&gt; m ((<A HREF="Data-IntMap.html#t%3AKey"
1714>Key</A
1715>, a), <A HREF="Data-IntMap.html#t%3AIntMap"
1716>IntMap</A
1717> a)</TD
1718></TR
1719><TR
1720><TD CLASS="s8"
1721></TD
1722></TR
1723><TR
1724><TD CLASS="decl"
1725><A HREF="#v%3AshowTree"
1726>showTree</A
1727> :: <A HREF="Prelude.html#t%3AShow"
1728>Show</A
1729> a =&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1730>IntMap</A
1731> a -&gt; <A HREF="Prelude.html#t%3AString"
1732>String</A
1733></TD
1734></TR
1735><TR
1736><TD CLASS="s8"
1737></TD
1738></TR
1739><TR
1740><TD CLASS="decl"
1741><A HREF="#v%3AshowTreeWith"
1742>showTreeWith</A
1743> :: <A HREF="Prelude.html#t%3AShow"
1744>Show</A
1745> a =&gt; <A HREF="Prelude.html#t%3ABool"
1746>Bool</A
1747> -&gt; <A HREF="Prelude.html#t%3ABool"
1748>Bool</A
1749> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1750>IntMap</A
1751> a -&gt; <A HREF="Prelude.html#t%3AString"
1752>String</A
1753></TD
1754></TR
1755></TABLE
1756></TD
1757></TR
1758><TR
1759><TD CLASS="s15"
1760></TD
1761></TR
1762><TR
1763><TD CLASS="s15"
1764></TD
1765></TR
1766><TR
1767><TD CLASS="section1"
1768><A NAME="1"
1769>Map type
1770</A
1771></TD
1772></TR
1773><TR
1774><TD CLASS="s15"
1775></TD
1776></TR
1777><TR
1778><TD CLASS="decl"
1779><SPAN CLASS="keyword"
1780>data</SPAN
1781> <A NAME="t%3AIntMap"
1782></A
1783><B
1784>IntMap</B
1785> a</TD
1786></TR
1787><TR
1788><TD CLASS="body"
1789><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
1790><TR
1791><TD CLASS="ndoc"
1792>A map of integers to values <TT
1793>a</TT
1794>.
1795</TD
1796></TR
1797><TR
1798><TD CLASS="section4"
1799><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:IntMap')" ALT="show/hide"
1800> Instances</TD
1801></TR
1802><TR
1803><TD CLASS="body"
1804><DIV ID="i:IntMap" STYLE="display:block;"
1805><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"
1806><TR
1807><TD CLASS="decl"
1808>Foldable <A HREF="Data-IntMap.html#t%3AIntMap"
1809>IntMap</A
1810></TD
1811></TR
1812><TR
1813><TD CLASS="decl"
1814><A HREF="Prelude.html#t%3AFunctor"
1815>Functor</A
1816> <A HREF="Data-IntMap.html#t%3AIntMap"
1817>IntMap</A
1818></TD
1819></TR
1820><TR
1821><TD CLASS="decl"
1822>Typeable1 <A HREF="Data-IntMap.html#t%3AIntMap"
1823>IntMap</A
1824></TD
1825></TR
1826><TR
1827><TD CLASS="decl"
1828>Data a =&gt; Data (<A HREF="Data-IntMap.html#t%3AIntMap"
1829>IntMap</A
1830> a)</TD
1831></TR
1832><TR
1833><TD CLASS="decl"
1834><A HREF="Prelude.html#t%3AEq"
1835>Eq</A
1836> a =&gt; <A HREF="Prelude.html#t%3AEq"
1837>Eq</A
1838> (<A HREF="Data-IntMap.html#t%3AIntMap"
1839>IntMap</A
1840> a)</TD
1841></TR
1842><TR
1843><TD CLASS="decl"
1844>Monoid (<A HREF="Data-IntMap.html#t%3AIntMap"
1845>IntMap</A
1846> a)</TD
1847></TR
1848><TR
1849><TD CLASS="decl"
1850><A HREF="Prelude.html#t%3AOrd"
1851>Ord</A
1852> a =&gt; <A HREF="Prelude.html#t%3AOrd"
1853>Ord</A
1854> (<A HREF="Data-IntMap.html#t%3AIntMap"
1855>IntMap</A
1856> a)</TD
1857></TR
1858><TR
1859><TD CLASS="decl"
1860><A HREF="Prelude.html#t%3ARead"
1861>Read</A
1862> e =&gt; <A HREF="Prelude.html#t%3ARead"
1863>Read</A
1864> (<A HREF="Data-IntMap.html#t%3AIntMap"
1865>IntMap</A
1866> e)</TD
1867></TR
1868><TR
1869><TD CLASS="decl"
1870><A HREF="Prelude.html#t%3AShow"
1871>Show</A
1872> a =&gt; <A HREF="Prelude.html#t%3AShow"
1873>Show</A
1874> (<A HREF="Data-IntMap.html#t%3AIntMap"
1875>IntMap</A
1876> a)</TD
1877></TR
1878></TABLE
1879></DIV
1880></TD
1881></TR
1882></TABLE
1883></TD
1884></TR
1885><TR
1886><TD CLASS="s15"
1887></TD
1888></TR
1889><TR
1890><TD CLASS="decl"
1891><SPAN CLASS="keyword"
1892>type</SPAN
1893> <A NAME="t%3AKey"
1894></A
1895><B
1896>Key</B
1897> = <A HREF="Prelude.html#t%3AInt"
1898>Int</A
1899></TD
1900></TR
1901><TR
1902><TD CLASS="s15"
1903></TD
1904></TR
1905><TR
1906><TD CLASS="section1"
1907><A NAME="2"
1908>Operators
1909</A
1910></TD
1911></TR
1912><TR
1913><TD CLASS="s15"
1914></TD
1915></TR
1916><TR
1917><TD CLASS="decl"
1918><A NAME="v%3A%21"
1919></A
1920><B
1921>(!)</B
1922> :: <A HREF="Data-IntMap.html#t%3AIntMap"
1923>IntMap</A
1924> a -&gt; <A HREF="Data-IntMap.html#t%3AKey"
1925>Key</A
1926> -&gt; a</TD
1927></TR
1928><TR
1929><TD CLASS="doc"
1930><P
1931><EM
1932>O(min(n,W))</EM
1933>. Find the value at a key.
1934 Calls <TT
1935><A HREF="Prelude.html#v%3Aerror"
1936>error</A
1937></TT
1938> when the element can not be found.
1939</P
1940><PRE
1941> fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map
1942 fromList [(5,'a'), (3,'b')] ! 5 == 'a'
1943</PRE
1944></TD
1945></TR
1946><TR
1947><TD CLASS="s15"
1948></TD
1949></TR
1950><TR
1951><TD CLASS="decl"
1952><A NAME="v%3A%5C%5C"
1953></A
1954><B
1955>(\\)</B
1956> :: <A HREF="Data-IntMap.html#t%3AIntMap"
1957>IntMap</A
1958> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1959>IntMap</A
1960> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
1961>IntMap</A
1962> a</TD
1963></TR
1964><TR
1965><TD CLASS="doc"
1966>Same as <TT
1967><A HREF="Data-IntMap.html#v%3Adifference"
1968>difference</A
1969></TT
1970>.
1971</TD
1972></TR
1973><TR
1974><TD CLASS="s15"
1975></TD
1976></TR
1977><TR
1978><TD CLASS="section1"
1979><A NAME="3"
1980>Query
1981</A
1982></TD
1983></TR
1984><TR
1985><TD CLASS="s15"
1986></TD
1987></TR
1988><TR
1989><TD CLASS="decl"
1990><A NAME="v%3Anull"
1991></A
1992><B
1993>null</B
1994> :: <A HREF="Data-IntMap.html#t%3AIntMap"
1995>IntMap</A
1996> a -&gt; <A HREF="Prelude.html#t%3ABool"
1997>Bool</A
1998></TD
1999></TR
2000><TR
2001><TD CLASS="doc"
2002><P
2003><EM
2004>O(1)</EM
2005>. Is the map empty?
2006</P
2007><PRE
2008> Data.IntMap.null (empty)           == True
2009 Data.IntMap.null (singleton 1 'a') == False
2010</PRE
2011></TD
2012></TR
2013><TR
2014><TD CLASS="s15"
2015></TD
2016></TR
2017><TR
2018><TD CLASS="decl"
2019><A NAME="v%3Asize"
2020></A
2021><B
2022>size</B
2023> :: <A HREF="Data-IntMap.html#t%3AIntMap"
2024>IntMap</A
2025> a -&gt; <A HREF="Prelude.html#t%3AInt"
2026>Int</A
2027></TD
2028></TR
2029><TR
2030><TD CLASS="doc"
2031><P
2032><EM
2033>O(n)</EM
2034>. Number of elements in the map.
2035</P
2036><PRE
2037> size empty                                   == 0
2038 size (singleton 1 'a')                       == 1
2039 size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
2040</PRE
2041></TD
2042></TR
2043><TR
2044><TD CLASS="s15"
2045></TD
2046></TR
2047><TR
2048><TD CLASS="decl"
2049><A NAME="v%3Amember"
2050></A
2051><B
2052>member</B
2053> :: <A HREF="Data-IntMap.html#t%3AKey"
2054>Key</A
2055> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2056>IntMap</A
2057> a -&gt; <A HREF="Prelude.html#t%3ABool"
2058>Bool</A
2059></TD
2060></TR
2061><TR
2062><TD CLASS="doc"
2063><P
2064><EM
2065>O(min(n,W))</EM
2066>. Is the key a member of the map?
2067</P
2068><PRE
2069> member 5 (fromList [(5,'a'), (3,'b')]) == True
2070 member 1 (fromList [(5,'a'), (3,'b')]) == False
2071</PRE
2072></TD
2073></TR
2074><TR
2075><TD CLASS="s15"
2076></TD
2077></TR
2078><TR
2079><TD CLASS="decl"
2080><A NAME="v%3AnotMember"
2081></A
2082><B
2083>notMember</B
2084> :: <A HREF="Data-IntMap.html#t%3AKey"
2085>Key</A
2086> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2087>IntMap</A
2088> a -&gt; <A HREF="Prelude.html#t%3ABool"
2089>Bool</A
2090></TD
2091></TR
2092><TR
2093><TD CLASS="doc"
2094><P
2095><EM
2096>O(log n)</EM
2097>. Is the key not a member of the map?
2098</P
2099><PRE
2100> notMember 5 (fromList [(5,'a'), (3,'b')]) == False
2101 notMember 1 (fromList [(5,'a'), (3,'b')]) == True
2102</PRE
2103></TD
2104></TR
2105><TR
2106><TD CLASS="s15"
2107></TD
2108></TR
2109><TR
2110><TD CLASS="decl"
2111><A NAME="v%3Alookup"
2112></A
2113><B
2114>lookup</B
2115> :: <A HREF="Prelude.html#t%3AMonad"
2116>Monad</A
2117> m =&gt; <A HREF="Data-IntMap.html#t%3AKey"
2118>Key</A
2119> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2120>IntMap</A
2121> a -&gt; m a</TD
2122></TR
2123><TR
2124><TD CLASS="doc"
2125><EM
2126>O(min(n,W))</EM
2127>. Lookup the value at a key in the map. See also <TT
2128><A HREF="Data-Map.html#v%3Alookup"
2129>lookup</A
2130></TT
2131>.
2132</TD
2133></TR
2134><TR
2135><TD CLASS="s15"
2136></TD
2137></TR
2138><TR
2139><TD CLASS="decl"
2140><A NAME="v%3AfindWithDefault"
2141></A
2142><B
2143>findWithDefault</B
2144> :: a -&gt; <A HREF="Data-IntMap.html#t%3AKey"
2145>Key</A
2146> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2147>IntMap</A
2148> a -&gt; a</TD
2149></TR
2150><TR
2151><TD CLASS="doc"
2152><P
2153><EM
2154>O(min(n,W))</EM
2155>. The expression <TT
2156>(<TT
2157><A HREF="Data-IntMap.html#v%3AfindWithDefault"
2158>findWithDefault</A
2159></TT
2160> def k map)</TT
2161>
2162 returns the value at key <TT
2163>k</TT
2164> or returns <TT
2165>def</TT
2166> when the key is not an
2167 element of the map.
2168</P
2169><PRE
2170> findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
2171 findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
2172</PRE
2173></TD
2174></TR
2175><TR
2176><TD CLASS="s15"
2177></TD
2178></TR
2179><TR
2180><TD CLASS="section1"
2181><A NAME="4"
2182>Construction
2183</A
2184></TD
2185></TR
2186><TR
2187><TD CLASS="s15"
2188></TD
2189></TR
2190><TR
2191><TD CLASS="decl"
2192><A NAME="v%3Aempty"
2193></A
2194><B
2195>empty</B
2196> :: <A HREF="Data-IntMap.html#t%3AIntMap"
2197>IntMap</A
2198> a</TD
2199></TR
2200><TR
2201><TD CLASS="doc"
2202><P
2203><EM
2204>O(1)</EM
2205>. The empty map.
2206</P
2207><PRE
2208> empty      == fromList []
2209 size empty == 0
2210</PRE
2211></TD
2212></TR
2213><TR
2214><TD CLASS="s15"
2215></TD
2216></TR
2217><TR
2218><TD CLASS="decl"
2219><A NAME="v%3Asingleton"
2220></A
2221><B
2222>singleton</B
2223> :: <A HREF="Data-IntMap.html#t%3AKey"
2224>Key</A
2225> -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2226>IntMap</A
2227> a</TD
2228></TR
2229><TR
2230><TD CLASS="doc"
2231><P
2232><EM
2233>O(1)</EM
2234>. A map of one element.
2235</P
2236><PRE
2237> singleton 1 'a'        == fromList [(1, 'a')]
2238 size (singleton 1 'a') == 1
2239</PRE
2240></TD
2241></TR
2242><TR
2243><TD CLASS="s15"
2244></TD
2245></TR
2246><TR
2247><TD CLASS="section2"
2248><A NAME="5"
2249>Insertion
2250</A
2251></TD
2252></TR
2253><TR
2254><TD CLASS="s15"
2255></TD
2256></TR
2257><TR
2258><TD CLASS="decl"
2259><A NAME="v%3Ainsert"
2260></A
2261><B
2262>insert</B
2263> :: <A HREF="Data-IntMap.html#t%3AKey"
2264>Key</A
2265> -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2266>IntMap</A
2267> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2268>IntMap</A
2269> a</TD
2270></TR
2271><TR
2272><TD CLASS="doc"
2273><P
2274><EM
2275>O(min(n,W))</EM
2276>. Insert a new key/value pair in the map.
2277 If the key is already present in the map, the associated value is
2278 replaced with the supplied value, i.e. <TT
2279><A HREF="Data-IntMap.html#v%3Ainsert"
2280>insert</A
2281></TT
2282> is equivalent to
2283 <TT
2284><TT
2285><A HREF="Data-IntMap.html#v%3AinsertWith"
2286>insertWith</A
2287></TT
2288> <TT
2289><A HREF="Prelude.html#v%3Aconst"
2290>const</A
2291></TT
2292></TT
2293>.
2294</P
2295><PRE
2296> insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]
2297 insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]
2298 insert 5 'x' empty                         == singleton 5 'x'
2299</PRE
2300></TD
2301></TR
2302><TR
2303><TD CLASS="s15"
2304></TD
2305></TR
2306><TR
2307><TD CLASS="decl"
2308><A NAME="v%3AinsertWith"
2309></A
2310><B
2311>insertWith</B
2312> :: (a -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
2313>Key</A
2314> -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2315>IntMap</A
2316> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2317>IntMap</A
2318> a</TD
2319></TR
2320><TR
2321><TD CLASS="doc"
2322><P
2323><EM
2324>O(min(n,W))</EM
2325>. Insert with a combining function.
2326 <TT
2327><TT
2328><A HREF="Data-IntMap.html#v%3AinsertWith"
2329>insertWith</A
2330></TT
2331> f key value mp</TT
2332> 
2333 will insert the pair (key, value) into <TT
2334>mp</TT
2335> if key does
2336 not exist in the map. If the key does exist, the function will
2337 insert <TT
2338>f new_value old_value</TT
2339>.
2340</P
2341><PRE
2342> insertWith (++) 5 &quot;xxx&quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;xxxa&quot;)]
2343 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;)]
2344 insertWith (++) 5 &quot;xxx&quot; empty                         == singleton 5 &quot;xxx&quot;
2345</PRE
2346></TD
2347></TR
2348><TR
2349><TD CLASS="s15"
2350></TD
2351></TR
2352><TR
2353><TD CLASS="decl"
2354><A NAME="v%3AinsertWithKey"
2355></A
2356><B
2357>insertWithKey</B
2358> :: (<A HREF="Data-IntMap.html#t%3AKey"
2359>Key</A
2360> -&gt; a -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
2361>Key</A
2362> -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2363>IntMap</A
2364> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2365>IntMap</A
2366> a</TD
2367></TR
2368><TR
2369><TD CLASS="doc"
2370><P
2371><EM
2372>O(min(n,W))</EM
2373>. Insert with a combining function.
2374 <TT
2375><TT
2376><A HREF="Data-IntMap.html#v%3AinsertWithKey"
2377>insertWithKey</A
2378></TT
2379> f key value mp</TT
2380> 
2381 will insert the pair (key, value) into <TT
2382>mp</TT
2383> if key does
2384 not exist in the map. If the key does exist, the function will
2385 insert <TT
2386>f key new_value old_value</TT
2387>.
2388</P
2389><PRE
2390> let f key new_value old_value = (show key) ++ &quot;:&quot; ++ new_value ++ &quot;|&quot; ++ old_value
2391 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;)]
2392 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;)]
2393 insertWithKey f 5 &quot;xxx&quot; empty                         == singleton 5 &quot;xxx&quot;
2394</PRE
2395></TD
2396></TR
2397><TR
2398><TD CLASS="s15"
2399></TD
2400></TR
2401><TR
2402><TD CLASS="decl"
2403><A NAME="v%3AinsertLookupWithKey"
2404></A
2405><B
2406>insertLookupWithKey</B
2407> :: (<A HREF="Data-IntMap.html#t%3AKey"
2408>Key</A
2409> -&gt; a -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
2410>Key</A
2411> -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2412>IntMap</A
2413> a -&gt; (<A HREF="Prelude.html#t%3AMaybe"
2414>Maybe</A
2415> a, <A HREF="Data-IntMap.html#t%3AIntMap"
2416>IntMap</A
2417> a)</TD
2418></TR
2419><TR
2420><TD CLASS="doc"
2421><P
2422><EM
2423>O(min(n,W))</EM
2424>. The expression (<TT
2425><TT
2426><A HREF="Data-IntMap.html#v%3AinsertLookupWithKey"
2427>insertLookupWithKey</A
2428></TT
2429> f k x map</TT
2430>)
2431 is a pair where the first element is equal to (<TT
2432><TT
2433><A HREF="Data-IntMap.html#v%3Alookup"
2434>lookup</A
2435></TT
2436> k map</TT
2437>)
2438 and the second element equal to (<TT
2439><TT
2440><A HREF="Data-IntMap.html#v%3AinsertWithKey"
2441>insertWithKey</A
2442></TT
2443> f k x map</TT
2444>).
2445</P
2446><PRE
2447> let f key new_value old_value = (show key) ++ &quot;:&quot; ++ new_value ++ &quot;|&quot; ++ old_value
2448 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;)])
2449 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;)])
2450 insertLookupWithKey f 5 &quot;xxx&quot; empty                         == (Nothing,  singleton 5 &quot;xxx&quot;)
2451</PRE
2452><P
2453>This is how to define <TT
2454>insertLookup</TT
2455> using <TT
2456>insertLookupWithKey</TT
2457>:
2458</P
2459><PRE
2460> let insertLookup kx x t = insertLookupWithKey (\_ a _ -&gt; a) kx x t
2461 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;)])
2462 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;)])
2463</PRE
2464></TD
2465></TR
2466><TR
2467><TD CLASS="s15"
2468></TD
2469></TR
2470><TR
2471><TD CLASS="section2"
2472><A NAME="6"
2473>Delete/Update
2474</A
2475></TD
2476></TR
2477><TR
2478><TD CLASS="s15"
2479></TD
2480></TR
2481><TR
2482><TD CLASS="decl"
2483><A NAME="v%3Adelete"
2484></A
2485><B
2486>delete</B
2487> :: <A HREF="Data-IntMap.html#t%3AKey"
2488>Key</A
2489> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2490>IntMap</A
2491> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2492>IntMap</A
2493> a</TD
2494></TR
2495><TR
2496><TD CLASS="doc"
2497><P
2498><EM
2499>O(min(n,W))</EM
2500>. Delete a key and its value from the map. When the key is not
2501 a member of the map, the original map is returned.
2502</P
2503><PRE
2504> delete 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;b&quot;
2505 delete 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
2506 delete 5 empty                         == empty
2507</PRE
2508></TD
2509></TR
2510><TR
2511><TD CLASS="s15"
2512></TD
2513></TR
2514><TR
2515><TD CLASS="decl"
2516><A NAME="v%3Aadjust"
2517></A
2518><B
2519>adjust</B
2520> :: (a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
2521>Key</A
2522> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2523>IntMap</A
2524> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2525>IntMap</A
2526> a</TD
2527></TR
2528><TR
2529><TD CLASS="doc"
2530><P
2531><EM
2532>O(min(n,W))</EM
2533>. Adjust a value at a specific key. When the key is not
2534 a member of the map, the original map is returned.
2535</P
2536><PRE
2537> adjust (&quot;new &quot; ++) 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;new a&quot;)]
2538 adjust (&quot;new &quot; ++) 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
2539 adjust (&quot;new &quot; ++) 7 empty                         == empty
2540</PRE
2541></TD
2542></TR
2543><TR
2544><TD CLASS="s15"
2545></TD
2546></TR
2547><TR
2548><TD CLASS="decl"
2549><A NAME="v%3AadjustWithKey"
2550></A
2551><B
2552>adjustWithKey</B
2553> :: (<A HREF="Data-IntMap.html#t%3AKey"
2554>Key</A
2555> -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
2556>Key</A
2557> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2558>IntMap</A
2559> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2560>IntMap</A
2561> a</TD
2562></TR
2563><TR
2564><TD CLASS="doc"
2565><P
2566><EM
2567>O(min(n,W))</EM
2568>. Adjust a value at a specific key. When the key is not
2569 a member of the map, the original map is returned.
2570</P
2571><PRE
2572> let f key x = (show key) ++ &quot;:new &quot; ++ x
2573 adjustWithKey f 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;5:new a&quot;)]
2574 adjustWithKey f 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
2575 adjustWithKey f 7 empty                         == empty
2576</PRE
2577></TD
2578></TR
2579><TR
2580><TD CLASS="s15"
2581></TD
2582></TR
2583><TR
2584><TD CLASS="decl"
2585><A NAME="v%3Aupdate"
2586></A
2587><B
2588>update</B
2589> :: (a -&gt; <A HREF="Prelude.html#t%3AMaybe"
2590>Maybe</A
2591> a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
2592>Key</A
2593> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2594>IntMap</A
2595> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2596>IntMap</A
2597> a</TD
2598></TR
2599><TR
2600><TD CLASS="doc"
2601><P
2602><EM
2603>O(min(n,W))</EM
2604>. The expression (<TT
2605><TT
2606><A HREF="Data-IntMap.html#v%3Aupdate"
2607>update</A
2608></TT
2609> f k map</TT
2610>) updates the value <TT
2611>x</TT
2612>
2613 at <TT
2614>k</TT
2615> (if it is in the map). If (<TT
2616>f x</TT
2617>) is <TT
2618><A HREF="Prelude.html#v%3ANothing"
2619>Nothing</A
2620></TT
2621>, the element is
2622 deleted. If it is (<TT
2623><TT
2624><A HREF="Prelude.html#v%3AJust"
2625>Just</A
2626></TT
2627> y</TT
2628>), the key <TT
2629>k</TT
2630> is bound to the new value <TT
2631>y</TT
2632>.
2633</P
2634><PRE
2635> let f x = if x == &quot;a&quot; then Just &quot;new a&quot; else Nothing
2636 update f 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;new a&quot;)]
2637 update f 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
2638 update f 3 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;a&quot;
2639</PRE
2640></TD
2641></TR
2642><TR
2643><TD CLASS="s15"
2644></TD
2645></TR
2646><TR
2647><TD CLASS="decl"
2648><A NAME="v%3AupdateWithKey"
2649></A
2650><B
2651>updateWithKey</B
2652> :: (<A HREF="Data-IntMap.html#t%3AKey"
2653>Key</A
2654> -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
2655>Maybe</A
2656> a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
2657>Key</A
2658> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2659>IntMap</A
2660> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2661>IntMap</A
2662> a</TD
2663></TR
2664><TR
2665><TD CLASS="doc"
2666><P
2667><EM
2668>O(min(n,W))</EM
2669>. The expression (<TT
2670><TT
2671><A HREF="Data-IntMap.html#v%3Aupdate"
2672>update</A
2673></TT
2674> f k map</TT
2675>) updates the value <TT
2676>x</TT
2677>
2678 at <TT
2679>k</TT
2680> (if it is in the map). If (<TT
2681>f k x</TT
2682>) is <TT
2683><A HREF="Prelude.html#v%3ANothing"
2684>Nothing</A
2685></TT
2686>, the element is
2687 deleted. If it is (<TT
2688><TT
2689><A HREF="Prelude.html#v%3AJust"
2690>Just</A
2691></TT
2692> y</TT
2693>), the key <TT
2694>k</TT
2695> is bound to the new value <TT
2696>y</TT
2697>.
2698</P
2699><PRE
2700> let f k x = if x == &quot;a&quot; then Just ((show k) ++ &quot;:new a&quot;) else Nothing
2701 updateWithKey f 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;5:new a&quot;)]
2702 updateWithKey f 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
2703 updateWithKey f 3 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;a&quot;
2704</PRE
2705></TD
2706></TR
2707><TR
2708><TD CLASS="s15"
2709></TD
2710></TR
2711><TR
2712><TD CLASS="decl"
2713><A NAME="v%3AupdateLookupWithKey"
2714></A
2715><B
2716>updateLookupWithKey</B
2717> :: (<A HREF="Data-IntMap.html#t%3AKey"
2718>Key</A
2719> -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
2720>Maybe</A
2721> a) -&gt; <A HREF="Data-IntMap.html#t%3AKey"
2722>Key</A
2723> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2724>IntMap</A
2725> a -&gt; (<A HREF="Prelude.html#t%3AMaybe"
2726>Maybe</A
2727> a, <A HREF="Data-IntMap.html#t%3AIntMap"
2728>IntMap</A
2729> a)</TD
2730></TR
2731><TR
2732><TD CLASS="doc"
2733><P
2734><EM
2735>O(min(n,W))</EM
2736>. Lookup and update.
2737 The function returns original value, if it is updated.
2738 <EM
2739>Attention</EM
2740>: this is different behavior than <TT
2741><A HREF="Data-Map.html#v%3AupdateLookupWithKey"
2742>updateLookupWithKey</A
2743></TT
2744>!
2745 Returns the original key value if the map entry is deleted.
2746</P
2747><PRE
2748> let f k x = if x == &quot;a&quot; then Just ((show k) ++ &quot;:new a&quot;) else Nothing
2749 updateLookupWithKey f 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (Just &quot;a&quot;, fromList [(3, &quot;b&quot;), (5, &quot;5:new a&quot;)])
2750 updateLookupWithKey f 7 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (Nothing,  fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)])
2751 updateLookupWithKey f 3 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (Just &quot;b&quot;, singleton 5 &quot;a&quot;)
2752</PRE
2753></TD
2754></TR
2755><TR
2756><TD CLASS="s15"
2757></TD
2758></TR
2759><TR
2760><TD CLASS="section1"
2761><A NAME="7"
2762>Combine
2763</A
2764></TD
2765></TR
2766><TR
2767><TD CLASS="s15"
2768></TD
2769></TR
2770><TR
2771><TD CLASS="section2"
2772><A NAME="8"
2773>Union
2774</A
2775></TD
2776></TR
2777><TR
2778><TD CLASS="s15"
2779></TD
2780></TR
2781><TR
2782><TD CLASS="decl"
2783><A NAME="v%3Aunion"
2784></A
2785><B
2786>union</B
2787> :: <A HREF="Data-IntMap.html#t%3AIntMap"
2788>IntMap</A
2789> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2790>IntMap</A
2791> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2792>IntMap</A
2793> a</TD
2794></TR
2795><TR
2796><TD CLASS="doc"
2797><P
2798><EM
2799>O(n+m)</EM
2800>. The (left-biased) union of two maps.
2801 It prefers the first map when duplicate keys are encountered,
2802 i.e. (<TT
2803><TT
2804><A HREF="Data-IntMap.html#v%3Aunion"
2805>union</A
2806></TT
2807> == <TT
2808><A HREF="Data-IntMap.html#v%3AunionWith"
2809>unionWith</A
2810></TT
2811> <TT
2812><A HREF="Prelude.html#v%3Aconst"
2813>const</A
2814></TT
2815></TT
2816>).
2817</P
2818><PRE
2819> 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;)]
2820</PRE
2821></TD
2822></TR
2823><TR
2824><TD CLASS="s15"
2825></TD
2826></TR
2827><TR
2828><TD CLASS="decl"
2829><A NAME="v%3AunionWith"
2830></A
2831><B
2832>unionWith</B
2833> :: (a -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2834>IntMap</A
2835> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2836>IntMap</A
2837> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2838>IntMap</A
2839> a</TD
2840></TR
2841><TR
2842><TD CLASS="doc"
2843><P
2844><EM
2845>O(n+m)</EM
2846>. The union with a combining function.
2847</P
2848><PRE
2849> 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;)]
2850</PRE
2851></TD
2852></TR
2853><TR
2854><TD CLASS="s15"
2855></TD
2856></TR
2857><TR
2858><TD CLASS="decl"
2859><A NAME="v%3AunionWithKey"
2860></A
2861><B
2862>unionWithKey</B
2863> :: (<A HREF="Data-IntMap.html#t%3AKey"
2864>Key</A
2865> -&gt; a -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2866>IntMap</A
2867> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2868>IntMap</A
2869> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2870>IntMap</A
2871> a</TD
2872></TR
2873><TR
2874><TD CLASS="doc"
2875><P
2876><EM
2877>O(n+m)</EM
2878>. The union with a combining function.
2879</P
2880><PRE
2881> let f key new_value old_value = (show key) ++ &quot;:&quot; ++ new_value ++ &quot;|&quot; ++ old_value
2882 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;)]
2883</PRE
2884></TD
2885></TR
2886><TR
2887><TD CLASS="s15"
2888></TD
2889></TR
2890><TR
2891><TD CLASS="decl"
2892><A NAME="v%3Aunions"
2893></A
2894><B
2895>unions</B
2896> :: [<A HREF="Data-IntMap.html#t%3AIntMap"
2897>IntMap</A
2898> a] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2899>IntMap</A
2900> a</TD
2901></TR
2902><TR
2903><TD CLASS="doc"
2904><P
2905>The union of a list of maps.
2906</P
2907><PRE
2908> 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;)])]
2909     == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;), (7, &quot;C&quot;)]
2910 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;)])]
2911     == fromList [(3, &quot;B3&quot;), (5, &quot;A3&quot;), (7, &quot;C&quot;)]
2912</PRE
2913></TD
2914></TR
2915><TR
2916><TD CLASS="s15"
2917></TD
2918></TR
2919><TR
2920><TD CLASS="decl"
2921><A NAME="v%3AunionsWith"
2922></A
2923><B
2924>unionsWith</B
2925> :: (a -&gt; a -&gt; a) -&gt; [<A HREF="Data-IntMap.html#t%3AIntMap"
2926>IntMap</A
2927> a] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2928>IntMap</A
2929> a</TD
2930></TR
2931><TR
2932><TD CLASS="doc"
2933><P
2934>The union of a list of maps, with a combining operation.
2935</P
2936><PRE
2937> 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;)])]
2938     == fromList [(3, &quot;bB3&quot;), (5, &quot;aAA3&quot;), (7, &quot;C&quot;)]
2939</PRE
2940></TD
2941></TR
2942><TR
2943><TD CLASS="s15"
2944></TD
2945></TR
2946><TR
2947><TD CLASS="section2"
2948><A NAME="9"
2949>Difference
2950</A
2951></TD
2952></TR
2953><TR
2954><TD CLASS="s15"
2955></TD
2956></TR
2957><TR
2958><TD CLASS="decl"
2959><A NAME="v%3Adifference"
2960></A
2961><B
2962>difference</B
2963> :: <A HREF="Data-IntMap.html#t%3AIntMap"
2964>IntMap</A
2965> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2966>IntMap</A
2967> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2968>IntMap</A
2969> a</TD
2970></TR
2971><TR
2972><TD CLASS="doc"
2973><P
2974><EM
2975>O(n+m)</EM
2976>. Difference between two maps (based on keys).
2977</P
2978><PRE
2979> difference (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]) == singleton 3 &quot;b&quot;
2980</PRE
2981></TD
2982></TR
2983><TR
2984><TD CLASS="s15"
2985></TD
2986></TR
2987><TR
2988><TD CLASS="decl"
2989><A NAME="v%3AdifferenceWith"
2990></A
2991><B
2992>differenceWith</B
2993> :: (a -&gt; b -&gt; <A HREF="Prelude.html#t%3AMaybe"
2994>Maybe</A
2995> a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2996>IntMap</A
2997> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
2998>IntMap</A
2999> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3000>IntMap</A
3001> a</TD
3002></TR
3003><TR
3004><TD CLASS="doc"
3005><P
3006><EM
3007>O(n+m)</EM
3008>. Difference with a combining function.
3009</P
3010><PRE
3011> let f al ar = if al == &quot;b&quot; then Just (al ++ &quot;:&quot; ++ ar) else Nothing
3012 differenceWith f (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (3, &quot;B&quot;), (7, &quot;C&quot;)])
3013     == singleton 3 &quot;b:B&quot;
3014</PRE
3015></TD
3016></TR
3017><TR
3018><TD CLASS="s15"
3019></TD
3020></TR
3021><TR
3022><TD CLASS="decl"
3023><A NAME="v%3AdifferenceWithKey"
3024></A
3025><B
3026>differenceWithKey</B
3027> :: (<A HREF="Data-IntMap.html#t%3AKey"
3028>Key</A
3029> -&gt; a -&gt; b -&gt; <A HREF="Prelude.html#t%3AMaybe"
3030>Maybe</A
3031> a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3032>IntMap</A
3033> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3034>IntMap</A
3035> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3036>IntMap</A
3037> a</TD
3038></TR
3039><TR
3040><TD CLASS="doc"
3041><P
3042><EM
3043>O(n+m)</EM
3044>. Difference with a combining function. When two equal keys are
3045 encountered, the combining function is applied to the key and both values.
3046 If it returns <TT
3047><A HREF="Prelude.html#v%3ANothing"
3048>Nothing</A
3049></TT
3050>, the element is discarded (proper set difference).
3051 If it returns (<TT
3052><TT
3053><A HREF="Prelude.html#v%3AJust"
3054>Just</A
3055></TT
3056> y</TT
3057>), the element is updated with a new value <TT
3058>y</TT
3059>.
3060</P
3061><PRE
3062> let f k al ar = if al == &quot;b&quot; then Just ((show k) ++ &quot;:&quot; ++ al ++ &quot;|&quot; ++ ar) else Nothing
3063 differenceWithKey f (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (3, &quot;B&quot;), (10, &quot;C&quot;)])
3064     == singleton 3 &quot;3:b|B&quot;
3065</PRE
3066></TD
3067></TR
3068><TR
3069><TD CLASS="s15"
3070></TD
3071></TR
3072><TR
3073><TD CLASS="section2"
3074><A NAME="10"
3075>Intersection
3076</A
3077></TD
3078></TR
3079><TR
3080><TD CLASS="s15"
3081></TD
3082></TR
3083><TR
3084><TD CLASS="decl"
3085><A NAME="v%3Aintersection"
3086></A
3087><B
3088>intersection</B
3089> :: <A HREF="Data-IntMap.html#t%3AIntMap"
3090>IntMap</A
3091> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3092>IntMap</A
3093> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3094>IntMap</A
3095> a</TD
3096></TR
3097><TR
3098><TD CLASS="doc"
3099><P
3100><EM
3101>O(n+m)</EM
3102>. The (left-biased) intersection of two maps (based on keys).
3103</P
3104><PRE
3105> intersection (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]) == singleton 5 &quot;a&quot;
3106</PRE
3107></TD
3108></TR
3109><TR
3110><TD CLASS="s15"
3111></TD
3112></TR
3113><TR
3114><TD CLASS="decl"
3115><A NAME="v%3AintersectionWith"
3116></A
3117><B
3118>intersectionWith</B
3119> :: (a -&gt; b -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3120>IntMap</A
3121> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3122>IntMap</A
3123> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3124>IntMap</A
3125> a</TD
3126></TR
3127><TR
3128><TD CLASS="doc"
3129><P
3130><EM
3131>O(n+m)</EM
3132>. The intersection with a combining function.
3133</P
3134><PRE
3135> intersectionWith (++) (fromList [(5, &quot;a&quot;), (3, &quot;b&quot;)]) (fromList [(5, &quot;A&quot;), (7, &quot;C&quot;)]) == singleton 5 &quot;aA&quot;
3136</PRE
3137></TD
3138></TR
3139><TR
3140><TD CLASS="s15"
3141></TD
3142></TR
3143><TR
3144><TD CLASS="decl"
3145><A NAME="v%3AintersectionWithKey"
3146></A
3147><B
3148>intersectionWithKey</B
3149> :: (<A HREF="Data-IntMap.html#t%3AKey"
3150>Key</A
3151> -&gt; a -&gt; b -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3152>IntMap</A
3153> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3154>IntMap</A
3155> b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3156>IntMap</A
3157> a</TD
3158></TR
3159><TR
3160><TD CLASS="doc"
3161><P
3162><EM
3163>O(n+m)</EM
3164>. The intersection with a combining function.
3165</P
3166><PRE
3167> let f k al ar = (show k) ++ &quot;:&quot; ++ al ++ &quot;|&quot; ++ ar
3168 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;
3169</PRE
3170></TD
3171></TR
3172><TR
3173><TD CLASS="s15"
3174></TD
3175></TR
3176><TR
3177><TD CLASS="section1"
3178><A NAME="11"
3179>Traversal
3180</A
3181></TD
3182></TR
3183><TR
3184><TD CLASS="s15"
3185></TD
3186></TR
3187><TR
3188><TD CLASS="section2"
3189><A NAME="12"
3190>Map
3191</A
3192></TD
3193></TR
3194><TR
3195><TD CLASS="s15"
3196></TD
3197></TR
3198><TR
3199><TD CLASS="decl"
3200><A NAME="v%3Amap"
3201></A
3202><B
3203>map</B
3204> :: (a -&gt; b) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3205>IntMap</A
3206> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3207>IntMap</A
3208> b</TD
3209></TR
3210><TR
3211><TD CLASS="doc"
3212><P
3213><EM
3214>O(n)</EM
3215>. Map a function over all values in the map.
3216</P
3217><PRE
3218> map (++ &quot;x&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;bx&quot;), (5, &quot;ax&quot;)]
3219</PRE
3220></TD
3221></TR
3222><TR
3223><TD CLASS="s15"
3224></TD
3225></TR
3226><TR
3227><TD CLASS="decl"
3228><A NAME="v%3AmapWithKey"
3229></A
3230><B
3231>mapWithKey</B
3232> :: (<A HREF="Data-IntMap.html#t%3AKey"
3233>Key</A
3234> -&gt; a -&gt; b) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3235>IntMap</A
3236> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3237>IntMap</A
3238> b</TD
3239></TR
3240><TR
3241><TD CLASS="doc"
3242><P
3243><EM
3244>O(n)</EM
3245>. Map a function over all values in the map.
3246</P
3247><PRE
3248> let f key x = (show key) ++ &quot;:&quot; ++ x
3249 mapWithKey f (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == fromList [(3, &quot;3:b&quot;), (5, &quot;5:a&quot;)]
3250</PRE
3251></TD
3252></TR
3253><TR
3254><TD CLASS="s15"
3255></TD
3256></TR
3257><TR
3258><TD CLASS="decl"
3259><A NAME="v%3AmapAccum"
3260></A
3261><B
3262>mapAccum</B
3263> :: (a -&gt; b -&gt; (a, c)) -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3264>IntMap</A
3265> b -&gt; (a, <A HREF="Data-IntMap.html#t%3AIntMap"
3266>IntMap</A
3267> c)</TD
3268></TR
3269><TR
3270><TD CLASS="doc"
3271><P
3272><EM
3273>O(n)</EM
3274>. The function <TT
3275><TT
3276><A HREF="Data-IntMap.html#v%3AmapAccum"
3277>mapAccum</A
3278></TT
3279></TT
3280> threads an accumulating
3281 argument through the map in ascending order of keys.
3282</P
3283><PRE
3284> let f a b = (a ++ b, b ++ &quot;X&quot;)
3285 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;)])
3286</PRE
3287></TD
3288></TR
3289><TR
3290><TD CLASS="s15"
3291></TD
3292></TR
3293><TR
3294><TD CLASS="decl"
3295><A NAME="v%3AmapAccumWithKey"
3296></A
3297><B
3298>mapAccumWithKey</B
3299> :: (a -&gt; <A HREF="Data-IntMap.html#t%3AKey"
3300>Key</A
3301> -&gt; b -&gt; (a, c)) -&gt; a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3302>IntMap</A
3303> b -&gt; (a, <A HREF="Data-IntMap.html#t%3AIntMap"
3304>IntMap</A
3305> c)</TD
3306></TR
3307><TR
3308><TD CLASS="doc"
3309><P
3310><EM
3311>O(n)</EM
3312>. The function <TT
3313><TT
3314><A HREF="Data-IntMap.html#v%3AmapAccumWithKey"
3315>mapAccumWithKey</A
3316></TT
3317></TT
3318> threads an accumulating
3319 argument through the map in ascending order of keys.
3320</P
3321><PRE
3322> let f a k b = (a ++ &quot; &quot; ++ (show k) ++ &quot;-&quot; ++ b, b ++ &quot;X&quot;)
3323 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;)])
3324</PRE
3325></TD
3326></TR
3327><TR
3328><TD CLASS="s15"
3329></TD
3330></TR
3331><TR
3332><TD CLASS="section2"
3333><A NAME="13"
3334>Fold
3335</A
3336></TD
3337></TR
3338><TR
3339><TD CLASS="s15"
3340></TD
3341></TR
3342><TR
3343><TD CLASS="decl"
3344><A NAME="v%3Afold"
3345></A
3346><B
3347>fold</B
3348> :: (a -&gt; b -&gt; b) -&gt; b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3349>IntMap</A
3350> a -&gt; b</TD
3351></TR
3352><TR
3353><TD CLASS="doc"
3354><P
3355><EM
3356>O(n)</EM
3357>. Fold the values in the map, such that
3358 <TT
3359><TT
3360><A HREF="Data-IntMap.html#v%3Afold"
3361>fold</A
3362></TT
3363> f z == <TT
3364><A HREF="Prelude.html#v%3Afoldr"
3365>foldr</A
3366></TT
3367> f z . <TT
3368><A HREF="Data-IntMap.html#v%3Aelems"
3369>elems</A
3370></TT
3371></TT
3372>.
3373 For example,
3374</P
3375><PRE
3376> elems map = fold (:) [] map
3377</PRE
3378><PRE
3379> let f a len = len + (length a)
3380 fold f 0 (fromList [(5,&quot;a&quot;), (3,&quot;bbb&quot;)]) == 4
3381</PRE
3382></TD
3383></TR
3384><TR
3385><TD CLASS="s15"
3386></TD
3387></TR
3388><TR
3389><TD CLASS="decl"
3390><A NAME="v%3AfoldWithKey"
3391></A
3392><B
3393>foldWithKey</B
3394> :: (<A HREF="Data-IntMap.html#t%3AKey"
3395>Key</A
3396> -&gt; a -&gt; b -&gt; b) -&gt; b -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3397>IntMap</A
3398> a -&gt; b</TD
3399></TR
3400><TR
3401><TD CLASS="doc"
3402><P
3403><EM
3404>O(n)</EM
3405>. Fold the keys and values in the map, such that
3406 <TT
3407><TT
3408><A HREF="Data-IntMap.html#v%3AfoldWithKey"
3409>foldWithKey</A
3410></TT
3411> f z == <TT
3412><A HREF="Prelude.html#v%3Afoldr"
3413>foldr</A
3414></TT
3415> (<TT
3416><A HREF="Prelude.html#v%3Auncurry"
3417>uncurry</A
3418></TT
3419> f) z . <TT
3420><A HREF="Data-IntMap.html#v%3AtoAscList"
3421>toAscList</A
3422></TT
3423></TT
3424>.
3425 For example,
3426</P
3427><PRE
3428> keys map = foldWithKey (\k x ks -&gt; k:ks) [] map
3429</PRE
3430><PRE
3431> let f k a result = result ++ &quot;(&quot; ++ (show k) ++ &quot;:&quot; ++ a ++ &quot;)&quot;
3432 foldWithKey f &quot;Map: &quot; (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == &quot;Map: (5:a)(3:b)&quot;
3433</PRE
3434></TD
3435></TR
3436><TR
3437><TD CLASS="s15"
3438></TD
3439></TR
3440><TR
3441><TD CLASS="section1"
3442><A NAME="14"
3443>Conversion
3444</A
3445></TD
3446></TR
3447><TR
3448><TD CLASS="s15"
3449></TD
3450></TR
3451><TR
3452><TD CLASS="decl"
3453><A NAME="v%3Aelems"
3454></A
3455><B
3456>elems</B
3457> :: <A HREF="Data-IntMap.html#t%3AIntMap"
3458>IntMap</A
3459> a -&gt; [a]</TD
3460></TR
3461><TR
3462><TD CLASS="doc"
3463><P
3464><EM
3465>O(n)</EM
3466>.
3467 Return all elements of the map in the ascending order of their keys.
3468</P
3469><PRE
3470> elems (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == [&quot;b&quot;,&quot;a&quot;]
3471 elems empty == []
3472</PRE
3473></TD
3474></TR
3475><TR
3476><TD CLASS="s15"
3477></TD
3478></TR
3479><TR
3480><TD CLASS="decl"
3481><A NAME="v%3Akeys"
3482></A
3483><B
3484>keys</B
3485> :: <A HREF="Data-IntMap.html#t%3AIntMap"
3486>IntMap</A
3487> a -&gt; [<A HREF="Data-IntMap.html#t%3AKey"
3488>Key</A
3489>]</TD
3490></TR
3491><TR
3492><TD CLASS="doc"
3493><P
3494><EM
3495>O(n)</EM
3496>. Return all keys of the map in ascending order.
3497</P
3498><PRE
3499> keys (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == [3,5]
3500 keys empty == []
3501</PRE
3502></TD
3503></TR
3504><TR
3505><TD CLASS="s15"
3506></TD
3507></TR
3508><TR
3509><TD CLASS="decl"
3510><A NAME="v%3AkeysSet"
3511></A
3512><B
3513>keysSet</B
3514> :: <A HREF="Data-IntMap.html#t%3AIntMap"
3515>IntMap</A
3516> a -&gt; IntSet</TD
3517></TR
3518><TR
3519><TD CLASS="doc"
3520><P
3521><EM
3522>O(n*min(n,W))</EM
3523>. The set of all keys of the map.
3524</P
3525><PRE
3526> keysSet (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == Data.IntSet.fromList [3,5]
3527 keysSet empty == Data.IntSet.empty
3528</PRE
3529></TD
3530></TR
3531><TR
3532><TD CLASS="s15"
3533></TD
3534></TR
3535><TR
3536><TD CLASS="decl"
3537><A NAME="v%3Aassocs"
3538></A
3539><B
3540>assocs</B
3541> :: <A HREF="Data-IntMap.html#t%3AIntMap"
3542>IntMap</A
3543> a -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
3544>Key</A
3545>, a)]</TD
3546></TR
3547><TR
3548><TD CLASS="doc"
3549><P
3550><EM
3551>O(n)</EM
3552>. Return all key/value pairs in the map in ascending key order.
3553</P
3554><PRE
3555> assocs (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == [(3,&quot;b&quot;), (5,&quot;a&quot;)]
3556 assocs empty == []
3557</PRE
3558></TD
3559></TR
3560><TR
3561><TD CLASS="s15"
3562></TD
3563></TR
3564><TR
3565><TD CLASS="section2"
3566><A NAME="15"
3567>Lists
3568</A
3569></TD
3570></TR
3571><TR
3572><TD CLASS="s15"
3573></TD
3574></TR
3575><TR
3576><TD CLASS="decl"
3577><A NAME="v%3AtoList"
3578></A
3579><B
3580>toList</B
3581> :: <A HREF="Data-IntMap.html#t%3AIntMap"
3582>IntMap</A
3583> a -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
3584>Key</A
3585>, a)]</TD
3586></TR
3587><TR
3588><TD CLASS="doc"
3589><P
3590><EM
3591>O(n)</EM
3592>. Convert the map to a list of key/value pairs.
3593</P
3594><PRE
3595> toList (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == [(3,&quot;b&quot;), (5,&quot;a&quot;)]
3596 toList empty == []
3597</PRE
3598></TD
3599></TR
3600><TR
3601><TD CLASS="s15"
3602></TD
3603></TR
3604><TR
3605><TD CLASS="decl"
3606><A NAME="v%3AfromList"
3607></A
3608><B
3609>fromList</B
3610> :: [(<A HREF="Data-IntMap.html#t%3AKey"
3611>Key</A
3612>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3613>IntMap</A
3614> a</TD
3615></TR
3616><TR
3617><TD CLASS="doc"
3618><P
3619><EM
3620>O(n*min(n,W))</EM
3621>. Create a map from a list of key/value pairs.
3622</P
3623><PRE
3624> fromList [] == empty
3625 fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (5, &quot;c&quot;)] == fromList [(5,&quot;c&quot;), (3,&quot;b&quot;)]
3626 fromList [(5,&quot;c&quot;), (3,&quot;b&quot;), (5, &quot;a&quot;)] == fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]
3627</PRE
3628></TD
3629></TR
3630><TR
3631><TD CLASS="s15"
3632></TD
3633></TR
3634><TR
3635><TD CLASS="decl"
3636><A NAME="v%3AfromListWith"
3637></A
3638><B
3639>fromListWith</B
3640> :: (a -&gt; a -&gt; a) -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
3641>Key</A
3642>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3643>IntMap</A
3644> a</TD
3645></TR
3646><TR
3647><TD CLASS="doc"
3648><P
3649><EM
3650>O(n*min(n,W))</EM
3651>. Create a map from a list of key/value pairs with a combining function. See also <TT
3652><A HREF="Data-IntMap.html#v%3AfromAscListWith"
3653>fromAscListWith</A
3654></TT
3655>.
3656</P
3657><PRE
3658> 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;)]
3659 fromListWith (++) [] == empty
3660</PRE
3661></TD
3662></TR
3663><TR
3664><TD CLASS="s15"
3665></TD
3666></TR
3667><TR
3668><TD CLASS="decl"
3669><A NAME="v%3AfromListWithKey"
3670></A
3671><B
3672>fromListWithKey</B
3673> :: (<A HREF="Data-IntMap.html#t%3AKey"
3674>Key</A
3675> -&gt; a -&gt; a -&gt; a) -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
3676>Key</A
3677>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3678>IntMap</A
3679> a</TD
3680></TR
3681><TR
3682><TD CLASS="doc"
3683><P
3684><EM
3685>O(n*min(n,W))</EM
3686>. Build a map from a list of key/value pairs with a combining function. See also fromAscListWithKey'.
3687</P
3688><PRE
3689> 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;)]
3690 fromListWith (++) [] == empty
3691</PRE
3692></TD
3693></TR
3694><TR
3695><TD CLASS="s15"
3696></TD
3697></TR
3698><TR
3699><TD CLASS="section2"
3700><A NAME="16"
3701>Ordered lists
3702</A
3703></TD
3704></TR
3705><TR
3706><TD CLASS="s15"
3707></TD
3708></TR
3709><TR
3710><TD CLASS="decl"
3711><A NAME="v%3AtoAscList"
3712></A
3713><B
3714>toAscList</B
3715> :: <A HREF="Data-IntMap.html#t%3AIntMap"
3716>IntMap</A
3717> a -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
3718>Key</A
3719>, a)]</TD
3720></TR
3721><TR
3722><TD CLASS="doc"
3723><P
3724><EM
3725>O(n)</EM
3726>. Convert the map to a list of key/value pairs where the
3727 keys are in ascending order.
3728</P
3729><PRE
3730> toAscList (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == [(3,&quot;b&quot;), (5,&quot;a&quot;)]
3731</PRE
3732></TD
3733></TR
3734><TR
3735><TD CLASS="s15"
3736></TD
3737></TR
3738><TR
3739><TD CLASS="decl"
3740><A NAME="v%3AfromAscList"
3741></A
3742><B
3743>fromAscList</B
3744> :: [(<A HREF="Data-IntMap.html#t%3AKey"
3745>Key</A
3746>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3747>IntMap</A
3748> a</TD
3749></TR
3750><TR
3751><TD CLASS="doc"
3752><P
3753><EM
3754>O(n*min(n,W))</EM
3755>. Build a map from a list of key/value pairs where
3756 the keys are in ascending order.
3757</P
3758><PRE
3759> fromAscList [(3,&quot;b&quot;), (5,&quot;a&quot;)]          == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
3760 fromAscList [(3,&quot;b&quot;), (5,&quot;a&quot;), (5,&quot;b&quot;)] == fromList [(3, &quot;b&quot;), (5, &quot;b&quot;)]
3761</PRE
3762></TD
3763></TR
3764><TR
3765><TD CLASS="s15"
3766></TD
3767></TR
3768><TR
3769><TD CLASS="decl"
3770><A NAME="v%3AfromAscListWith"
3771></A
3772><B
3773>fromAscListWith</B
3774> :: (a -&gt; a -&gt; a) -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
3775>Key</A
3776>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3777>IntMap</A
3778> a</TD
3779></TR
3780><TR
3781><TD CLASS="doc"
3782><P
3783><EM
3784>O(n*min(n,W))</EM
3785>. Build a map from a list of key/value pairs where
3786 the keys are in ascending order, with a combining function on equal keys.
3787</P
3788><PRE
3789> fromAscListWith (++) [(3,&quot;b&quot;), (5,&quot;a&quot;), (5,&quot;b&quot;)] == fromList [(3, &quot;b&quot;), (5, &quot;ba&quot;)]
3790</PRE
3791></TD
3792></TR
3793><TR
3794><TD CLASS="s15"
3795></TD
3796></TR
3797><TR
3798><TD CLASS="decl"
3799><A NAME="v%3AfromAscListWithKey"
3800></A
3801><B
3802>fromAscListWithKey</B
3803> :: (<A HREF="Data-IntMap.html#t%3AKey"
3804>Key</A
3805> -&gt; a -&gt; a -&gt; a) -&gt; [(<A HREF="Data-IntMap.html#t%3AKey"
3806>Key</A
3807>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3808>IntMap</A
3809> a</TD
3810></TR
3811><TR
3812><TD CLASS="doc"
3813><P
3814><EM
3815>O(n*min(n,W))</EM
3816>. Build a map from a list of key/value pairs where
3817 the keys are in ascending order, with a combining function on equal keys.
3818</P
3819><PRE
3820> fromAscListWith (++) [(3,&quot;b&quot;), (5,&quot;a&quot;), (5,&quot;b&quot;)] == fromList [(3, &quot;b&quot;), (5, &quot;ba&quot;)]
3821</PRE
3822></TD
3823></TR
3824><TR
3825><TD CLASS="s15"
3826></TD
3827></TR
3828><TR
3829><TD CLASS="decl"
3830><A NAME="v%3AfromDistinctAscList"
3831></A
3832><B
3833>fromDistinctAscList</B
3834> :: [(<A HREF="Data-IntMap.html#t%3AKey"
3835>Key</A
3836>, a)] -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3837>IntMap</A
3838> a</TD
3839></TR
3840><TR
3841><TD CLASS="doc"
3842><P
3843><EM
3844>O(n*min(n,W))</EM
3845>. Build a map from a list of key/value pairs where
3846 the keys are in ascending order and all distinct.
3847</P
3848><PRE
3849> fromDistinctAscList [(3,&quot;b&quot;), (5,&quot;a&quot;)] == fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)]
3850</PRE
3851></TD
3852></TR
3853><TR
3854><TD CLASS="s15"
3855></TD
3856></TR
3857><TR
3858><TD CLASS="section1"
3859><A NAME="17"
3860>Filter
3861</A
3862></TD
3863></TR
3864><TR
3865><TD CLASS="s15"
3866></TD
3867></TR
3868><TR
3869><TD CLASS="decl"
3870><A NAME="v%3Afilter"
3871></A
3872><B
3873>filter</B
3874> :: (a -&gt; <A HREF="Prelude.html#t%3ABool"
3875>Bool</A
3876>) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3877>IntMap</A
3878> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3879>IntMap</A
3880> a</TD
3881></TR
3882><TR
3883><TD CLASS="doc"
3884><P
3885><EM
3886>O(n)</EM
3887>. Filter all values that satisfy some predicate.
3888</P
3889><PRE
3890> filter (&gt; &quot;a&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;b&quot;
3891 filter (&gt; &quot;x&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == empty
3892 filter (&lt; &quot;a&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == empty
3893</PRE
3894></TD
3895></TR
3896><TR
3897><TD CLASS="s15"
3898></TD
3899></TR
3900><TR
3901><TD CLASS="decl"
3902><A NAME="v%3AfilterWithKey"
3903></A
3904><B
3905>filterWithKey</B
3906> :: (<A HREF="Data-IntMap.html#t%3AKey"
3907>Key</A
3908> -&gt; a -&gt; <A HREF="Prelude.html#t%3ABool"
3909>Bool</A
3910>) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3911>IntMap</A
3912> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3913>IntMap</A
3914> a</TD
3915></TR
3916><TR
3917><TD CLASS="doc"
3918><P
3919><EM
3920>O(n)</EM
3921>. Filter all keys/values that satisfy some predicate.
3922</P
3923><PRE
3924> filterWithKey (\k _ -&gt; k &gt; 4) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;a&quot;
3925</PRE
3926></TD
3927></TR
3928><TR
3929><TD CLASS="s15"
3930></TD
3931></TR
3932><TR
3933><TD CLASS="decl"
3934><A NAME="v%3Apartition"
3935></A
3936><B
3937>partition</B
3938> :: (a -&gt; <A HREF="Prelude.html#t%3ABool"
3939>Bool</A
3940>) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3941>IntMap</A
3942> a -&gt; (<A HREF="Data-IntMap.html#t%3AIntMap"
3943>IntMap</A
3944> a, <A HREF="Data-IntMap.html#t%3AIntMap"
3945>IntMap</A
3946> a)</TD
3947></TR
3948><TR
3949><TD CLASS="doc"
3950><P
3951><EM
3952>O(n)</EM
3953>. Partition the map according to some predicate. The first
3954 map contains all elements that satisfy the predicate, the second all
3955 elements that fail the predicate. See also <TT
3956><A HREF="Data-IntMap.html#v%3Asplit"
3957>split</A
3958></TT
3959>.
3960</P
3961><PRE
3962> partition (&gt; &quot;a&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (singleton 3 &quot;b&quot;, singleton 5 &quot;a&quot;)
3963 partition (&lt; &quot;x&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)], empty)
3964 partition (&gt; &quot;x&quot;) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (empty, fromList [(3, &quot;b&quot;), (5, &quot;a&quot;)])
3965</PRE
3966></TD
3967></TR
3968><TR
3969><TD CLASS="s15"
3970></TD
3971></TR
3972><TR
3973><TD CLASS="decl"
3974><A NAME="v%3ApartitionWithKey"
3975></A
3976><B
3977>partitionWithKey</B
3978> :: (<A HREF="Data-IntMap.html#t%3AKey"
3979>Key</A
3980> -&gt; a -&gt; <A HREF="Prelude.html#t%3ABool"
3981>Bool</A
3982>) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
3983>IntMap</A
3984> a -&gt; (<A HREF="Data-IntMap.html#t%3AIntMap"
3985>IntMap</A
3986> a, <A HREF="Data-IntMap.html#t%3AIntMap"
3987>IntMap</A
3988> a)</TD
3989></TR
3990><TR
3991><TD CLASS="doc"
3992><P
3993><EM
3994>O(n)</EM
3995>. Partition the map according to some predicate. The first
3996 map contains all elements that satisfy the predicate, the second all
3997 elements that fail the predicate. See also <TT
3998><A HREF="Data-IntMap.html#v%3Asplit"
3999>split</A
4000></TT
4001>.
4002</P
4003><PRE
4004> 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;)
4005 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)
4006 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;)])
4007</PRE
4008></TD
4009></TR
4010><TR
4011><TD CLASS="s15"
4012></TD
4013></TR
4014><TR
4015><TD CLASS="decl"
4016><A NAME="v%3AmapMaybe"
4017></A
4018><B
4019>mapMaybe</B
4020> :: (a -&gt; <A HREF="Prelude.html#t%3AMaybe"
4021>Maybe</A
4022> b) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4023>IntMap</A
4024> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4025>IntMap</A
4026> b</TD
4027></TR
4028><TR
4029><TD CLASS="doc"
4030><P
4031><EM
4032>O(n)</EM
4033>. Map values and collect the <TT
4034><A HREF="Prelude.html#v%3AJust"
4035>Just</A
4036></TT
4037> results.
4038</P
4039><PRE
4040> let f x = if x == &quot;a&quot; then Just &quot;new a&quot; else Nothing
4041 mapMaybe f (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;new a&quot;
4042</PRE
4043></TD
4044></TR
4045><TR
4046><TD CLASS="s15"
4047></TD
4048></TR
4049><TR
4050><TD CLASS="decl"
4051><A NAME="v%3AmapMaybeWithKey"
4052></A
4053><B
4054>mapMaybeWithKey</B
4055> :: (<A HREF="Data-IntMap.html#t%3AKey"
4056>Key</A
4057> -&gt; a -&gt; <A HREF="Prelude.html#t%3AMaybe"
4058>Maybe</A
4059> b) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4060>IntMap</A
4061> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4062>IntMap</A
4063> b</TD
4064></TR
4065><TR
4066><TD CLASS="doc"
4067><P
4068><EM
4069>O(n)</EM
4070>. Map keys/values and collect the <TT
4071><A HREF="Prelude.html#v%3AJust"
4072>Just</A
4073></TT
4074> results.
4075</P
4076><PRE
4077> let f k _ = if k &lt; 5 then Just (&quot;key : &quot; ++ (show k)) else Nothing
4078 mapMaybeWithKey f (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;key : 3&quot;
4079</PRE
4080></TD
4081></TR
4082><TR
4083><TD CLASS="s15"
4084></TD
4085></TR
4086><TR
4087><TD CLASS="decl"
4088><A NAME="v%3AmapEither"
4089></A
4090><B
4091>mapEither</B
4092> :: (a -&gt; <A HREF="Prelude.html#t%3AEither"
4093>Either</A
4094> b c) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4095>IntMap</A
4096> a -&gt; (<A HREF="Data-IntMap.html#t%3AIntMap"
4097>IntMap</A
4098> b, <A HREF="Data-IntMap.html#t%3AIntMap"
4099>IntMap</A
4100> c)</TD
4101></TR
4102><TR
4103><TD CLASS="doc"
4104><P
4105><EM
4106>O(n)</EM
4107>. Map values and separate the <TT
4108><A HREF="Prelude.html#v%3ALeft"
4109>Left</A
4110></TT
4111> and <TT
4112><A HREF="Prelude.html#v%3ARight"
4113>Right</A
4114></TT
4115> results.
4116</P
4117><PRE
4118> let f a = if a &lt; &quot;c&quot; then Left a else Right a
4119 mapEither f (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (1,&quot;x&quot;), (7,&quot;z&quot;)])
4120     == (fromList [(3,&quot;b&quot;), (5,&quot;a&quot;)], fromList [(1,&quot;x&quot;), (7,&quot;z&quot;)])
4121
4122 mapEither (\ a -&gt; Right a) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (1,&quot;x&quot;), (7,&quot;z&quot;)])
4123     == (empty, fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (1,&quot;x&quot;), (7,&quot;z&quot;)])
4124</PRE
4125></TD
4126></TR
4127><TR
4128><TD CLASS="s15"
4129></TD
4130></TR
4131><TR
4132><TD CLASS="decl"
4133><A NAME="v%3AmapEitherWithKey"
4134></A
4135><B
4136>mapEitherWithKey</B
4137> :: (<A HREF="Data-IntMap.html#t%3AKey"
4138>Key</A
4139> -&gt; a -&gt; <A HREF="Prelude.html#t%3AEither"
4140>Either</A
4141> b c) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4142>IntMap</A
4143> a -&gt; (<A HREF="Data-IntMap.html#t%3AIntMap"
4144>IntMap</A
4145> b, <A HREF="Data-IntMap.html#t%3AIntMap"
4146>IntMap</A
4147> c)</TD
4148></TR
4149><TR
4150><TD CLASS="doc"
4151><P
4152><EM
4153>O(n)</EM
4154>. Map keys/values and separate the <TT
4155><A HREF="Prelude.html#v%3ALeft"
4156>Left</A
4157></TT
4158> and <TT
4159><A HREF="Prelude.html#v%3ARight"
4160>Right</A
4161></TT
4162> results.
4163</P
4164><PRE
4165> let f k a = if k &lt; 5 then Left (k * 2) else Right (a ++ a)
4166 mapEitherWithKey f (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (1,&quot;x&quot;), (7,&quot;z&quot;)])
4167     == (fromList [(1,2), (3,6)], fromList [(5,&quot;aa&quot;), (7,&quot;zz&quot;)])
4168
4169 mapEitherWithKey (\_ a -&gt; Right a) (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;), (1,&quot;x&quot;), (7,&quot;z&quot;)])
4170     == (empty, fromList [(1,&quot;x&quot;), (3,&quot;b&quot;), (5,&quot;a&quot;), (7,&quot;z&quot;)])
4171</PRE
4172></TD
4173></TR
4174><TR
4175><TD CLASS="s15"
4176></TD
4177></TR
4178><TR
4179><TD CLASS="decl"
4180><A NAME="v%3Asplit"
4181></A
4182><B
4183>split</B
4184> :: <A HREF="Data-IntMap.html#t%3AKey"
4185>Key</A
4186> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4187>IntMap</A
4188> a -&gt; (<A HREF="Data-IntMap.html#t%3AIntMap"
4189>IntMap</A
4190> a, <A HREF="Data-IntMap.html#t%3AIntMap"
4191>IntMap</A
4192> a)</TD
4193></TR
4194><TR
4195><TD CLASS="doc"
4196><P
4197><EM
4198>O(log n)</EM
4199>. The expression (<TT
4200><TT
4201><A HREF="Data-IntMap.html#v%3Asplit"
4202>split</A
4203></TT
4204> k map</TT
4205>) is a pair <TT
4206>(map1,map2)</TT
4207>
4208 where all keys in <TT
4209>map1</TT
4210> are lower than <TT
4211>k</TT
4212> and all keys in
4213 <TT
4214>map2</TT
4215> larger than <TT
4216>k</TT
4217>. Any key equal to <TT
4218>k</TT
4219> is found in neither <TT
4220>map1</TT
4221> nor <TT
4222>map2</TT
4223>.
4224</P
4225><PRE
4226> split 2 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (empty, fromList [(3,&quot;b&quot;), (5,&quot;a&quot;)])
4227 split 3 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (empty, singleton 5 &quot;a&quot;)
4228 split 4 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (singleton 3 &quot;b&quot;, singleton 5 &quot;a&quot;)
4229 split 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (singleton 3 &quot;b&quot;, empty)
4230 split 6 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (fromList [(3,&quot;b&quot;), (5,&quot;a&quot;)], empty)
4231</PRE
4232></TD
4233></TR
4234><TR
4235><TD CLASS="s15"
4236></TD
4237></TR
4238><TR
4239><TD CLASS="decl"
4240><A NAME="v%3AsplitLookup"
4241></A
4242><B
4243>splitLookup</B
4244> :: <A HREF="Data-IntMap.html#t%3AKey"
4245>Key</A
4246> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4247>IntMap</A
4248> a -&gt; (<A HREF="Data-IntMap.html#t%3AIntMap"
4249>IntMap</A
4250> a, <A HREF="Prelude.html#t%3AMaybe"
4251>Maybe</A
4252> a, <A HREF="Data-IntMap.html#t%3AIntMap"
4253>IntMap</A
4254> a)</TD
4255></TR
4256><TR
4257><TD CLASS="doc"
4258><P
4259><EM
4260>O(log n)</EM
4261>. Performs a <TT
4262><A HREF="Data-IntMap.html#v%3Asplit"
4263>split</A
4264></TT
4265> but also returns whether the pivot
4266 key was found in the original map.
4267</P
4268><PRE
4269> splitLookup 2 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (empty, Nothing, fromList [(3,&quot;b&quot;), (5,&quot;a&quot;)])
4270 splitLookup 3 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (empty, Just &quot;b&quot;, singleton 5 &quot;a&quot;)
4271 splitLookup 4 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (singleton 3 &quot;b&quot;, Nothing, singleton 5 &quot;a&quot;)
4272 splitLookup 5 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (singleton 3 &quot;b&quot;, Just &quot;a&quot;, empty)
4273 splitLookup 6 (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == (fromList [(3,&quot;b&quot;), (5,&quot;a&quot;)], Nothing, empty)
4274</PRE
4275></TD
4276></TR
4277><TR
4278><TD CLASS="s15"
4279></TD
4280></TR
4281><TR
4282><TD CLASS="section1"
4283><A NAME="18"
4284>Submap
4285</A
4286></TD
4287></TR
4288><TR
4289><TD CLASS="s15"
4290></TD
4291></TR
4292><TR
4293><TD CLASS="decl"
4294><A NAME="v%3AisSubmapOf"
4295></A
4296><B
4297>isSubmapOf</B
4298> :: <A HREF="Prelude.html#t%3AEq"
4299>Eq</A
4300> a =&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4301>IntMap</A
4302> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4303>IntMap</A
4304> a -&gt; <A HREF="Prelude.html#t%3ABool"
4305>Bool</A
4306></TD
4307></TR
4308><TR
4309><TD CLASS="doc"
4310><EM
4311>O(n+m)</EM
4312>. Is this a submap?
4313 Defined as (<TT
4314><TT
4315><A HREF="Data-IntMap.html#v%3AisSubmapOf"
4316>isSubmapOf</A
4317></TT
4318> = <TT
4319><A HREF="Data-IntMap.html#v%3AisSubmapOfBy"
4320>isSubmapOfBy</A
4321></TT
4322> (==)</TT
4323>).
4324</TD
4325></TR
4326><TR
4327><TD CLASS="s15"
4328></TD
4329></TR
4330><TR
4331><TD CLASS="decl"
4332><A NAME="v%3AisSubmapOfBy"
4333></A
4334><B
4335>isSubmapOfBy</B
4336> :: (a -&gt; b -&gt; <A HREF="Prelude.html#t%3ABool"
4337>Bool</A
4338>) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4339>IntMap</A
4340> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4341>IntMap</A
4342> b -&gt; <A HREF="Prelude.html#t%3ABool"
4343>Bool</A
4344></TD
4345></TR
4346><TR
4347><TD CLASS="doc"
4348><P
4349><EM
4350>O(n+m)</EM
4351>.
4352 The expression (<TT
4353><TT
4354><A HREF="Data-IntMap.html#v%3AisSubmapOfBy"
4355>isSubmapOfBy</A
4356></TT
4357> f m1 m2</TT
4358>) returns <TT
4359><A HREF="Prelude.html#v%3ATrue"
4360>True</A
4361></TT
4362> if
4363 all keys in <TT
4364>m1</TT
4365> are in <TT
4366>m2</TT
4367>, and when <TT
4368>f</TT
4369> returns <TT
4370><A HREF="Prelude.html#v%3ATrue"
4371>True</A
4372></TT
4373> when
4374 applied to their respective values. For example, the following
4375 expressions are all <TT
4376><A HREF="Prelude.html#v%3ATrue"
4377>True</A
4378></TT
4379>:
4380</P
4381><PRE
4382> isSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
4383 isSubmapOfBy (&lt;=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
4384 isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
4385</PRE
4386><P
4387>But the following are all <TT
4388><A HREF="Prelude.html#v%3AFalse"
4389>False</A
4390></TT
4391>:
4392</P
4393><PRE
4394> isSubmapOfBy (==) (fromList [(1,2)]) (fromList [(1,1),(2,2)])
4395 isSubmapOfBy (&lt;) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
4396 isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
4397</PRE
4398></TD
4399></TR
4400><TR
4401><TD CLASS="s15"
4402></TD
4403></TR
4404><TR
4405><TD CLASS="decl"
4406><A NAME="v%3AisProperSubmapOf"
4407></A
4408><B
4409>isProperSubmapOf</B
4410> :: <A HREF="Prelude.html#t%3AEq"
4411>Eq</A
4412> a =&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4413>IntMap</A
4414> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4415>IntMap</A
4416> a -&gt; <A HREF="Prelude.html#t%3ABool"
4417>Bool</A
4418></TD
4419></TR
4420><TR
4421><TD CLASS="doc"
4422><EM
4423>O(n+m)</EM
4424>. Is this a proper submap? (ie. a submap but not equal).
4425 Defined as (<TT
4426><TT
4427><A HREF="Data-IntMap.html#v%3AisProperSubmapOf"
4428>isProperSubmapOf</A
4429></TT
4430> = <TT
4431><A HREF="Data-IntMap.html#v%3AisProperSubmapOfBy"
4432>isProperSubmapOfBy</A
4433></TT
4434> (==)</TT
4435>).
4436</TD
4437></TR
4438><TR
4439><TD CLASS="s15"
4440></TD
4441></TR
4442><TR
4443><TD CLASS="decl"
4444><A NAME="v%3AisProperSubmapOfBy"
4445></A
4446><B
4447>isProperSubmapOfBy</B
4448> :: (a -&gt; b -&gt; <A HREF="Prelude.html#t%3ABool"
4449>Bool</A
4450>) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4451>IntMap</A
4452> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4453>IntMap</A
4454> b -&gt; <A HREF="Prelude.html#t%3ABool"
4455>Bool</A
4456></TD
4457></TR
4458><TR
4459><TD CLASS="doc"
4460><P
4461><EM
4462>O(n+m)</EM
4463>. Is this a proper submap? (ie. a submap but not equal).
4464 The expression (<TT
4465><TT
4466><A HREF="Data-IntMap.html#v%3AisProperSubmapOfBy"
4467>isProperSubmapOfBy</A
4468></TT
4469> f m1 m2</TT
4470>) returns <TT
4471><A HREF="Prelude.html#v%3ATrue"
4472>True</A
4473></TT
4474> when
4475 <TT
4476>m1</TT
4477> and <TT
4478>m2</TT
4479> are not equal,
4480 all keys in <TT
4481>m1</TT
4482> are in <TT
4483>m2</TT
4484>, and when <TT
4485>f</TT
4486> returns <TT
4487><A HREF="Prelude.html#v%3ATrue"
4488>True</A
4489></TT
4490> when
4491 applied to their respective values. For example, the following
4492 expressions are all <TT
4493><A HREF="Prelude.html#v%3ATrue"
4494>True</A
4495></TT
4496>:
4497</P
4498><PRE
4499> isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
4500 isProperSubmapOfBy (&lt;=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
4501</PRE
4502><P
4503>But the following are all <TT
4504><A HREF="Prelude.html#v%3AFalse"
4505>False</A
4506></TT
4507>:
4508</P
4509><PRE
4510> isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
4511 isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
4512 isProperSubmapOfBy (&lt;)  (fromList [(1,1)])       (fromList [(1,1),(2,2)])
4513</PRE
4514></TD
4515></TR
4516><TR
4517><TD CLASS="s15"
4518></TD
4519></TR
4520><TR
4521><TD CLASS="section1"
4522><A NAME="19"
4523>Min/Max
4524</A
4525></TD
4526></TR
4527><TR
4528><TD CLASS="s15"
4529></TD
4530></TR
4531><TR
4532><TD CLASS="decl"
4533><A NAME="v%3AupdateMin"
4534></A
4535><B
4536>updateMin</B
4537> :: (a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4538>IntMap</A
4539> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4540>IntMap</A
4541> a</TD
4542></TR
4543><TR
4544><TD CLASS="doc"
4545><P
4546><EM
4547>O(log n)</EM
4548>. Update the value at the minimal key.
4549</P
4550><PRE
4551> 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;)]
4552 updateMin (\ _ -&gt; Nothing)         (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;a&quot;
4553</PRE
4554></TD
4555></TR
4556><TR
4557><TD CLASS="s15"
4558></TD
4559></TR
4560><TR
4561><TD CLASS="decl"
4562><A NAME="v%3AupdateMax"
4563></A
4564><B
4565>updateMax</B
4566> :: (a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4567>IntMap</A
4568> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4569>IntMap</A
4570> a</TD
4571></TR
4572><TR
4573><TD CLASS="doc"
4574><P
4575><EM
4576>O(log n)</EM
4577>. Update the value at the maximal key.
4578</P
4579><PRE
4580> 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;)]
4581 updateMax (\ _ -&gt; Nothing)         (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;b&quot;
4582</PRE
4583></TD
4584></TR
4585><TR
4586><TD CLASS="s15"
4587></TD
4588></TR
4589><TR
4590><TD CLASS="decl"
4591><A NAME="v%3AupdateMinWithKey"
4592></A
4593><B
4594>updateMinWithKey</B
4595> :: (<A HREF="Data-IntMap.html#t%3AKey"
4596>Key</A
4597> -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4598>IntMap</A
4599> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4600>IntMap</A
4601> a</TD
4602></TR
4603><TR
4604><TD CLASS="doc"
4605><P
4606><EM
4607>O(log n)</EM
4608>. Update the value at the minimal key.
4609</P
4610><PRE
4611> 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;)]
4612 updateMinWithKey (\ _ _ -&gt; Nothing)                     (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 5 &quot;a&quot;
4613</PRE
4614></TD
4615></TR
4616><TR
4617><TD CLASS="s15"
4618></TD
4619></TR
4620><TR
4621><TD CLASS="decl"
4622><A NAME="v%3AupdateMaxWithKey"
4623></A
4624><B
4625>updateMaxWithKey</B
4626> :: (<A HREF="Data-IntMap.html#t%3AKey"
4627>Key</A
4628> -&gt; a -&gt; a) -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4629>IntMap</A
4630> a -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4631>IntMap</A
4632> a</TD
4633></TR
4634><TR
4635><TD CLASS="doc"
4636><P
4637><EM
4638>O(log n)</EM
4639>. Update the value at the maximal key.
4640</P
4641><PRE
4642> 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;)]
4643 updateMaxWithKey (\ _ _ -&gt; Nothing)                     (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)]) == singleton 3 &quot;b&quot;
4644</PRE
4645></TD
4646></TR
4647><TR
4648><TD CLASS="s15"
4649></TD
4650></TR
4651><TR
4652><TD CLASS="decl"
4653><A NAME="v%3AminViewWithKey"
4654></A
4655><B
4656>minViewWithKey</B
4657> :: <A HREF="Prelude.html#t%3AMonad"
4658>Monad</A
4659> m =&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4660>IntMap</A
4661> a -&gt; m ((<A HREF="Data-IntMap.html#t%3AKey"
4662>Key</A
4663>, a), <A HREF="Data-IntMap.html#t%3AIntMap"
4664>IntMap</A
4665> a)</TD
4666></TR
4667><TR
4668><TD CLASS="doc"
4669><P
4670><EM
4671>O(log n)</EM
4672>. Retrieves the minimal (key,value) couple of the map, and the map stripped from that element.
4673 <TT
4674>fail</TT
4675>s (in the monad) when passed an empty map.
4676</P
4677><PRE
4678> v &lt;- minViewWithKey (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])
4679 v ==  ((3,&quot;b&quot;), singleton 5 &quot;a&quot;)
4680 minViewWithKey empty              Error: empty map
4681</PRE
4682></TD
4683></TR
4684><TR
4685><TD CLASS="s15"
4686></TD
4687></TR
4688><TR
4689><TD CLASS="decl"
4690><A NAME="v%3AmaxViewWithKey"
4691></A
4692><B
4693>maxViewWithKey</B
4694> :: <A HREF="Prelude.html#t%3AMonad"
4695>Monad</A
4696> m =&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4697>IntMap</A
4698> a -&gt; m ((<A HREF="Data-IntMap.html#t%3AKey"
4699>Key</A
4700>, a), <A HREF="Data-IntMap.html#t%3AIntMap"
4701>IntMap</A
4702> a)</TD
4703></TR
4704><TR
4705><TD CLASS="doc"
4706><P
4707><EM
4708>O(log n)</EM
4709>. Retrieves the maximal (key,value) couple of the map, and the map stripped from that element.
4710 <TT
4711>fail</TT
4712>s (in the monad) when passed an empty map.
4713</P
4714><PRE
4715> v &lt;- maxViewWithKey (fromList [(5,&quot;a&quot;), (3,&quot;b&quot;)])
4716 v == ((5,&quot;a&quot;), singleton 3 &quot;b&quot;)
4717 maxViewWithKey empty              Error: empty map
4718</PRE
4719></TD
4720></TR
4721><TR
4722><TD CLASS="s15"
4723></TD
4724></TR
4725><TR
4726><TD CLASS="section1"
4727><A NAME="20"
4728>Debugging
4729</A
4730></TD
4731></TR
4732><TR
4733><TD CLASS="s15"
4734></TD
4735></TR
4736><TR
4737><TD CLASS="decl"
4738><A NAME="v%3AshowTree"
4739></A
4740><B
4741>showTree</B
4742> :: <A HREF="Prelude.html#t%3AShow"
4743>Show</A
4744> a =&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4745>IntMap</A
4746> a -&gt; <A HREF="Prelude.html#t%3AString"
4747>String</A
4748></TD
4749></TR
4750><TR
4751><TD CLASS="doc"
4752><EM
4753>O(n)</EM
4754>. Show the tree that implements the map. The tree is shown
4755 in a compressed, hanging format.
4756</TD
4757></TR
4758><TR
4759><TD CLASS="s15"
4760></TD
4761></TR
4762><TR
4763><TD CLASS="decl"
4764><A NAME="v%3AshowTreeWith"
4765></A
4766><B
4767>showTreeWith</B
4768> :: <A HREF="Prelude.html#t%3AShow"
4769>Show</A
4770> a =&gt; <A HREF="Prelude.html#t%3ABool"
4771>Bool</A
4772> -&gt; <A HREF="Prelude.html#t%3ABool"
4773>Bool</A
4774> -&gt; <A HREF="Data-IntMap.html#t%3AIntMap"
4775>IntMap</A
4776> a -&gt; <A HREF="Prelude.html#t%3AString"
4777>String</A
4778></TD
4779></TR
4780><TR
4781><TD CLASS="doc"
4782><EM
4783>O(n)</EM
4784>. The expression (<TT
4785><TT
4786><A HREF="Data-IntMap.html#v%3AshowTreeWith"
4787>showTreeWith</A
4788></TT
4789> hang wide map</TT
4790>) shows
4791 the tree that implements the map. If <TT
4792>hang</TT
4793> is
4794 <TT
4795><A HREF="Prelude.html#v%3ATrue"
4796>True</A
4797></TT
4798>, a <EM
4799>hanging</EM
4800> tree is shown otherwise a rotated tree is shown. If
4801 <TT
4802>wide</TT
4803> is <TT
4804><A HREF="Prelude.html#v%3ATrue"
4805>True</A
4806></TT
4807>, an extra wide version is shown.
4808</TD
4809></TR
4810><TR
4811><TD CLASS="s15"
4812></TD
4813></TR
4814><TR
4815><TD CLASS="botbar"
4816>Produced by <A HREF="http://www.haskell.org/haddock/"
4817>Haddock</A
4818> version 0.8</TD
4819></TR
4820></TABLE
4821></BODY
4822></HTML
4823>