<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!--Rendered using the Haskell Html Library v0.2-->
<HTML
><HEAD
><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"
><TITLE
>Data.IntMap</TITLE
><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"
><SCRIPT SRC="haddock-util.js" TYPE="text/javascript"
></SCRIPT
><SCRIPT TYPE="text/javascript"
>window.onload = function () {setSynopsis("mini_Data-IntMap.html")};</SCRIPT
></HEAD
><BODY
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="topbar"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD
><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "
></TD
><TD CLASS="title"
>containers-0.2.0.1: Assorted concrete container types</TD
><TD CLASS="topbut"
><A HREF="index.html"
>Contents</A
></TD
><TD CLASS="topbut"
><A HREF="doc-index.html"
>Index</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="modulebar"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD
><FONT SIZE="6"
>Data.IntMap</FONT
></TD
><TD ALIGN="right"
><TABLE CLASS="narrow" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="infohead"
>Portability</TD
><TD CLASS="infoval"
>portable</TD
></TR
><TR
><TD CLASS="infohead"
>Stability</TD
><TD CLASS="infoval"
>provisional</TD
></TR
><TR
><TD CLASS="infohead"
>Maintainer</TD
><TD CLASS="infoval"
>libraries@haskell.org</TD
></TR
></TABLE
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="section4"
><B
>Contents</B
></TD
></TR
><TR
><TD
><DL
><DT
><A HREF="#1"
>Map type
</A
></DT
><DT
><A HREF="#2"
>Operators
</A
></DT
><DT
><A HREF="#3"
>Query
</A
></DT
><DT
><A HREF="#4"
>Construction
</A
></DT
><DD
><DL
><DT
><A HREF="#5"
>Insertion
</A
></DT
><DT
><A HREF="#6"
>Delete/Update
</A
></DT
></DL
></DD
><DT
><A HREF="#7"
>Combine
</A
></DT
><DD
><DL
><DT
><A HREF="#8"
>Union
</A
></DT
><DT
><A HREF="#9"
>Difference
</A
></DT
><DT
><A HREF="#10"
>Intersection
</A
></DT
></DL
></DD
><DT
><A HREF="#11"
>Traversal
</A
></DT
><DD
><DL
><DT
><A HREF="#12"
>Map
</A
></DT
><DT
><A HREF="#13"
>Fold
</A
></DT
></DL
></DD
><DT
><A HREF="#14"
>Conversion
</A
></DT
><DD
><DL
><DT
><A HREF="#15"
>Lists
</A
></DT
><DT
><A HREF="#16"
>Ordered lists
</A
></DT
></DL
></DD
><DT
><A HREF="#17"
>Filter
</A
></DT
><DT
><A HREF="#18"
>Submap
</A
></DT
><DT
><A HREF="#19"
>Min/Max
</A
></DT
><DT
><A HREF="#20"
>Debugging
</A
></DT
></DL
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Description</TD
></TR
><TR
><TD CLASS="doc"
><P
>An efficient implementation of maps from integer keys to values.
</P
><P
>Since many function names (but not the type name) clash with
<A HREF="Prelude.html"
>Prelude</A
> names, this module is usually imported <TT
>qualified</TT
>, e.g.
</P
><PRE
> import Data.IntMap (IntMap)
import qualified Data.IntMap as IntMap
</PRE
><P
>The implementation is based on <EM
>big-endian patricia trees</EM
>. This data
structure performs especially well on binary operations like <TT
><A HREF="Data-IntMap.html#v%3Aunion"
>union</A
></TT
>
and <TT
><A HREF="Data-IntMap.html#v%3Aintersection"
>intersection</A
></TT
>. However, my benchmarks show that it is also
(much) faster on insertions and deletions when compared to a generic
size-balanced map implementation (see <A HREF="Data-Map.html"
>Data.Map</A
>).
</P
><UL
><LI
> Chris Okasaki and Andy Gill, "<EM
>Fast Mergeable Integer Maps</EM
>",
Workshop on ML, September 1998, pages 77-86,
<A HREF="http://citeseer.ist.psu.edu/okasaki98fast.html"
>http://citeseer.ist.psu.edu/okasaki98fast.html</A
>
</LI
><LI
> D.R. Morrison, "/PATRICIA -- Practical Algorithm To Retrieve
Information Coded In Alphanumeric/", Journal of the ACM, 15(4),
October 1968, pages 514-534.
</LI
></UL
><P
>Operation comments contain the operation time complexity in
the Big-O notation <A HREF="http://en.wikipedia.org/wiki/Big_O_notation"
>http://en.wikipedia.org/wiki/Big_O_notation</A
>.
Many operations have a worst-case complexity of <EM
>O(min(n,W))</EM
>.
This means that the operation can become linear in the number of
elements with a maximum of <EM
>W</EM
> -- the number of bits in an <TT
><A HREF="../ghc-prim/GHC-Types.html#t%3AInt"
>Int</A
></TT
>
(32 or 64).
</P
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Synopsis</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="body"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="decl"
><SPAN CLASS="keyword"
>data</SPAN
> <A HREF="#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><SPAN CLASS="keyword"
>type</SPAN
> <A HREF="#t%3AKey"
>Key</A
> = <A HREF="../ghc-prim/GHC-Types.html#t%3AInt"
>Int</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3A%21"
>(!)</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3A%5C%5C"
>(\\)</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Anull"
>null</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Asize"
>size</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../ghc-prim/GHC-Types.html#t%3AInt"
>Int</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Amember"
>member</A
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AnotMember"
>notMember</A
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Alookup"
>lookup</A
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfindWithDefault"
>findWithDefault</A
> :: a -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aempty"
>empty</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Asingleton"
>singleton</A
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Ainsert"
>insert</A
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AinsertWith"
>insertWith</A
> :: (a -> a -> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AinsertWithKey"
>insertWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a -> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AinsertLookupWithKey"
>insertLookupWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a -> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Adelete"
>delete</A
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aadjust"
>adjust</A
> :: (a -> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AadjustWithKey"
>adjustWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aupdate"
>update</A
> :: (a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AupdateWithKey"
>updateWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AupdateLookupWithKey"
>updateLookupWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aalter"
>alter</A
> :: (<A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a) -> <A HREF="../ghc-prim/GHC-Types.html#t%3AInt"
>Int</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aunion"
>union</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AunionWith"
>unionWith</A
> :: (a -> a -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AunionWithKey"
>unionWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aunions"
>unions</A
> :: [<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AunionsWith"
>unionsWith</A
> :: (a -> a -> a) -> [<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Adifference"
>difference</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AdifferenceWith"
>differenceWith</A
> :: (a -> b -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AdifferenceWithKey"
>differenceWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> b -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aintersection"
>intersection</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AintersectionWith"
>intersectionWith</A
> :: (a -> b -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AintersectionWithKey"
>intersectionWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> b -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Amap"
>map</A
> :: (a -> b) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmapWithKey"
>mapWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> b) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmapAccum"
>mapAccum</A
> :: (a -> b -> (a, c)) -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> (a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> c)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmapAccumWithKey"
>mapAccumWithKey</A
> :: (a -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> b -> (a, c)) -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> (a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> c)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Afold"
>fold</A
> :: (a -> b -> b) -> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> b</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfoldWithKey"
>foldWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> b -> b) -> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> b</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aelems"
>elems</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> [a]</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Akeys"
>keys</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> [<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>]</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AkeysSet"
>keysSet</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntSet.html#t%3AIntSet"
>IntSet</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aassocs"
>assocs</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)]</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AtoList"
>toList</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)]</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfromList"
>fromList</A
> :: [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfromListWith"
>fromListWith</A
> :: (a -> a -> a) -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfromListWithKey"
>fromListWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a -> a) -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AtoAscList"
>toAscList</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)]</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfromAscList"
>fromAscList</A
> :: [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfromAscListWith"
>fromAscListWith</A
> :: (a -> a -> a) -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfromAscListWithKey"
>fromAscListWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a -> a) -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfromDistinctAscList"
>fromDistinctAscList</A
> :: [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Afilter"
>filter</A
> :: (a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfilterWithKey"
>filterWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Apartition"
>partition</A
> :: (a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3ApartitionWithKey"
>partitionWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmapMaybe"
>mapMaybe</A
> :: (a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> b) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmapMaybeWithKey"
>mapMaybeWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> b) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmapEither"
>mapEither</A
> :: (a -> <A HREF="../base/Data-Either.html#t%3AEither"
>Either</A
> b c) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> c)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmapEitherWithKey"
>mapEitherWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="../base/Data-Either.html#t%3AEither"
>Either</A
> b c) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> c)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Asplit"
>split</A
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AsplitLookup"
>splitLookup</A
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a, <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AisSubmapOf"
>isSubmapOf</A
> :: <A HREF="../base/Data-Eq.html#t%3AEq"
>Eq</A
> a => <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AisSubmapOfBy"
>isSubmapOfBy</A
> :: (a -> b -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AisProperSubmapOf"
>isProperSubmapOf</A
> :: <A HREF="../base/Data-Eq.html#t%3AEq"
>Eq</A
> a => <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AisProperSubmapOfBy"
>isProperSubmapOfBy</A
> :: (a -> b -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmaxView"
>maxView</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> (a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AminView"
>minView</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> (a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfindMin"
>findMin</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfindMax"
>findMax</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AdeleteMin"
>deleteMin</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AdeleteMax"
>deleteMax</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AdeleteFindMin"
>deleteFindMin</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AdeleteFindMax"
>deleteFindMax</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AupdateMin"
>updateMin</A
> :: (a -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AupdateMax"
>updateMax</A
> :: (a -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AupdateMinWithKey"
>updateMinWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AupdateMaxWithKey"
>updateMaxWithKey</A
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AminViewWithKey"
>minViewWithKey</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> ((<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a), <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmaxViewWithKey"
>maxViewWithKey</A
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> ((<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a), <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AshowTree"
>showTree</A
> :: <A HREF="../base/Text-Show.html#t%3AShow"
>Show</A
> a => <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Char.html#t%3AString"
>String</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AshowTreeWith"
>showTreeWith</A
> :: <A HREF="../base/Text-Show.html#t%3AShow"
>Show</A
> a => <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
> -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Char.html#t%3AString"
>String</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="1"
><A NAME="1"
>Map type
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><SPAN CLASS="keyword"
>data</SPAN
> <A NAME="t:IntMap"
><A NAME="t%3AIntMap"
></A
></A
><B
>IntMap</B
> a </TD
></TR
><TR
><TD CLASS="body"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="ndoc"
>A map of integers to values <TT
>a</TT
>.
</TD
></TR
><TR
><TD CLASS="section4"
><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:IntMap')" ALT="show/hide"
> Instances</TD
></TR
><TR
><TD CLASS="body"
><DIV ID="i:IntMap" STYLE="display:block;"
><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"
><TR
><TD CLASS="decl"
><A HREF="../base/Control-Monad.html#t%3AFunctor"
>Functor</A
> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Data-Typeable.html#t%3ATypeable1"
>Typeable1</A
> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Data-Foldable.html#t%3AFoldable"
>Foldable</A
> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Data-Eq.html#t%3AEq"
>Eq</A
> a => <A HREF="../base/Data-Eq.html#t%3AEq"
>Eq</A
> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Data-Data.html#t%3AData"
>Data</A
> a => <A HREF="../base/Data-Data.html#t%3AData"
>Data</A
> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Text-Read.html#t%3ARead"
>Read</A
> e => <A HREF="../base/Text-Read.html#t%3ARead"
>Read</A
> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> e)</TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Text-Show.html#t%3AShow"
>Show</A
> a => <A HREF="../base/Text-Show.html#t%3AShow"
>Show</A
> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Data-Monoid.html#t%3AMonoid"
>Monoid</A
> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
></TABLE
></DIV
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><SPAN CLASS="keyword"
>type</SPAN
> <A NAME="t:Key"
><A NAME="t%3AKey"
></A
></A
><B
>Key</B
> = <A HREF="../ghc-prim/GHC-Types.html#t%3AInt"
>Int</A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="2"
><A NAME="2"
>Operators
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:!"
><A NAME="v%3A%21"
></A
></A
><B
>(!)</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. Find the value at a key.
Calls <TT
><A HREF="../base/Prelude.html#v%3Aerror"
>error</A
></TT
> when the element can not be found.
</P
><PRE
> fromList [(5,'a'), (3,'b')] ! 1 Error: element not in the map
fromList [(5,'a'), (3,'b')] ! 5 == 'a'
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:\\"
><A NAME="v%3A%5C%5C"
></A
></A
><B
>(\\)</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
>Same as <TT
><A HREF="Data-IntMap.html#v%3Adifference"
>difference</A
></TT
>.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="3"
><A NAME="3"
>Query
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:null"
><A NAME="v%3Anull"
></A
></A
><B
>null</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(1)</EM
>. Is the map empty?
</P
><PRE
> Data.IntMap.null (empty) == True
Data.IntMap.null (singleton 1 'a') == False
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:size"
><A NAME="v%3Asize"
></A
></A
><B
>size</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../ghc-prim/GHC-Types.html#t%3AInt"
>Int</A
></TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Number of elements in the map.
</P
><PRE
> size empty == 0
size (singleton 1 'a') == 1
size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:member"
><A NAME="v%3Amember"
></A
></A
><B
>member</B
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. Is the key a member of the map?
</P
><PRE
> member 5 (fromList [(5,'a'), (3,'b')]) == True
member 1 (fromList [(5,'a'), (3,'b')]) == False
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:notMember"
><A NAME="v%3AnotMember"
></A
></A
><B
>notMember</B
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(log n)</EM
>. Is the key not a member of the map?
</P
><PRE
> notMember 5 (fromList [(5,'a'), (3,'b')]) == False
notMember 1 (fromList [(5,'a'), (3,'b')]) == True
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:lookup"
><A NAME="v%3Alookup"
></A
></A
><B
>lookup</B
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(min(n,W))</EM
>. Lookup the value at a key in the map. See also Data.Map.lookup.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:findWithDefault"
><A NAME="v%3AfindWithDefault"
></A
></A
><B
>findWithDefault</B
> :: a -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. The expression <TT
>(<TT
><A HREF="Data-IntMap.html#v%3AfindWithDefault"
>findWithDefault</A
></TT
> def k map)</TT
>
returns the value at key <TT
>k</TT
> or returns <TT
>def</TT
> when the key is not an
element of the map.
</P
><PRE
> findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="4"
><A NAME="4"
>Construction
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:empty"
><A NAME="v%3Aempty"
></A
></A
><B
>empty</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(1)</EM
>. The empty map.
</P
><PRE
> empty == fromList []
size empty == 0
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:singleton"
><A NAME="v%3Asingleton"
></A
></A
><B
>singleton</B
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(1)</EM
>. A map of one element.
</P
><PRE
> singleton 1 'a' == fromList [(1, 'a')]
size (singleton 1 'a') == 1
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section2"
><A NAME="5"
><A NAME="5"
>Insertion
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:insert"
><A NAME="v%3Ainsert"
></A
></A
><B
>insert</B
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. Insert a new key/value pair in the map.
If the key is already present in the map, the associated value is
replaced with the supplied value, i.e. <TT
><A HREF="Data-IntMap.html#v%3Ainsert"
>insert</A
></TT
> is equivalent to
<TT
><TT
><A HREF="Data-IntMap.html#v%3AinsertWith"
>insertWith</A
></TT
> <TT
><A HREF="../base/Prelude.html#v%3Aconst"
>const</A
></TT
></TT
>.
</P
><PRE
> insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]
insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]
insert 5 'x' empty == singleton 5 'x'
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:insertWith"
><A NAME="v%3AinsertWith"
></A
></A
><B
>insertWith</B
> :: (a -> a -> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. Insert with a combining function.
<TT
><TT
><A HREF="Data-IntMap.html#v%3AinsertWith"
>insertWith</A
></TT
> f key value mp</TT
>
will insert the pair (key, value) into <TT
>mp</TT
> if key does
not exist in the map. If the key does exist, the function will
insert <TT
>f new_value old_value</TT
>.
</P
><PRE
> insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]
insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
insertWith (++) 5 "xxx" empty == singleton 5 "xxx"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:insertWithKey"
><A NAME="v%3AinsertWithKey"
></A
></A
><B
>insertWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a -> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. Insert with a combining function.
<TT
><TT
><A HREF="Data-IntMap.html#v%3AinsertWithKey"
>insertWithKey</A
></TT
> f key value mp</TT
>
will insert the pair (key, value) into <TT
>mp</TT
> if key does
not exist in the map. If the key does exist, the function will
insert <TT
>f key new_value old_value</TT
>.
</P
><PRE
> let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")]
insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
insertWithKey f 5 "xxx" empty == singleton 5 "xxx"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:insertLookupWithKey"
><A NAME="v%3AinsertLookupWithKey"
></A
></A
><B
>insertLookupWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a -> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. The expression (<TT
><TT
><A HREF="Data-IntMap.html#v%3AinsertLookupWithKey"
>insertLookupWithKey</A
></TT
> f k x map</TT
>)
is a pair where the first element is equal to (<TT
><TT
><A HREF="Data-IntMap.html#v%3Alookup"
>lookup</A
></TT
> k map</TT
>)
and the second element equal to (<TT
><TT
><A HREF="Data-IntMap.html#v%3AinsertWithKey"
>insertWithKey</A
></TT
> f k x map</TT
>).
</P
><PRE
> let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])
insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "xxx")])
insertLookupWithKey f 5 "xxx" empty == (Nothing, singleton 5 "xxx")
</PRE
><P
>This is how to define <TT
>insertLookup</TT
> using <TT
>insertLookupWithKey</TT
>:
</P
><PRE
> let insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t
insertLookup 5 "x" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "x")])
insertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "x")])
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section2"
><A NAME="6"
><A NAME="6"
>Delete/Update
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:delete"
><A NAME="v%3Adelete"
></A
></A
><B
>delete</B
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. Delete a key and its value from the map. When the key is not
a member of the map, the original map is returned.
</P
><PRE
> delete 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
delete 5 empty == empty
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:adjust"
><A NAME="v%3Aadjust"
></A
></A
><B
>adjust</B
> :: (a -> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. Adjust a value at a specific key. When the key is not
a member of the map, the original map is returned.
</P
><PRE
> adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
adjust ("new " ++) 7 empty == empty
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:adjustWithKey"
><A NAME="v%3AadjustWithKey"
></A
></A
><B
>adjustWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. Adjust a value at a specific key. When the key is not
a member of the map, the original map is returned.
</P
><PRE
> let f key x = (show key) ++ ":new " ++ x
adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
adjustWithKey f 7 empty == empty
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:update"
><A NAME="v%3Aupdate"
></A
></A
><B
>update</B
> :: (a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. The expression (<TT
><TT
><A HREF="Data-IntMap.html#v%3Aupdate"
>update</A
></TT
> f k map</TT
>) updates the value <TT
>x</TT
>
at <TT
>k</TT
> (if it is in the map). If (<TT
>f x</TT
>) is <TT
><A HREF="../base/Data-Maybe.html#v%3ANothing"
>Nothing</A
></TT
>, the element is
deleted. If it is (<TT
><TT
><A HREF="../base/Data-Maybe.html#v%3AJust"
>Just</A
></TT
> y</TT
>), the key <TT
>k</TT
> is bound to the new value <TT
>y</TT
>.
</P
><PRE
> let f x = if x == "a" then Just "new a" else Nothing
update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:updateWithKey"
><A NAME="v%3AupdateWithKey"
></A
></A
><B
>updateWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. The expression (<TT
><TT
><A HREF="Data-IntMap.html#v%3Aupdate"
>update</A
></TT
> f k map</TT
>) updates the value <TT
>x</TT
>
at <TT
>k</TT
> (if it is in the map). If (<TT
>f k x</TT
>) is <TT
><A HREF="../base/Data-Maybe.html#v%3ANothing"
>Nothing</A
></TT
>, the element is
deleted. If it is (<TT
><TT
><A HREF="../base/Data-Maybe.html#v%3AJust"
>Just</A
></TT
> y</TT
>), the key <TT
>k</TT
> is bound to the new value <TT
>y</TT
>.
</P
><PRE
> let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:updateLookupWithKey"
><A NAME="v%3AupdateLookupWithKey"
></A
></A
><B
>updateLookupWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a) -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(min(n,W))</EM
>. Lookup and update.
The function returns original value, if it is updated.
This is different behavior than Data.Map.updateLookupWithKey.
Returns the original key value if the map entry is deleted.
</P
><PRE
> let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:new a")])
updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a")])
updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:alter"
><A NAME="v%3Aalter"
></A
></A
><B
>alter</B
> :: (<A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a) -> <A HREF="../ghc-prim/GHC-Types.html#t%3AInt"
>Int</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. The expression (<TT
><TT
><A HREF="Data-IntMap.html#v%3Aalter"
>alter</A
></TT
> f k map</TT
>) alters the value <TT
>x</TT
> at <TT
>k</TT
>, or absence thereof.
<TT
><A HREF="Data-IntMap.html#v%3Aalter"
>alter</A
></TT
> can be used to insert, delete, or update a value in an <TT
><A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
></TT
>.
In short : <TT
><TT
><A HREF="Data-IntMap.html#v%3Alookup"
>lookup</A
></TT
> k (<TT
><A HREF="Data-IntMap.html#v%3Aalter"
>alter</A
></TT
> f k m) = f (<TT
><A HREF="Data-IntMap.html#v%3Alookup"
>lookup</A
></TT
> k m)</TT
>.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="7"
><A NAME="7"
>Combine
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section2"
><A NAME="8"
><A NAME="8"
>Union
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:union"
><A NAME="v%3Aunion"
></A
></A
><B
>union</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n+m)</EM
>. The (left-biased) union of two maps.
It prefers the first map when duplicate keys are encountered,
i.e. (<TT
><TT
><A HREF="Data-IntMap.html#v%3Aunion"
>union</A
></TT
> == <TT
><A HREF="Data-IntMap.html#v%3AunionWith"
>unionWith</A
></TT
> <TT
><A HREF="../base/Prelude.html#v%3Aconst"
>const</A
></TT
></TT
>).
</P
><PRE
> union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:unionWith"
><A NAME="v%3AunionWith"
></A
></A
><B
>unionWith</B
> :: (a -> a -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n+m)</EM
>. The union with a combining function.
</P
><PRE
> unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:unionWithKey"
><A NAME="v%3AunionWithKey"
></A
></A
><B
>unionWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n+m)</EM
>. The union with a combining function.
</P
><PRE
> let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:unions"
><A NAME="v%3Aunions"
></A
></A
><B
>unions</B
> :: [<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
>The union of a list of maps.
</P
><PRE
> unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
== fromList [(3, "b"), (5, "a"), (7, "C")]
unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
== fromList [(3, "B3"), (5, "A3"), (7, "C")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:unionsWith"
><A NAME="v%3AunionsWith"
></A
></A
><B
>unionsWith</B
> :: (a -> a -> a) -> [<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
>The union of a list of maps, with a combining operation.
</P
><PRE
> unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
== fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section2"
><A NAME="9"
><A NAME="9"
>Difference
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:difference"
><A NAME="v%3Adifference"
></A
></A
><B
>difference</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n+m)</EM
>. Difference between two maps (based on keys).
</P
><PRE
> difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:differenceWith"
><A NAME="v%3AdifferenceWith"
></A
></A
><B
>differenceWith</B
> :: (a -> b -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n+m)</EM
>. Difference with a combining function.
</P
><PRE
> let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
== singleton 3 "b:B"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:differenceWithKey"
><A NAME="v%3AdifferenceWithKey"
></A
></A
><B
>differenceWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> b -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n+m)</EM
>. Difference with a combining function. When two equal keys are
encountered, the combining function is applied to the key and both values.
If it returns <TT
><A HREF="../base/Data-Maybe.html#v%3ANothing"
>Nothing</A
></TT
>, the element is discarded (proper set difference).
If it returns (<TT
><TT
><A HREF="../base/Data-Maybe.html#v%3AJust"
>Just</A
></TT
> y</TT
>), the element is updated with a new value <TT
>y</TT
>.
</P
><PRE
> let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
== singleton 3 "3:b|B"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section2"
><A NAME="10"
><A NAME="10"
>Intersection
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:intersection"
><A NAME="v%3Aintersection"
></A
></A
><B
>intersection</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n+m)</EM
>. The (left-biased) intersection of two maps (based on keys).
</P
><PRE
> intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:intersectionWith"
><A NAME="v%3AintersectionWith"
></A
></A
><B
>intersectionWith</B
> :: (a -> b -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n+m)</EM
>. The intersection with a combining function.
</P
><PRE
> intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:intersectionWithKey"
><A NAME="v%3AintersectionWithKey"
></A
></A
><B
>intersectionWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> b -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n+m)</EM
>. The intersection with a combining function.
</P
><PRE
> let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="11"
><A NAME="11"
>Traversal
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section2"
><A NAME="12"
><A NAME="12"
>Map
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:map"
><A NAME="v%3Amap"
></A
></A
><B
>map</B
> :: (a -> b) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Map a function over all values in the map.
</P
><PRE
> map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:mapWithKey"
><A NAME="v%3AmapWithKey"
></A
></A
><B
>mapWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> b) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Map a function over all values in the map.
</P
><PRE
> let f key x = (show key) ++ ":" ++ x
mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:mapAccum"
><A NAME="v%3AmapAccum"
></A
></A
><B
>mapAccum</B
> :: (a -> b -> (a, c)) -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> (a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> c)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. The function <TT
><TT
><A HREF="Data-IntMap.html#v%3AmapAccum"
>mapAccum</A
></TT
></TT
> threads an accumulating
argument through the map in ascending order of keys.
</P
><PRE
> let f a b = (a ++ b, b ++ "X")
mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:mapAccumWithKey"
><A NAME="v%3AmapAccumWithKey"
></A
></A
><B
>mapAccumWithKey</B
> :: (a -> <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> b -> (a, c)) -> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> (a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> c)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. The function <TT
><TT
><A HREF="Data-IntMap.html#v%3AmapAccumWithKey"
>mapAccumWithKey</A
></TT
></TT
> threads an accumulating
argument through the map in ascending order of keys.
</P
><PRE
> let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section2"
><A NAME="13"
><A NAME="13"
>Fold
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:fold"
><A NAME="v%3Afold"
></A
></A
><B
>fold</B
> :: (a -> b -> b) -> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> b</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Fold the values in the map, such that
<TT
><TT
><A HREF="Data-IntMap.html#v%3Afold"
>fold</A
></TT
> f z == Prelude.foldr f z . <TT
><A HREF="Data-IntMap.html#v%3Aelems"
>elems</A
></TT
></TT
>.
For example,
</P
><PRE
> elems map = fold (:) [] map
</PRE
><PRE
> let f a len = len + (length a)
fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:foldWithKey"
><A NAME="v%3AfoldWithKey"
></A
></A
><B
>foldWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> b -> b) -> b -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> b</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Fold the keys and values in the map, such that
<TT
><TT
><A HREF="Data-IntMap.html#v%3AfoldWithKey"
>foldWithKey</A
></TT
> f z == Prelude.foldr (<TT
><A HREF="../base/Data-Tuple.html#v%3Auncurry"
>uncurry</A
></TT
> f) z . <TT
><A HREF="Data-IntMap.html#v%3AtoAscList"
>toAscList</A
></TT
></TT
>.
For example,
</P
><PRE
> keys map = foldWithKey (\k x ks -> k:ks) [] map
</PRE
><PRE
> let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
foldWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="14"
><A NAME="14"
>Conversion
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:elems"
><A NAME="v%3Aelems"
></A
></A
><B
>elems</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> [a]</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>.
Return all elements of the map in the ascending order of their keys.
</P
><PRE
> elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
elems empty == []
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:keys"
><A NAME="v%3Akeys"
></A
></A
><B
>keys</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> [<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>]</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Return all keys of the map in ascending order.
</P
><PRE
> keys (fromList [(5,"a"), (3,"b")]) == [3,5]
keys empty == []
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:keysSet"
><A NAME="v%3AkeysSet"
></A
></A
><B
>keysSet</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntSet.html#t%3AIntSet"
>IntSet</A
></TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n*min(n,W))</EM
>. The set of all keys of the map.
</P
><PRE
> keysSet (fromList [(5,"a"), (3,"b")]) == Data.IntSet.fromList [3,5]
keysSet empty == Data.IntSet.empty
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:assocs"
><A NAME="v%3Aassocs"
></A
></A
><B
>assocs</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)]</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Return all key/value pairs in the map in ascending key order.
</P
><PRE
> assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
assocs empty == []
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section2"
><A NAME="15"
><A NAME="15"
>Lists
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:toList"
><A NAME="v%3AtoList"
></A
></A
><B
>toList</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)]</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Convert the map to a list of key/value pairs.
</P
><PRE
> toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
toList empty == []
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:fromList"
><A NAME="v%3AfromList"
></A
></A
><B
>fromList</B
> :: [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n*min(n,W))</EM
>. Create a map from a list of key/value pairs.
</P
><PRE
> fromList [] == empty
fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:fromListWith"
><A NAME="v%3AfromListWith"
></A
></A
><B
>fromListWith</B
> :: (a -> a -> a) -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n*min(n,W))</EM
>. Create a map from a list of key/value pairs with a combining function. See also <TT
><A HREF="Data-IntMap.html#v%3AfromAscListWith"
>fromAscListWith</A
></TT
>.
</P
><PRE
> fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
fromListWith (++) [] == empty
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:fromListWithKey"
><A NAME="v%3AfromListWithKey"
></A
></A
><B
>fromListWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a -> a) -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n*min(n,W))</EM
>. Build a map from a list of key/value pairs with a combining function. See also fromAscListWithKey'.
</P
><PRE
> fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
fromListWith (++) [] == empty
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section2"
><A NAME="16"
><A NAME="16"
>Ordered lists
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:toAscList"
><A NAME="v%3AtoAscList"
></A
></A
><B
>toAscList</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)]</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Convert the map to a list of key/value pairs where the
keys are in ascending order.
</P
><PRE
> toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:fromAscList"
><A NAME="v%3AfromAscList"
></A
></A
><B
>fromAscList</B
> :: [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n*min(n,W))</EM
>. Build a map from a list of key/value pairs where
the keys are in ascending order.
</P
><PRE
> fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:fromAscListWith"
><A NAME="v%3AfromAscListWith"
></A
></A
><B
>fromAscListWith</B
> :: (a -> a -> a) -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n*min(n,W))</EM
>. Build a map from a list of key/value pairs where
the keys are in ascending order, with a combining function on equal keys.
</P
><PRE
> fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:fromAscListWithKey"
><A NAME="v%3AfromAscListWithKey"
></A
></A
><B
>fromAscListWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a -> a) -> [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n*min(n,W))</EM
>. Build a map from a list of key/value pairs where
the keys are in ascending order, with a combining function on equal keys.
</P
><PRE
> fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:fromDistinctAscList"
><A NAME="v%3AfromDistinctAscList"
></A
></A
><B
>fromDistinctAscList</B
> :: [(<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a)] -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n*min(n,W))</EM
>. Build a map from a list of key/value pairs where
the keys are in ascending order and all distinct.
</P
><PRE
> fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="17"
><A NAME="17"
>Filter
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:filter"
><A NAME="v%3Afilter"
></A
></A
><B
>filter</B
> :: (a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Filter all values that satisfy some predicate.
</P
><PRE
> filter (> "a") (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
filter (> "x") (fromList [(5,"a"), (3,"b")]) == empty
filter (< "a") (fromList [(5,"a"), (3,"b")]) == empty
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:filterWithKey"
><A NAME="v%3AfilterWithKey"
></A
></A
><B
>filterWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Filter all keys/values that satisfy some predicate.
</P
><PRE
> filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:partition"
><A NAME="v%3Apartition"
></A
></A
><B
>partition</B
> :: (a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Partition the map according to some predicate. The first
map contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also <TT
><A HREF="Data-IntMap.html#v%3Asplit"
>split</A
></TT
>.
</P
><PRE
> partition (> "a") (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:partitionWithKey"
><A NAME="v%3ApartitionWithKey"
></A
></A
><B
>partitionWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Partition the map according to some predicate. The first
map contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also <TT
><A HREF="Data-IntMap.html#v%3Asplit"
>split</A
></TT
>.
</P
><PRE
> partitionWithKey (\ k _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (singleton 5 "a", singleton 3 "b")
partitionWithKey (\ k _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
partitionWithKey (\ k _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:mapMaybe"
><A NAME="v%3AmapMaybe"
></A
></A
><B
>mapMaybe</B
> :: (a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> b) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Map values and collect the <TT
><A HREF="../base/Data-Maybe.html#v%3AJust"
>Just</A
></TT
> results.
</P
><PRE
> let f x = if x == "a" then Just "new a" else Nothing
mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:mapMaybeWithKey"
><A NAME="v%3AmapMaybeWithKey"
></A
></A
><B
>mapMaybeWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> b) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Map keys/values and collect the <TT
><A HREF="../base/Data-Maybe.html#v%3AJust"
>Just</A
></TT
> results.
</P
><PRE
> let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:mapEither"
><A NAME="v%3AmapEither"
></A
></A
><B
>mapEither</B
> :: (a -> <A HREF="../base/Data-Either.html#t%3AEither"
>Either</A
> b c) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> c)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Map values and separate the <TT
><A HREF="../base/Data-Either.html#v%3ALeft"
>Left</A
></TT
> and <TT
><A HREF="../base/Data-Either.html#v%3ARight"
>Right</A
></TT
> results.
</P
><PRE
> let f a = if a < "c" then Left a else Right a
mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
== (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])
mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
== (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:mapEitherWithKey"
><A NAME="v%3AmapEitherWithKey"
></A
></A
><B
>mapEitherWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> <A HREF="../base/Data-Either.html#t%3AEither"
>Either</A
> b c) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> c)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. Map keys/values and separate the <TT
><A HREF="../base/Data-Either.html#v%3ALeft"
>Left</A
></TT
> and <TT
><A HREF="../base/Data-Either.html#v%3ARight"
>Right</A
></TT
> results.
</P
><PRE
> let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
== (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])
mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
== (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:split"
><A NAME="v%3Asplit"
></A
></A
><B
>split</B
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(log n)</EM
>. The expression (<TT
><TT
><A HREF="Data-IntMap.html#v%3Asplit"
>split</A
></TT
> k map</TT
>) is a pair <TT
>(map1,map2)</TT
>
where all keys in <TT
>map1</TT
> are lower than <TT
>k</TT
> and all keys in
<TT
>map2</TT
> larger than <TT
>k</TT
>. Any key equal to <TT
>k</TT
> is found in neither <TT
>map1</TT
> nor <TT
>map2</TT
>.
</P
><PRE
> split 2 (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3,"b"), (5,"a")])
split 3 (fromList [(5,"a"), (3,"b")]) == (empty, singleton 5 "a")
split 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
split 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", empty)
split 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], empty)
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:splitLookup"
><A NAME="v%3AsplitLookup"
></A
></A
><B
>splitLookup</B
> :: <A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (<A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a, <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(log n)</EM
>. Performs a <TT
><A HREF="Data-IntMap.html#v%3Asplit"
>split</A
></TT
> but also returns whether the pivot
key was found in the original map.
</P
><PRE
> splitLookup 2 (fromList [(5,"a"), (3,"b")]) == (empty, Nothing, fromList [(3,"b"), (5,"a")])
splitLookup 3 (fromList [(5,"a"), (3,"b")]) == (empty, Just "b", singleton 5 "a")
splitLookup 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Nothing, singleton 5 "a")
splitLookup 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Just "a", empty)
splitLookup 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], Nothing, empty)
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="18"
><A NAME="18"
>Submap
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:isSubmapOf"
><A NAME="v%3AisSubmapOf"
></A
></A
><B
>isSubmapOf</B
> :: <A HREF="../base/Data-Eq.html#t%3AEq"
>Eq</A
> a => <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n+m)</EM
>. Is this a submap?
Defined as (<TT
><TT
><A HREF="Data-IntMap.html#v%3AisSubmapOf"
>isSubmapOf</A
></TT
> = <TT
><A HREF="Data-IntMap.html#v%3AisSubmapOfBy"
>isSubmapOfBy</A
></TT
> (==)</TT
>).
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:isSubmapOfBy"
><A NAME="v%3AisSubmapOfBy"
></A
></A
><B
>isSubmapOfBy</B
> :: (a -> b -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n+m)</EM
>.
The expression (<TT
><TT
><A HREF="Data-IntMap.html#v%3AisSubmapOfBy"
>isSubmapOfBy</A
></TT
> f m1 m2</TT
>) returns <TT
><A HREF="../ghc-prim/GHC-Bool.html#v%3ATrue"
>True</A
></TT
> if
all keys in <TT
>m1</TT
> are in <TT
>m2</TT
>, and when <TT
>f</TT
> returns <TT
><A HREF="../ghc-prim/GHC-Bool.html#v%3ATrue"
>True</A
></TT
> when
applied to their respective values. For example, the following
expressions are all <TT
><A HREF="../ghc-prim/GHC-Bool.html#v%3ATrue"
>True</A
></TT
>:
</P
><PRE
> isSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
isSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
</PRE
><P
>But the following are all <TT
><A HREF="../ghc-prim/GHC-Bool.html#v%3AFalse"
>False</A
></TT
>:
</P
><PRE
> isSubmapOfBy (==) (fromList [(1,2)]) (fromList [(1,1),(2,2)])
isSubmapOfBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:isProperSubmapOf"
><A NAME="v%3AisProperSubmapOf"
></A
></A
><B
>isProperSubmapOf</B
> :: <A HREF="../base/Data-Eq.html#t%3AEq"
>Eq</A
> a => <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n+m)</EM
>. Is this a proper submap? (ie. a submap but not equal).
Defined as (<TT
><TT
><A HREF="Data-IntMap.html#v%3AisProperSubmapOf"
>isProperSubmapOf</A
></TT
> = <TT
><A HREF="Data-IntMap.html#v%3AisProperSubmapOfBy"
>isProperSubmapOfBy</A
></TT
> (==)</TT
>).
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:isProperSubmapOfBy"
><A NAME="v%3AisProperSubmapOfBy"
></A
></A
><B
>isProperSubmapOfBy</B
> :: (a -> b -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> b -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n+m)</EM
>. Is this a proper submap? (ie. a submap but not equal).
The expression (<TT
><TT
><A HREF="Data-IntMap.html#v%3AisProperSubmapOfBy"
>isProperSubmapOfBy</A
></TT
> f m1 m2</TT
>) returns <TT
><A HREF="../ghc-prim/GHC-Bool.html#v%3ATrue"
>True</A
></TT
> when
<TT
>m1</TT
> and <TT
>m2</TT
> are not equal,
all keys in <TT
>m1</TT
> are in <TT
>m2</TT
>, and when <TT
>f</TT
> returns <TT
><A HREF="../ghc-prim/GHC-Bool.html#v%3ATrue"
>True</A
></TT
> when
applied to their respective values. For example, the following
expressions are all <TT
><A HREF="../ghc-prim/GHC-Bool.html#v%3ATrue"
>True</A
></TT
>:
</P
><PRE
> isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
</PRE
><P
>But the following are all <TT
><A HREF="../ghc-prim/GHC-Bool.html#v%3AFalse"
>False</A
></TT
>:
</P
><PRE
> isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
isProperSubmapOfBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="19"
><A NAME="19"
>Min/Max
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:maxView"
><A NAME="v%3AmaxView"
></A
></A
><B
>maxView</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> (a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Retrieves the maximal key of the map, and the map
stripped of that element, or <TT
><A HREF="../base/Data-Maybe.html#v%3ANothing"
>Nothing</A
></TT
> if passed an empty map.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:minView"
><A NAME="v%3AminView"
></A
></A
><B
>minView</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> (a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Retrieves the minimal key of the map, and the map
stripped of that element, or <TT
><A HREF="../base/Data-Maybe.html#v%3ANothing"
>Nothing</A
></TT
> if passed an empty map.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:findMin"
><A NAME="v%3AfindMin"
></A
></A
><B
>findMin</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. The minimal key of the map.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:findMax"
><A NAME="v%3AfindMax"
></A
></A
><B
>findMax</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. The maximal key of the map.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:deleteMin"
><A NAME="v%3AdeleteMin"
></A
></A
><B
>deleteMin</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Delete the minimal key.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:deleteMax"
><A NAME="v%3AdeleteMax"
></A
></A
><B
>deleteMax</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Delete the maximal key.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:deleteFindMin"
><A NAME="v%3AdeleteFindMin"
></A
></A
><B
>deleteFindMin</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Delete and find the minimal element.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:deleteFindMax"
><A NAME="v%3AdeleteFindMax"
></A
></A
><B
>deleteFindMax</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> (a, <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Delete and find the maximal element.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:updateMin"
><A NAME="v%3AupdateMin"
></A
></A
><B
>updateMin</B
> :: (a -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(log n)</EM
>. Update the value at the minimal key.
</P
><PRE
> updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")]
updateMin (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:updateMax"
><A NAME="v%3AupdateMax"
></A
></A
><B
>updateMax</B
> :: (a -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(log n)</EM
>. Update the value at the maximal key.
</P
><PRE
> updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")]
updateMax (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:updateMinWithKey"
><A NAME="v%3AupdateMinWithKey"
></A
></A
><B
>updateMinWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(log n)</EM
>. Update the value at the minimal key.
</P
><PRE
> updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")]
updateMinWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:updateMaxWithKey"
><A NAME="v%3AupdateMaxWithKey"
></A
></A
><B
>updateMaxWithKey</B
> :: (<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
> -> a -> a) -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(log n)</EM
>. Update the value at the maximal key.
</P
><PRE
> updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")]
updateMaxWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:minViewWithKey"
><A NAME="v%3AminViewWithKey"
></A
></A
><B
>minViewWithKey</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> ((<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a), <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(log n)</EM
>. Retrieves the minimal (key,value) pair of the map, and
the map stripped of that element, or <TT
><A HREF="../base/Data-Maybe.html#v%3ANothing"
>Nothing</A
></TT
> if passed an empty map.
</P
><PRE
> minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
minViewWithKey empty == Nothing
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:maxViewWithKey"
><A NAME="v%3AmaxViewWithKey"
></A
></A
><B
>maxViewWithKey</B
> :: <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> ((<A HREF="Data-IntMap.html#t%3AKey"
>Key</A
>, a), <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(log n)</EM
>. Retrieves the maximal (key,value) pair of the map, and
the map stripped of that element, or <TT
><A HREF="../base/Data-Maybe.html#v%3ANothing"
>Nothing</A
></TT
> if passed an empty map.
</P
><PRE
> maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
maxViewWithKey empty == Nothing
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="20"
><A NAME="20"
>Debugging
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:showTree"
><A NAME="v%3AshowTree"
></A
></A
><B
>showTree</B
> :: <A HREF="../base/Text-Show.html#t%3AShow"
>Show</A
> a => <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Char.html#t%3AString"
>String</A
></TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n)</EM
>. Show the tree that implements the map. The tree is shown
in a compressed, hanging format.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:showTreeWith"
><A NAME="v%3AshowTreeWith"
></A
></A
><B
>showTreeWith</B
> :: <A HREF="../base/Text-Show.html#t%3AShow"
>Show</A
> a => <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
> -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
> -> <A HREF="Data-IntMap.html#t%3AIntMap"
>IntMap</A
> a -> <A HREF="../base/Data-Char.html#t%3AString"
>String</A
></TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n)</EM
>. The expression (<TT
><TT
><A HREF="Data-IntMap.html#v%3AshowTreeWith"
>showTreeWith</A
></TT
> hang wide map</TT
>) shows
the tree that implements the map. If <TT
>hang</TT
> is
<TT
><A HREF="../ghc-prim/GHC-Bool.html#v%3ATrue"
>True</A
></TT
>, a <EM
>hanging</EM
> tree is shown otherwise a rotated tree is shown. If
<TT
>wide</TT
> is <TT
><A HREF="../ghc-prim/GHC-Bool.html#v%3ATrue"
>True</A
></TT
>, an extra wide version is shown.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="botbar"
>Produced by <A HREF="http://www.haskell.org/haddock/"
>Haddock</A
> version 2.4.2</TD
></TR
></TABLE
></BODY
></HTML
>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
1f2b142b9d2ef4849a6f5316fa1c5b12
>
files
>
1570
