<!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.Map</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-Map.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.Map</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" >Indexed </A ></DT ><DT ><A HREF="#20" >Min/Max </A ></DT ><DT ><A HREF="#21" >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 keys to values (dictionaries). </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.Map (Map) import qualified Data.Map as Map </PRE ><P >The implementation of <TT ><A HREF="Data-Map.html#t%3AMap" >Map</A ></TT > is based on <EM >size balanced</EM > binary trees (or trees of <EM >bounded balance</EM >) as described by: </P ><UL ><LI > Stephen Adams, "<EM >Efficient sets: a balancing act</EM >", Journal of Functional Programming 3(4):553-562, October 1993, <A HREF="http://www.swiss.ai.mit.edu/~adams/BB/" >http://www.swiss.ai.mit.edu/~adams/BB/</A >. </LI ><LI > J. Nievergelt and E.M. Reingold, "<EM >Binary search trees of bounded balance</EM >", SIAM journal of computing 2(1), March 1973. </LI ></UL ><P >Note that the implementation is <EM >left-biased</EM > -- the elements of a first argument are always preferred to the second, for example in <TT ><A HREF="Data-Map.html#v%3Aunion" >union</A ></TT > or <TT ><A HREF="Data-Map.html#v%3Ainsert" >insert</A ></TT >. </P ><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 >. </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%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3A%21" >(!)</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> k -> a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3A%5C%5C" >(\\)</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Anull" >null</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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-Map.html#t%3AMap" >Map</A > k 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => a -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Aempty" >empty</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Asingleton" >singleton</A > :: k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Ainsert" >insert</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AinsertWith" >insertWith</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> a -> a) -> k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AinsertWithKey" >insertWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> a -> a) -> k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AinsertLookupWithKey" >insertLookupWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> a -> a) -> k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AinsertWith%27" >insertWith'</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> a -> a) -> k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AinsertWithKey%27" >insertWithKey'</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> a -> a) -> k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Adelete" >delete</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Aadjust" >adjust</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> a) -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AadjustWithKey" >adjustWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> a) -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Aupdate" >update</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AupdateWithKey" >updateWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AupdateLookupWithKey" >updateLookupWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Aalter" >alter</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (<A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Aunion" >union</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AunionWith" >unionWith</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> a -> a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AunionWithKey" >unionWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> a -> a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Aunions" >unions</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => [<A HREF="Data-Map.html#t%3AMap" >Map</A > k a] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AunionsWith" >unionsWith</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> a -> a) -> [<A HREF="Data-Map.html#t%3AMap" >Map</A > k a] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Adifference" >difference</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AdifferenceWith" >differenceWith</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> b -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AdifferenceWithKey" >differenceWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> b -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Aintersection" >intersection</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AintersectionWith" >intersectionWith</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> b -> c) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k c</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AintersectionWithKey" >intersectionWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> b -> c) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k c</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Amap" >map</A > :: (a -> b) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AmapWithKey" >mapWithKey</A > :: (k -> a -> b) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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-Map.html#t%3AMap" >Map</A > k b -> (a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k c)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AmapAccumWithKey" >mapAccumWithKey</A > :: (a -> k -> b -> (a, c)) -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> (a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k c)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AmapKeys" >mapKeys</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k2 => (k1 -> k2) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k1 a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k2 a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AmapKeysWith" >mapKeysWith</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k2 => (a -> a -> a) -> (k1 -> k2) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k1 a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k2 a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AmapKeysMonotonic" >mapKeysMonotonic</A > :: (k1 -> k2) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k1 a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k2 a</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-Map.html#t%3AMap" >Map</A > k a -> b</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AfoldWithKey" >foldWithKey</A > :: (k -> a -> b -> b) -> b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> b</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Aelems" >elems</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> [a]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Akeys" >keys</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> [k]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AkeysSet" >keysSet</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Set.html#t%3ASet" >Set</A > k</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Aassocs" >assocs</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> [(k, a)]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AtoList" >toList</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> [(k, a)]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AfromList" >fromList</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AfromListWith" >fromListWith</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> a -> a) -> [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AfromListWithKey" >fromListWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> a -> a) -> [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AtoAscList" >toAscList</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> [(k, a)]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AfromAscList" >fromAscList</A > :: <A HREF="../base/Data-Eq.html#t%3AEq" >Eq</A > k => [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AfromAscListWith" >fromAscListWith</A > :: <A HREF="../base/Data-Eq.html#t%3AEq" >Eq</A > k => (a -> a -> a) -> [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AfromAscListWithKey" >fromAscListWithKey</A > :: <A HREF="../base/Data-Eq.html#t%3AEq" >Eq</A > k => (k -> a -> a -> a) -> [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AfromDistinctAscList" >fromDistinctAscList</A > :: [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Afilter" >filter</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AfilterWithKey" >filterWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Apartition" >partition</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="Data-Map.html#t%3AMap" >Map</A > k a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3ApartitionWithKey" >partitionWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="Data-Map.html#t%3AMap" >Map</A > k a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AmapMaybe" >mapMaybe</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > b) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AmapMaybeWithKey" >mapMaybeWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > b) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AmapEither" >mapEither</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> <A HREF="../base/Data-Either.html#t%3AEither" >Either</A > b c) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="Data-Map.html#t%3AMap" >Map</A > k b, <A HREF="Data-Map.html#t%3AMap" >Map</A > k c)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AmapEitherWithKey" >mapEitherWithKey</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> <A HREF="../base/Data-Either.html#t%3AEither" >Either</A > b c) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="Data-Map.html#t%3AMap" >Map</A > k b, <A HREF="Data-Map.html#t%3AMap" >Map</A > k c)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Asplit" >split</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="Data-Map.html#t%3AMap" >Map</A > k a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AsplitLookup" >splitLookup</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="Data-Map.html#t%3AMap" >Map</A > k a, <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AisSubmapOf" >isSubmapOf</A > :: (<A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k, <A HREF="../base/Data-Eq.html#t%3AEq" >Eq</A > a) => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> b -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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-Ord.html#t%3AOrd" >Ord</A > k, <A HREF="../base/Data-Eq.html#t%3AEq" >Eq</A > a) => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> b -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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%3AlookupIndex" >lookupIndex</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</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%3AfindIndex" >findIndex</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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%3AelemAt" >elemAt</A > :: <A HREF="../ghc-prim/GHC-Types.html#t%3AInt" >Int</A > -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (k, a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AupdateAt" >updateAt</A > :: (k -> 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-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AdeleteAt" >deleteAt</A > :: <A HREF="../ghc-prim/GHC-Types.html#t%3AInt" >Int</A > -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AfindMin" >findMin</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (k, a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AfindMax" >findMax</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (k, a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AdeleteMin" >deleteMin</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AdeleteMax" >deleteMax</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AdeleteFindMin" >deleteFindMin</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> ((k, a), <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AdeleteFindMax" >deleteFindMax</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> ((k, a), <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AupdateMin" >updateMin</A > :: (a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AupdateMax" >updateMax</A > :: (a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AupdateMinWithKey" >updateMinWithKey</A > :: (k -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AupdateMaxWithKey" >updateMaxWithKey</A > :: (k -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AminView" >minView</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > (a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AmaxView" >maxView</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > (a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AminViewWithKey" >minViewWithKey</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > ((k, a), <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AmaxViewWithKey" >maxViewWithKey</A > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > ((k, a), <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 > k, <A HREF="../base/Text-Show.html#t%3AShow" >Show</A > a) => <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 > :: (k -> a -> <A HREF="../base/Data-Char.html#t%3AString" >String</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-Map.html#t%3AMap" >Map</A > k 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%3Avalid" >valid</A > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</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:Map" ><A NAME="t%3AMap" ></A ></A ><B >Map</B > k a </TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="ndoc" >A Map from keys <TT >k</TT > to values <TT >a</TT >. </TD ></TR ><TR ><TD CLASS="section4" ><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:Map')" ALT="show/hide" > Instances</TD ></TR ><TR ><TD CLASS="body" ><DIV ID="i:Map" STYLE="display:block;" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="decl" ><A HREF="../base/Data-Typeable.html#t%3ATypeable2" >Typeable2</A > <A HREF="Data-Map.html#t%3AMap" >Map</A ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="../base/Control-Monad.html#t%3AFunctor" >Functor</A > (<A HREF="Data-Map.html#t%3AMap" >Map</A > k)</TD ></TR ><TR ><TD CLASS="decl" ><A HREF="../base/Data-Traversable.html#t%3ATraversable" >Traversable</A > (<A HREF="Data-Map.html#t%3AMap" >Map</A > k)</TD ></TR ><TR ><TD CLASS="decl" ><A HREF="../base/Data-Foldable.html#t%3AFoldable" >Foldable</A > (<A HREF="Data-Map.html#t%3AMap" >Map</A > k)</TD ></TR ><TR ><TD CLASS="decl" >(<A HREF="../base/Data-Eq.html#t%3AEq" >Eq</A > k, <A HREF="../base/Data-Eq.html#t%3AEq" >Eq</A > a) => <A HREF="../base/Data-Eq.html#t%3AEq" >Eq</A > (<A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="decl" >(<A HREF="../base/Data-Data.html#t%3AData" >Data</A > k, <A HREF="../base/Data-Data.html#t%3AData" >Data</A > a, <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k) => <A HREF="../base/Data-Data.html#t%3AData" >Data</A > (<A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="decl" >(<A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k, <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > v) => <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > (<A HREF="Data-Map.html#t%3AMap" >Map</A > k v)</TD ></TR ><TR ><TD CLASS="decl" >(<A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k, <A HREF="../base/Text-Read.html#t%3ARead" >Read</A > k, <A HREF="../base/Text-Read.html#t%3ARead" >Read</A > e) => <A HREF="../base/Text-Read.html#t%3ARead" >Read</A > (<A HREF="Data-Map.html#t%3AMap" >Map</A > k e)</TD ></TR ><TR ><TD CLASS="decl" >(<A HREF="../base/Text-Show.html#t%3AShow" >Show</A > k, <A HREF="../base/Text-Show.html#t%3AShow" >Show</A > a) => <A HREF="../base/Text-Show.html#t%3AShow" >Show</A > (<A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="decl" ><A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="../base/Data-Monoid.html#t%3AMonoid" >Monoid</A > (<A HREF="Data-Map.html#t%3AMap" >Map</A > k v)</TD ></TR ></TABLE ></DIV ></TD ></TR ></TABLE ></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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> k -> a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" >Same as <TT ><A HREF="Data-Map.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-Map.html#t%3AMap" >Map</A > k 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.Map.null (empty) == True Data.Map.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-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../ghc-prim/GHC-Types.html#t%3AInt" >Int</A ></TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(1)</EM >. The 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 a member of the map? See also <TT ><A HREF="Data-Map.html#v%3AnotMember" >notMember</A ></TT >. </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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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? See also <TT ><A HREF="Data-Map.html#v%3Amember" >member</A ></TT >. </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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Lookup the value at a key in the map. </P ><P >The function will return the corresponding value as <TT >(<TT ><A HREF="../base/Data-Maybe.html#v%3AJust" >Just</A ></TT > value)</TT >, or <TT ><A HREF="../base/Data-Maybe.html#v%3ANothing" >Nothing</A ></TT > if the key isn't in the map. </P ><P >An example of using <TT >lookup</TT >: </P ><PRE > import Prelude hiding (lookup) import Data.Map employeeDept = fromList([("John","Sales"), ("Bob","IT")]) deptCountry = fromList([("IT","USA"), ("Sales","France")]) countryCurrency = fromList([("USA", "Dollar"), ("France", "Euro")]) employeeCurrency :: String -> Maybe String employeeCurrency name = do dept <- lookup name employeeDept country <- lookup dept deptCountry lookup country countryCurrency main = do putStrLn $ "John's currency: " ++ (show (employeeCurrency "John")) putStrLn $ "Pete's currency: " ++ (show (employeeCurrency "Pete")) </PRE ><P >The output of this program: </P ><PRE > John's currency: Just "Euro" Pete's currency: Nothing </PRE ></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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => a -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. The expression <TT >(<TT ><A HREF="Data-Map.html#v%3AfindWithDefault" >findWithDefault</A ></TT > def k map)</TT > returns the value at key <TT >k</TT > or returns default value <TT >def</TT > when the key is not in 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-Map.html#t%3AMap" >Map</A > k 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 > :: k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(1)</EM >. A map with a single 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Insert a new key and value in the map. If the key is already present in the map, the associated value is replaced with the supplied value. <TT ><A HREF="Data-Map.html#v%3Ainsert" >insert</A ></TT > is equivalent to <TT ><TT ><A HREF="Data-Map.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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> a -> a) -> k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Insert with a function, combining new value and old value. <TT ><TT ><A HREF="Data-Map.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 the pair <TT >(key, 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> a -> a) -> k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Insert with a function, combining key, new value and old value. <TT ><TT ><A HREF="Data-Map.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 the pair <TT >(key,f key new_value old_value)</TT >. Note that the key passed to f is the same key passed to <TT ><A HREF="Data-Map.html#v%3AinsertWithKey" >insertWithKey</A ></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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> a -> a) -> k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Combines insert operation with old value retrieval. The expression (<TT ><TT ><A HREF="Data-Map.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-Map.html#v%3Alookup" >lookup</A ></TT > k map</TT >) and the second element equal to (<TT ><TT ><A HREF="Data-Map.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="decl" ><A NAME="v:insertWith'" ><A NAME="v%3AinsertWith%27" ></A ></A ><B >insertWith'</B > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> a -> a) -> k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" >Same as <TT ><A HREF="Data-Map.html#v%3AinsertWith" >insertWith</A ></TT >, but the combining function is applied strictly. </TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:insertWithKey'" ><A NAME="v%3AinsertWithKey%27" ></A ></A ><B >insertWithKey'</B > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> a -> a) -> k -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" >Same as <TT ><A HREF="Data-Map.html#v%3AinsertWithKey" >insertWithKey</A ></TT >, but the combining function is applied strictly. </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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> a) -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Update a value at a specific key with the result of the provided function. 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> a) -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. The expression (<TT ><TT ><A HREF="Data-Map.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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. The expression (<TT ><TT ><A HREF="Data-Map.html#v%3AupdateWithKey" >updateWithKey</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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Lookup and update. See also <TT ><A HREF="Data-Map.html#v%3AupdateWithKey" >updateWithKey</A ></TT >. The function returns changed value, if it is updated. 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 "5:new 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-Ord.html#t%3AOrd" >Ord</A > k => (<A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. The expression (<TT ><TT ><A HREF="Data-Map.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-Map.html#v%3Aalter" >alter</A ></TT > can be used to insert, delete, or update a value in a <TT ><A HREF="Data-Map.html#t%3AMap" >Map</A ></TT >. In short : <TT ><TT ><A HREF="Data-Map.html#v%3Alookup" >lookup</A ></TT > k (<TT ><A HREF="Data-Map.html#v%3Aalter" >alter</A ></TT > f k m) = f (<TT ><A HREF="Data-Map.html#v%3Alookup" >lookup</A ></TT > k m)</TT >. </P ><PRE > let f _ = Nothing alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" let f _ = Just "c" alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")] alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")] </PRE ></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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n+m)</EM >. The expression (<TT ><TT ><A HREF="Data-Map.html#v%3Aunion" >union</A ></TT > t1 t2</TT >) takes the left-biased union of <TT >t1</TT > and <TT >t2</TT >. It prefers <TT >t1</TT > when duplicate keys are encountered, i.e. (<TT ><TT ><A HREF="Data-Map.html#v%3Aunion" >union</A ></TT > == <TT ><A HREF="Data-Map.html#v%3AunionWith" >unionWith</A ></TT > <TT ><A HREF="../base/Prelude.html#v%3Aconst" >const</A ></TT ></TT >). The implementation uses the efficient <EM >hedge-union</EM > algorithm. Hedge-union is more efficient on (bigset `<TT ><A HREF="Data-Map.html#v%3Aunion" >union</A ></TT >` smallset). </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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> a -> a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n+m)</EM >. Union with a combining function. The implementation uses the efficient <EM >hedge-union</EM > algorithm. </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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> a -> a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n+m)</EM >. Union with a combining function. The implementation uses the efficient <EM >hedge-union</EM > algorithm. Hedge-union is more efficient on (bigset `<TT ><A HREF="Data-Map.html#v%3Aunion" >union</A ></TT >` smallset). </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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => [<A HREF="Data-Map.html#t%3AMap" >Map</A > k a] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P >The union of a list of maps: (<TT ><TT ><A HREF="Data-Map.html#v%3Aunions" >unions</A ></TT > == Prelude.foldl <TT ><A HREF="Data-Map.html#v%3Aunion" >union</A ></TT > <TT ><A HREF="Data-Map.html#v%3Aempty" >empty</A ></TT ></TT >). </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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> a -> a) -> [<A HREF="Data-Map.html#t%3AMap" >Map</A > k a] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P >The union of a list of maps, with a combining operation: (<TT ><TT ><A HREF="Data-Map.html#v%3AunionsWith" >unionsWith</A ></TT > f == Prelude.foldl (<TT ><A HREF="Data-Map.html#v%3AunionWith" >unionWith</A ></TT > f) <TT ><A HREF="Data-Map.html#v%3Aempty" >empty</A ></TT ></TT >). </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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n+m)</EM >. Difference of two maps. Return elements of the first map not existing in the second map. The implementation uses an efficient <EM >hedge</EM > algorithm comparable with <EM >hedge-union</EM >. </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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> b -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 values of these keys. 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 >. The implementation uses an efficient <EM >hedge</EM > algorithm comparable with <EM >hedge-union</EM >. </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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> b -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 >. The implementation uses an efficient <EM >hedge</EM > algorithm comparable with <EM >hedge-union</EM >. </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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n+m)</EM >. Intersection of two maps. Return data in the first map for the keys existing in both maps. (<TT ><TT ><A HREF="Data-Map.html#v%3Aintersection" >intersection</A ></TT > m1 m2 == <TT ><A HREF="Data-Map.html#v%3AintersectionWith" >intersectionWith</A ></TT > <TT ><A HREF="../base/Prelude.html#v%3Aconst" >const</A ></TT > m1 m2</TT >). </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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> b -> c) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k c</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n+m)</EM >. 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> b -> c) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k c</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n+m)</EM >. Intersection with a combining function. Intersection is more efficient on (bigset `<TT ><A HREF="Data-Map.html#v%3Aintersection" >intersection</A ></TT >` smallset). </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-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 > :: (k -> a -> b) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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-Map.html#t%3AMap" >Map</A > k b -> (a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k c)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. The function <TT ><A HREF="Data-Map.html#v%3AmapAccum" >mapAccum</A ></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 -> k -> b -> (a, c)) -> a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k b -> (a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k c)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. The function <TT ><A HREF="Data-Map.html#v%3AmapAccumWithKey" >mapAccumWithKey</A ></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="decl" ><A NAME="v:mapKeys" ><A NAME="v%3AmapKeys" ></A ></A ><B >mapKeys</B > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k2 => (k1 -> k2) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k1 a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k2 a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n*log n)</EM >. <TT ><TT ><A HREF="Data-Map.html#v%3AmapKeys" >mapKeys</A ></TT > f s</TT > is the map obtained by applying <TT >f</TT > to each key of <TT >s</TT >. </P ><P >The size of the result may be smaller if <TT >f</TT > maps two or more distinct keys to the same new key. In this case the value at the smallest of these keys is retained. </P ><PRE > mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")] mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "c" mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "c" </PRE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:mapKeysWith" ><A NAME="v%3AmapKeysWith" ></A ></A ><B >mapKeysWith</B > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k2 => (a -> a -> a) -> (k1 -> k2) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k1 a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k2 a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n*log n)</EM >. <TT ><TT ><A HREF="Data-Map.html#v%3AmapKeysWith" >mapKeysWith</A ></TT > c f s</TT > is the map obtained by applying <TT >f</TT > to each key of <TT >s</TT >. </P ><P >The size of the result may be smaller if <TT >f</TT > maps two or more distinct keys to the same new key. In this case the associated values will be combined using <TT >c</TT >. </P ><PRE > mapKeysWith (++) (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "cdab" mapKeysWith (++) (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "cdab" </PRE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:mapKeysMonotonic" ><A NAME="v%3AmapKeysMonotonic" ></A ></A ><B >mapKeysMonotonic</B > :: (k1 -> k2) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k1 a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k2 a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. <TT ><TT ><A HREF="Data-Map.html#v%3AmapKeysMonotonic" >mapKeysMonotonic</A ></TT > f s == <TT ><A HREF="Data-Map.html#v%3AmapKeys" >mapKeys</A ></TT > f s</TT >, but works only when <TT >f</TT > is strictly monotonic. That is, for any values <TT >x</TT > and <TT >y</TT >, if <TT >x</TT > < <TT >y</TT > then <TT >f x</TT > < <TT >f y</TT >. <EM >The precondition is not checked.</EM > Semi-formally, we have: </P ><PRE > and [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapKeysMonotonic f s == mapKeys f s where ls = keys s </PRE ><P >This means that <TT >f</TT > maps distinct original keys to distinct resulting keys. This function has better performance than <TT ><A HREF="Data-Map.html#v%3AmapKeys" >mapKeys</A ></TT >. </P ><PRE > mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")] valid (mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")])) == True valid (mapKeysMonotonic (\ _ -> 1) (fromList [(5,"a"), (3,"b")])) == False </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-Map.html#t%3AMap" >Map</A > k 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-Map.html#v%3Afold" >fold</A ></TT > f z == Prelude.foldr f z . <TT ><A HREF="Data-Map.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 > :: (k -> a -> b -> b) -> b -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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-Map.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-Map.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-Map.html#t%3AMap" >Map</A > k 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-Map.html#t%3AMap" >Map</A > k a -> [k]</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-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Set.html#t%3ASet" >Set</A > k</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. The set of all keys of the map. </P ><PRE > keysSet (fromList [(5,"a"), (3,"b")]) == Data.Set.fromList [3,5] keysSet empty == Data.Set.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-Map.html#t%3AMap" >Map</A > k a -> [(k, 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-Map.html#t%3AMap" >Map</A > k a -> [(k, a)]</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. Convert 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n*log n)</EM >. Build a map from a list of key/value pairs. See also <TT ><A HREF="Data-Map.html#v%3AfromAscList" >fromAscList</A ></TT >. If the list contains more than one value for the same key, the last value for the key is retained. </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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> a -> a) -> [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n*log n)</EM >. Build a map from a list of key/value pairs with a combining function. See also <TT ><A HREF="Data-Map.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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> a -> a) -> [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n*log n)</EM >. Build a map from a list of key/value pairs with a combining function. See also <TT ><A HREF="Data-Map.html#v%3AfromAscListWithKey" >fromAscListWithKey</A ></TT >. </P ><PRE > let f k a1 a2 = (show k) ++ a1 ++ a2 fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")] fromListWithKey f [] == 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-Map.html#t%3AMap" >Map</A > k a -> [(k, a)]</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. Convert to an ascending list. </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="../base/Data-Eq.html#t%3AEq" >Eq</A > k => [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. Build a map from an ascending list in linear time. <EM >The precondition (input list is ascending) is not checked.</EM > </P ><PRE > fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")] fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")] valid (fromAscList [(3,"b"), (5,"a"), (5,"b")]) == True valid (fromAscList [(5,"a"), (3,"b"), (5,"b")]) == False </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 HREF="../base/Data-Eq.html#t%3AEq" >Eq</A > k => (a -> a -> a) -> [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. Build a map from an ascending list in linear time with a combining function for equal keys. <EM >The precondition (input list is ascending) is not checked.</EM > </P ><PRE > fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")] valid (fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")]) == True valid (fromAscListWith (++) [(5,"a"), (3,"b"), (5,"b")]) == False </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="../base/Data-Eq.html#t%3AEq" >Eq</A > k => (k -> a -> a -> a) -> [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. Build a map from an ascending list in linear time with a combining function for equal keys. <EM >The precondition (input list is ascending) is not checked.</EM > </P ><PRE > let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2 fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")] == fromList [(3, "b"), (5, "5:b5:ba")] valid (fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")]) == True valid (fromAscListWithKey f [(5,"a"), (3,"b"), (5,"b"), (5,"b")]) == False </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 > :: [(k, a)] -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. Build a map from an ascending list of distinct elements in linear time. <EM >The precondition is not checked.</EM > </P ><PRE > fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")] valid (fromDistinctAscList [(3,"b"), (5,"a")]) == True valid (fromDistinctAscList [(3,"b"), (5,"a"), (5,"b")]) == False </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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. Filter all values that satisfy the 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. Filter all keys/values that satisfy the 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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="Data-Map.html#t%3AMap" >Map</A > k a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. Partition the map according to a 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-Map.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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="Data-Map.html#t%3AMap" >Map</A > k a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. Partition the map according to a 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-Map.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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > b) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > b) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> <A HREF="../base/Data-Either.html#t%3AEither" >Either</A > b c) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="Data-Map.html#t%3AMap" >Map</A > k b, <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (k -> a -> <A HREF="../base/Data-Either.html#t%3AEither" >Either</A > b c) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="Data-Map.html#t%3AMap" >Map</A > k b, <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="Data-Map.html#t%3AMap" >Map</A > k a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. The expression (<TT ><TT ><A HREF="Data-Map.html#v%3Asplit" >split</A ></TT > k map</TT >) is a pair <TT >(map1,map2)</TT > where the keys in <TT >map1</TT > are smaller than <TT >k</TT > and the 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="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (<A HREF="Data-Map.html#t%3AMap" >Map</A > k a, <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. The expression (<TT ><TT ><A HREF="Data-Map.html#v%3AsplitLookup" >splitLookup</A ></TT > k map</TT >) splits a map just like <TT ><A HREF="Data-Map.html#v%3Asplit" >split</A ></TT > but also returns <TT ><TT ><A HREF="Data-Map.html#v%3Alookup" >lookup</A ></TT > k map</TT >. </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-Ord.html#t%3AOrd" >Ord</A > k, <A HREF="../base/Data-Eq.html#t%3AEq" >Eq</A > a) => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A ></TD ></TR ><TR ><TD CLASS="doc" ><EM >O(n+m)</EM >. This function is defined as (<TT ><TT ><A HREF="Data-Map.html#v%3AisSubmapOf" >isSubmapOf</A ></TT > = <TT ><A HREF="Data-Map.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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> b -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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-Map.html#v%3AisSubmapOfBy" >isSubmapOfBy</A ></TT > f t1 t2</TT >) returns <TT ><A HREF="../ghc-prim/GHC-Bool.html#v%3ATrue" >True</A ></TT > if all keys in <TT >t1</TT > are in tree <TT >t2</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 [('a',1)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',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 [('a',2)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (<) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',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-Ord.html#t%3AOrd" >Ord</A > k, <A HREF="../base/Data-Eq.html#t%3AEq" >Eq</A > a) => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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-Map.html#v%3AisProperSubmapOf" >isProperSubmapOf</A ></TT > = <TT ><A HREF="Data-Map.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 HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => (a -> b -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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-Map.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" >Indexed </A ></A ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:lookupIndex" ><A NAME="v%3AlookupIndex" ></A ></A ><B >lookupIndex</B > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > <A HREF="../ghc-prim/GHC-Types.html#t%3AInt" >Int</A ></TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Lookup the <EM >index</EM > of a key. The index is a number from <EM >0</EM > up to, but not including, the <TT ><A HREF="Data-Map.html#v%3Asize" >size</A ></TT > of the map. </P ><PRE > isJust (lookupIndex 2 (fromList [(5,"a"), (3,"b")])) == False fromJust (lookupIndex 3 (fromList [(5,"a"), (3,"b")])) == 0 fromJust (lookupIndex 5 (fromList [(5,"a"), (3,"b")])) == 1 isJust (lookupIndex 6 (fromList [(5,"a"), (3,"b")])) == False </PRE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:findIndex" ><A NAME="v%3AfindIndex" ></A ></A ><B >findIndex</B > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => k -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../ghc-prim/GHC-Types.html#t%3AInt" >Int</A ></TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Return the <EM >index</EM > of a key. The index is a number from <EM >0</EM > up to, but not including, the <TT ><A HREF="Data-Map.html#v%3Asize" >size</A ></TT > of the map. Calls <TT ><A HREF="../base/Prelude.html#v%3Aerror" >error</A ></TT > when the key is not a <TT ><A HREF="Data-Map.html#v%3Amember" >member</A ></TT > of the map. </P ><PRE > findIndex 2 (fromList [(5,"a"), (3,"b")]) Error: element is not in the map findIndex 3 (fromList [(5,"a"), (3,"b")]) == 0 findIndex 5 (fromList [(5,"a"), (3,"b")]) == 1 findIndex 6 (fromList [(5,"a"), (3,"b")]) Error: element is not in the map </PRE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:elemAt" ><A NAME="v%3AelemAt" ></A ></A ><B >elemAt</B > :: <A HREF="../ghc-prim/GHC-Types.html#t%3AInt" >Int</A > -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> (k, a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Retrieve an element by <EM >index</EM >. Calls <TT ><A HREF="../base/Prelude.html#v%3Aerror" >error</A ></TT > when an invalid index is used. </P ><PRE > elemAt 0 (fromList [(5,"a"), (3,"b")]) == (3,"b") elemAt 1 (fromList [(5,"a"), (3,"b")]) == (5, "a") elemAt 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range </PRE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:updateAt" ><A NAME="v%3AupdateAt" ></A ></A ><B >updateAt</B > :: (k -> 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-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Update the element at <EM >index</EM >. Calls <TT ><A HREF="../base/Prelude.html#v%3Aerror" >error</A ></TT > when an invalid index is used. </P ><PRE > updateAt (\ _ _ -> Just "x") 0 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "x"), (5, "a")] updateAt (\ _ _ -> Just "x") 1 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "x")] updateAt (\ _ _ -> Just "x") 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range updateAt (\ _ _ -> Just "x") (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range updateAt (\_ _ -> Nothing) 0 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" updateAt (\_ _ -> Nothing) 1 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" updateAt (\_ _ -> Nothing) 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range updateAt (\_ _ -> Nothing) (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range </PRE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:deleteAt" ><A NAME="v%3AdeleteAt" ></A ></A ><B >deleteAt</B > :: <A HREF="../ghc-prim/GHC-Types.html#t%3AInt" >Int</A > -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Delete the element at <EM >index</EM >. Defined as (<TT ><TT ><A HREF="Data-Map.html#v%3AdeleteAt" >deleteAt</A ></TT > i map = <TT ><A HREF="Data-Map.html#v%3AupdateAt" >updateAt</A ></TT > (k x -> <TT ><A HREF="../base/Data-Maybe.html#v%3ANothing" >Nothing</A ></TT >) i map</TT >). </P ><PRE > deleteAt 0 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" deleteAt 1 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" deleteAt 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range deleteAt (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range </PRE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" ><A NAME="20" ><A NAME="20" >Min/Max </A ></A ></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-Map.html#t%3AMap" >Map</A > k a -> (k, a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. The minimal key of the map. Calls <TT ><A HREF="../base/Prelude.html#v%3Aerror" >error</A ></TT > is the map is empty. </P ><PRE > findMin (fromList [(5,"a"), (3,"b")]) == (3,"b") findMin empty Error: empty map has no minimal element </PRE ></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-Map.html#t%3AMap" >Map</A > k a -> (k, a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. The maximal key of the map. Calls <TT ><A HREF="../base/Prelude.html#v%3Aerror" >error</A ></TT > is the map is empty. </P ><PRE > findMax (fromList [(5,"a"), (3,"b")]) == (5,"a") findMax empty Error: empty map has no maximal element </PRE ></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-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Delete the minimal key. Returns an empty map if the map is empty. </P ><PRE > deleteMin (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(5,"a"), (7,"c")] deleteMin empty == empty </PRE ></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-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Delete the maximal key. Returns an empty map if the map is empty. </P ><PRE > deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")] deleteMax empty == empty </PRE ></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-Map.html#t%3AMap" >Map</A > k a -> ((k, a), <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Delete and find the minimal element. </P ><PRE > deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")]) deleteFindMin Error: can not return the minimal element of an empty map </PRE ></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-Map.html#t%3AMap" >Map</A > k a -> ((k, a), <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Delete and find the maximal element. </P ><PRE > deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")]) deleteFindMax empty Error: can not return the maximal element of an empty map </PRE ></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 HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 > :: (k -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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 > :: (k -> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > a) -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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:minView" ><A NAME="v%3AminView" ></A ></A ><B >minView</B > :: <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > (a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Retrieves the value associated with 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. </P ><PRE > minView (fromList [(5,"a"), (3,"b")]) == Just ("b", singleton 5 "a") minView empty == Nothing </PRE ></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-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > (a, <A HREF="Data-Map.html#t%3AMap" >Map</A > k a)</TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(log n)</EM >. Retrieves the value associated with 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 </P ><PRE > maxView (fromList [(5,"a"), (3,"b")]) == Just ("a", singleton 3 "b") maxView empty == Nothing </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-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > ((k, a), <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe" >Maybe</A > ((k, a), <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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="21" ><A NAME="21" >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 > k, <A HREF="../base/Text-Show.html#t%3AShow" >Show</A > a) => <A HREF="Data-Map.html#t%3AMap" >Map</A > k 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. See <TT ><A HREF="Data-Map.html#v%3AshowTreeWith" >showTreeWith</A ></TT >. </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 > :: (k -> a -> <A HREF="../base/Data-Char.html#t%3AString" >String</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-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../base/Data-Char.html#t%3AString" >String</A ></TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. The expression (<TT ><TT ><A HREF="Data-Map.html#v%3AshowTreeWith" >showTreeWith</A ></TT > showelem hang wide map</TT >) shows the tree that implements the map. Elements are shown using the <TT >showElem</TT > function. 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. </P ><PRE > Map> let t = fromDistinctAscList [(x,()) | x <- [1..5]] Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True False t (4,()) +--(2,()) | +--(1,()) | +--(3,()) +--(5,()) Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True True t (4,()) | +--(2,()) | | | +--(1,()) | | | +--(3,()) | +--(5,()) Map> putStrLn $ showTreeWith (\k x -> show (k,x)) False True t +--(5,()) | (4,()) | | +--(3,()) | | +--(2,()) | +--(1,()) </PRE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:valid" ><A NAME="v%3Avalid" ></A ></A ><B >valid</B > :: <A HREF="../base/Data-Ord.html#t%3AOrd" >Ord</A > k => <A HREF="Data-Map.html#t%3AMap" >Map</A > k a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool" >Bool</A ></TD ></TR ><TR ><TD CLASS="doc" ><P ><EM >O(n)</EM >. Test if the internal map structure is valid. </P ><PRE > valid (fromAscList [(3,"b"), (5,"a")]) == True valid (fromAscList [(5,"a"), (3,"b")]) == False </PRE ></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 >