<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Data.Map</title><link href="ocean.css" rel="stylesheet" type="text/css" title="Ocean" /><script src="haddock-util.js" type="text/javascript"></script><script type="text/javascript">//<![CDATA[
window.onload = function () {pageLoad();setSynopsis("mini_Data-Map.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">containers-0.4.2.1: Assorted concrete container types</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Portability</th><td>portable</td></tr><tr><th>Stability</th><td>provisional</td></tr><tr><th>Maintainer</th><td>libraries@haskell.org</td></tr><tr><th>Safe Haskell</th><td>Safe</td></tr></table><p class="caption">Data.Map</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">Map type
</a></li><li><a href="#g:2">Operators
</a></li><li><a href="#g:3">Query
</a></li><li><a href="#g:4">Construction
</a><ul><li><a href="#g:5">Insertion
</a></li><li><a href="#g:6">Delete/Update
</a></li></ul></li><li><a href="#g:7">Combine
</a><ul><li><a href="#g:8">Union
</a></li><li><a href="#g:9">Difference
</a></li><li><a href="#g:10">Intersection
</a></li></ul></li><li><a href="#g:11">Traversal
</a><ul><li><a href="#g:12">Map
</a></li></ul></li><li><a href="#g:13">Folds
</a><ul><li><a href="#g:14">Strict folds
</a></li><li><a href="#g:15">Legacy folds
</a></li></ul></li><li><a href="#g:16">Conversion
</a><ul><li><a href="#g:17">Lists
</a></li><li><a href="#g:18">Ordered lists
</a></li></ul></li><li><a href="#g:19">Filter
</a></li><li><a href="#g:20">Submap
</a></li><li><a href="#g:21">Indexed
</a></li><li><a href="#g:22">Min/Max
</a></li><li><a href="#g:23">Debugging
</a></li></ul></div><div id="description"><p class="caption">Description</p><div 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="../base-4.5.1.0/Prelude.html">Prelude</a> names, this module is usually imported <code>qualified</code>, e.g.
</p><pre> import Data.Map (Map)
import qualified Data.Map as Map
</pre><p>The implementation of <code><a href="Data-Map.html#t:Map">Map</a></code> 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
<code><a href="Data-Map.html#v:union">union</a></code> or <code><a href="Data-Map.html#v:insert">insert</a></code>.
</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></div></div><div id="synopsis"><p id="control.syn" class="caption expander" onclick="toggleSection('syn')">Synopsis</p><ul id="section.syn" class="hide" onclick="toggleSection('syn')"><li class="src short"><span class="keyword">data</span> <a href="#t:Map">Map</a> k a</li><li class="src short"><a href="#v:-33-">(!)</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="Data-Map.html#t:Map">Map</a> k a -> k -> a</li><li class="src short"><a href="#v:-92--92-">(\\)</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:size">size</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:member">member</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:notMember">notMember</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:lookup">lookup</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a</li><li class="src short"><a href="#v:findWithDefault">findWithDefault</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => a -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> a</li><li class="src short"><a href="#v:empty">empty</a> :: <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:singleton">singleton</a> :: k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:insert">insert</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:insertWith">insertWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> a -> a) -> k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:insertWith-39-">insertWith'</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> a -> a) -> k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:insertWithKey">insertWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a -> a) -> k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:insertWithKey-39-">insertWithKey'</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a -> a) -> k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:insertLookupWithKey">insertLookupWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a -> a) -> k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a, <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:insertLookupWithKey-39-">insertLookupWithKey'</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a -> a) -> k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a, <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:delete">delete</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:adjust">adjust</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> a) -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:adjustWithKey">adjustWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a) -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:update">update</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:updateWithKey">updateWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:updateLookupWithKey">updateLookupWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a, <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:alter">alter</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (<a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:union">union</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:unionWith">unionWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> a -> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:unionWithKey">unionWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a -> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:unions">unions</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => [<a href="Data-Map.html#t:Map">Map</a> k a] -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:unionsWith">unionsWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> a -> a) -> [<a href="Data-Map.html#t:Map">Map</a> k a] -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:difference">difference</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:differenceWith">differenceWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> b -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:differenceWithKey">differenceWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> b -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:intersection">intersection</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:intersectionWith">intersectionWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> b -> c) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k c</li><li class="src short"><a href="#v:intersectionWithKey">intersectionWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> b -> c) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k c</li><li class="src short"><a href="#v:map">map</a> :: (a -> b) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b</li><li class="src short"><a href="#v:mapWithKey">mapWithKey</a> :: (k -> a -> b) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b</li><li class="src short"><a href="#v:mapAccum">mapAccum</a> :: (a -> b -> (a, c)) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> (a, <a href="Data-Map.html#t:Map">Map</a> k c)</li><li class="src short"><a href="#v:mapAccumWithKey">mapAccumWithKey</a> :: (a -> k -> b -> (a, c)) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> (a, <a href="Data-Map.html#t:Map">Map</a> k c)</li><li class="src short"><a href="#v:mapAccumRWithKey">mapAccumRWithKey</a> :: (a -> k -> b -> (a, c)) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> (a, <a href="Data-Map.html#t:Map">Map</a> k c)</li><li class="src short"><a href="#v:mapKeys">mapKeys</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k2 => (k1 -> k2) -> <a href="Data-Map.html#t:Map">Map</a> k1 a -> <a href="Data-Map.html#t:Map">Map</a> k2 a</li><li class="src short"><a href="#v:mapKeysWith">mapKeysWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k2 => (a -> a -> a) -> (k1 -> k2) -> <a href="Data-Map.html#t:Map">Map</a> k1 a -> <a href="Data-Map.html#t:Map">Map</a> k2 a</li><li class="src short"><a href="#v:mapKeysMonotonic">mapKeysMonotonic</a> :: (k1 -> k2) -> <a href="Data-Map.html#t:Map">Map</a> k1 a -> <a href="Data-Map.html#t:Map">Map</a> k2 a</li><li class="src short"><a href="#v:foldr">foldr</a> :: (a -> b -> b) -> b -> <a href="Data-Map.html#t:Map">Map</a> k a -> b</li><li class="src short"><a href="#v:foldl">foldl</a> :: (a -> b -> a) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> a</li><li class="src short"><a href="#v:foldrWithKey">foldrWithKey</a> :: (k -> a -> b -> b) -> b -> <a href="Data-Map.html#t:Map">Map</a> k a -> b</li><li class="src short"><a href="#v:foldlWithKey">foldlWithKey</a> :: (a -> k -> b -> a) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> a</li><li class="src short"><a href="#v:foldr-39-">foldr'</a> :: (a -> b -> b) -> b -> <a href="Data-Map.html#t:Map">Map</a> k a -> b</li><li class="src short"><a href="#v:foldl-39-">foldl'</a> :: (a -> b -> a) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> a</li><li class="src short"><a href="#v:foldrWithKey-39-">foldrWithKey'</a> :: (k -> a -> b -> b) -> b -> <a href="Data-Map.html#t:Map">Map</a> k a -> b</li><li class="src short"><a href="#v:foldlWithKey-39-">foldlWithKey'</a> :: (a -> k -> b -> a) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> a</li><li class="src short"><a href="#v:fold">fold</a> :: (a -> b -> b) -> b -> <a href="Data-Map.html#t:Map">Map</a> k a -> b</li><li class="src short"><a href="#v:foldWithKey">foldWithKey</a> :: (k -> a -> b -> b) -> b -> <a href="Data-Map.html#t:Map">Map</a> k a -> b</li><li class="src short"><a href="#v:elems">elems</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> [a]</li><li class="src short"><a href="#v:keys">keys</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> [k]</li><li class="src short"><a href="#v:keysSet">keysSet</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Set.html#t:Set">Set</a> k</li><li class="src short"><a href="#v:assocs">assocs</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> [(k, a)]</li><li class="src short"><a href="#v:toList">toList</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> [(k, a)]</li><li class="src short"><a href="#v:fromList">fromList</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:fromListWith">fromListWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> a -> a) -> [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:fromListWithKey">fromListWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a -> a) -> [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:toAscList">toAscList</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> [(k, a)]</li><li class="src short"><a href="#v:toDescList">toDescList</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> [(k, a)]</li><li class="src short"><a href="#v:fromAscList">fromAscList</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> k => [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:fromAscListWith">fromAscListWith</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> k => (a -> a -> a) -> [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:fromAscListWithKey">fromAscListWithKey</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> k => (k -> a -> a -> a) -> [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:fromDistinctAscList">fromDistinctAscList</a> :: [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:filter">filter</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:filterWithKey">filterWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:partition">partition</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="Data-Map.html#t:Map">Map</a> k a, <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:partitionWithKey">partitionWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="Data-Map.html#t:Map">Map</a> k a, <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:mapMaybe">mapMaybe</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> b) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b</li><li class="src short"><a href="#v:mapMaybeWithKey">mapMaybeWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> b) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b</li><li class="src short"><a href="#v:mapEither">mapEither</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> <a href="../base-4.5.1.0/Data-Either.html#t:Either">Either</a> b c) -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="Data-Map.html#t:Map">Map</a> k b, <a href="Data-Map.html#t:Map">Map</a> k c)</li><li class="src short"><a href="#v:mapEitherWithKey">mapEitherWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> <a href="../base-4.5.1.0/Data-Either.html#t:Either">Either</a> b c) -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="Data-Map.html#t:Map">Map</a> k b, <a href="Data-Map.html#t:Map">Map</a> k c)</li><li class="src short"><a href="#v:split">split</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="Data-Map.html#t:Map">Map</a> k a, <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:splitLookup">splitLookup</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="Data-Map.html#t:Map">Map</a> k a, <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a, <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:isSubmapOf">isSubmapOf</a> :: (<a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a) => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:isSubmapOfBy">isSubmapOfBy</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> b -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:isProperSubmapOf">isProperSubmapOf</a> :: (<a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a) => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:isProperSubmapOfBy">isProperSubmapOfBy</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> b -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:lookupIndex">lookupIndex</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:findIndex">findIndex</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:elemAt">elemAt</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Map.html#t:Map">Map</a> k a -> (k, a)</li><li class="src short"><a href="#v:updateAt">updateAt</a> :: (k -> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:deleteAt">deleteAt</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:findMin">findMin</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> (k, a)</li><li class="src short"><a href="#v:findMax">findMax</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> (k, a)</li><li class="src short"><a href="#v:deleteMin">deleteMin</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:deleteMax">deleteMax</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:deleteFindMin">deleteFindMin</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> ((k, a), <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:deleteFindMax">deleteFindMax</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> ((k, a), <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:updateMin">updateMin</a> :: (a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:updateMax">updateMax</a> :: (a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:updateMinWithKey">updateMinWithKey</a> :: (k -> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:updateMaxWithKey">updateMaxWithKey</a> :: (k -> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</li><li class="src short"><a href="#v:minView">minView</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (a, <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:maxView">maxView</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (a, <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:minViewWithKey">minViewWithKey</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> ((k, a), <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:maxViewWithKey">maxViewWithKey</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> ((k, a), <a href="Data-Map.html#t:Map">Map</a> k a)</li><li class="src short"><a href="#v:showTree">showTree</a> :: (<a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> k, <a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> a) => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-String.html#t:String">String</a></li><li class="src short"><a href="#v:showTreeWith">showTreeWith</a> :: (k -> a -> <a href="../base-4.5.1.0/Data-String.html#t:String">String</a>) -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a> -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-String.html#t:String">String</a></li><li class="src short"><a href="#v:valid">valid</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li></ul></div><div id="interface"><h1 id="g:1">Map type
</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Map" class="def">Map</a> k a </p><div class="doc"><p>A Map from keys <code>k</code> to values <code>a</code>.
</p></div><div class="subs instances"><p id="control.i:Map" class="caption collapser" onclick="toggleSection('i:Map')">Instances</p><div id="section.i:Map" class="show"><table><tr><td class="src"><a href="../base-4.5.1.0/Data-Typeable-Internal.html#t:Typeable2">Typeable2</a> <a href="Data-Map.html#t:Map">Map</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Control-Monad.html#t:Functor">Functor</a> (<a href="Data-Map.html#t:Map">Map</a> k)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Foldable.html#t:Foldable">Foldable</a> (<a href="Data-Map.html#t:Map">Map</a> k)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Traversable.html#t:Traversable">Traversable</a> (<a href="Data-Map.html#t:Map">Map</a> k)</td><td class="doc empty"> </td></tr><tr><td class="src">(<a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> k, <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a) => <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> (<a href="Data-Map.html#t:Map">Map</a> k a)</td><td class="doc empty"> </td></tr><tr><td class="src">(<a href="../base-4.5.1.0/Data-Data.html#t:Data">Data</a> k, <a href="../base-4.5.1.0/Data-Data.html#t:Data">Data</a> a, <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k) => <a href="../base-4.5.1.0/Data-Data.html#t:Data">Data</a> (<a href="Data-Map.html#t:Map">Map</a> k a)</td><td class="doc empty"> </td></tr><tr><td class="src">(<a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> v) => <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> (<a href="Data-Map.html#t:Map">Map</a> k v)</td><td class="doc empty"> </td></tr><tr><td class="src">(<a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="../base-4.5.1.0/Text-Read.html#t:Read">Read</a> k, <a href="../base-4.5.1.0/Text-Read.html#t:Read">Read</a> e) => <a href="../base-4.5.1.0/Text-Read.html#t:Read">Read</a> (<a href="Data-Map.html#t:Map">Map</a> k e)</td><td class="doc empty"> </td></tr><tr><td class="src">(<a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> k, <a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> a) => <a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> (<a href="Data-Map.html#t:Map">Map</a> k a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="../base-4.5.1.0/Data-Monoid.html#t:Monoid">Monoid</a> (<a href="Data-Map.html#t:Map">Map</a> k v)</td><td class="doc empty"> </td></tr><tr><td class="src">(<a href="../deepseq-1.3.0.0/Control-DeepSeq.html#t:NFData">NFData</a> k, <a href="../deepseq-1.3.0.0/Control-DeepSeq.html#t:NFData">NFData</a> a) => <a href="../deepseq-1.3.0.0/Control-DeepSeq.html#t:NFData">NFData</a> (<a href="Data-Map.html#t:Map">Map</a> k a)</td><td class="doc empty"> </td></tr></table></div></div></div><h1 id="g:2">Operators
</h1><div class="top"><p class="src"><a name="v:-33-" class="def">(!)</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="Data-Map.html#t:Map">Map</a> k a -> k -> a</p><div class="doc"><p><em>O(log n)</em>. Find the value at a key.
Calls <code><a href="../base-4.5.1.0/Prelude.html#v:error">error</a></code> 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></div></div><div class="top"><p class="src"><a name="v:-92--92-" class="def">(\\)</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p>Same as <code><a href="Data-Map.html#v:difference">difference</a></code>.
</p></div></div><h1 id="g:3">Query
</h1><div class="top"><p class="src"><a name="v:null" class="def">null</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div 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></div></div><div class="top"><p class="src"><a name="v:size" class="def">size</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div 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></div></div><div class="top"><p class="src"><a name="v:member" class="def">member</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(log n)</em>. Is the key a member of the map? See also <code><a href="Data-Map.html#v:notMember">notMember</a></code>.
</p><pre> member 5 (fromList [(5,'a'), (3,'b')]) == True
member 1 (fromList [(5,'a'), (3,'b')]) == False
</pre></div></div><div class="top"><p class="src"><a name="v:notMember" class="def">notMember</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(log n)</em>. Is the key not a member of the map? See also <code><a href="Data-Map.html#v:member">member</a></code>.
</p><pre> notMember 5 (fromList [(5,'a'), (3,'b')]) == False
notMember 1 (fromList [(5,'a'), (3,'b')]) == True
</pre></div></div><div class="top"><p class="src"><a name="v:lookup" class="def">lookup</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a</p><div 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 <code>(<code><a href="../base-4.5.1.0/Data-Maybe.html#v:Just">Just</a></code> value)</code>,
or <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code> if the key isn't in the map.
</p><p>An example of using <code>lookup</code>:
</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></div></div><div class="top"><p class="src"><a name="v:findWithDefault" class="def">findWithDefault</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => a -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> a</p><div class="doc"><p><em>O(log n)</em>. The expression <code>(<code><a href="Data-Map.html#v:findWithDefault">findWithDefault</a></code> def k map)</code> returns
the value at key <code>k</code> or returns default value <code>def</code>
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></div></div><h1 id="g:4">Construction
</h1><div class="top"><p class="src"><a name="v:empty" class="def">empty</a> :: <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p><em>O(1)</em>. The empty map.
</p><pre> empty == fromList []
size empty == 0
</pre></div></div><div class="top"><p class="src"><a name="v:singleton" class="def">singleton</a> :: k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><h2 id="g:5">Insertion
</h2><div class="top"><p class="src"><a name="v:insert" class="def">insert</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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. <code><a href="Data-Map.html#v:insert">insert</a></code> is equivalent to
<code><code><a href="Data-Map.html#v:insertWith">insertWith</a></code> <code><a href="../base-4.5.1.0/Prelude.html#v:const">const</a></code></code>.
</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></div></div><div class="top"><p class="src"><a name="v:insertWith" class="def">insertWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> a -> a) -> k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p><em>O(log n)</em>. Insert with a function, combining new value and old value.
<code><code><a href="Data-Map.html#v:insertWith">insertWith</a></code> f key value mp</code>
will insert the pair (key, value) into <code>mp</code> if key does
not exist in the map. If the key does exist, the function will
insert the pair <code>(key, f new_value old_value)</code>.
</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></div></div><div class="top"><p class="src"><a name="v:insertWith-39-" class="def">insertWith'</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> a -> a) -> k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p>Same as <code><a href="Data-Map.html#v:insertWith">insertWith</a></code>, but the combining function is applied strictly.
This is often the most desirable behavior.
</p><p>For example, to update a counter:
</p><pre> insertWith' (+) k 1 m
</pre></div></div><div class="top"><p class="src"><a name="v:insertWithKey" class="def">insertWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a -> a) -> k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p><em>O(log n)</em>. Insert with a function, combining key, new value and old value.
<code><code><a href="Data-Map.html#v:insertWithKey">insertWithKey</a></code> f key value mp</code>
will insert the pair (key, value) into <code>mp</code> if key does
not exist in the map. If the key does exist, the function will
insert the pair <code>(key,f key new_value old_value)</code>.
Note that the key passed to f is the same key passed to <code><a href="Data-Map.html#v:insertWithKey">insertWithKey</a></code>.
</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></div></div><div class="top"><p class="src"><a name="v:insertWithKey-39-" class="def">insertWithKey'</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a -> a) -> k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p>Same as <code><a href="Data-Map.html#v:insertWithKey">insertWithKey</a></code>, but the combining function is applied strictly.
</p></div></div><div class="top"><p class="src"><a name="v:insertLookupWithKey" class="def">insertLookupWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a -> a) -> k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a, <a href="Data-Map.html#t:Map">Map</a> k a)</p><div class="doc"><p><em>O(log n)</em>. Combines insert operation with old value retrieval.
The expression (<code><code><a href="Data-Map.html#v:insertLookupWithKey">insertLookupWithKey</a></code> f k x map</code>)
is a pair where the first element is equal to (<code><code><a href="Data-Map.html#v:lookup">lookup</a></code> k map</code>)
and the second element equal to (<code><code><a href="Data-Map.html#v:insertWithKey">insertWithKey</a></code> f k x map</code>).
</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 <code>insertLookup</code> using <code>insertLookupWithKey</code>:
</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></div></div><div class="top"><p class="src"><a name="v:insertLookupWithKey-39-" class="def">insertLookupWithKey'</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a -> a) -> k -> a -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a, <a href="Data-Map.html#t:Map">Map</a> k a)</p><div class="doc"><p><em>O(log n)</em>. A strict version of <code><a href="Data-Map.html#v:insertLookupWithKey">insertLookupWithKey</a></code>.
</p></div></div><h2 id="g:6">Delete/Update
</h2><div class="top"><p class="src"><a name="v:delete" class="def">delete</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:adjust" class="def">adjust</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> a) -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:adjustWithKey" class="def">adjustWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a) -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:update" class="def">update</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p><em>O(log n)</em>. The expression (<code><code><a href="Data-Map.html#v:update">update</a></code> f k map</code>) updates the value <code>x</code>
at <code>k</code> (if it is in the map). If (<code>f x</code>) is <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code>, the element is
deleted. If it is (<code><code><a href="../base-4.5.1.0/Data-Maybe.html#v:Just">Just</a></code> y</code>), the key <code>k</code> is bound to the new value <code>y</code>.
</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></div></div><div class="top"><p class="src"><a name="v:updateWithKey" class="def">updateWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p><em>O(log n)</em>. The expression (<code><code><a href="Data-Map.html#v:updateWithKey">updateWithKey</a></code> f k map</code>) updates the
value <code>x</code> at <code>k</code> (if it is in the map). If (<code>f k x</code>) is <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code>,
the element is deleted. If it is (<code><code><a href="../base-4.5.1.0/Data-Maybe.html#v:Just">Just</a></code> y</code>), the key <code>k</code> is bound
to the new value <code>y</code>.
</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></div></div><div class="top"><p class="src"><a name="v:updateLookupWithKey" class="def">updateLookupWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a, <a href="Data-Map.html#t:Map">Map</a> k a)</p><div class="doc"><p><em>O(log n)</em>. Lookup and update. See also <code><a href="Data-Map.html#v:updateWithKey">updateWithKey</a></code>.
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></div></div><div class="top"><p class="src"><a name="v:alter" class="def">alter</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (<a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p><em>O(log n)</em>. The expression (<code><code><a href="Data-Map.html#v:alter">alter</a></code> f k map</code>) alters the value <code>x</code> at <code>k</code>, or absence thereof.
<code><a href="Data-Map.html#v:alter">alter</a></code> can be used to insert, delete, or update a value in a <code><a href="Data-Map.html#t:Map">Map</a></code>.
In short : <code><code><a href="Data-Map.html#v:lookup">lookup</a></code> k (<code><a href="Data-Map.html#v:alter">alter</a></code> f k m) = f (<code><a href="Data-Map.html#v:lookup">lookup</a></code> k m)</code>.
</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></div></div><h1 id="g:7">Combine
</h1><h2 id="g:8">Union
</h2><div class="top"><p class="src"><a name="v:union" class="def">union</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p><em>O(n+m)</em>.
The expression (<code><code><a href="Data-Map.html#v:union">union</a></code> t1 t2</code>) takes the left-biased union of <code>t1</code> and <code>t2</code>.
It prefers <code>t1</code> when duplicate keys are encountered,
i.e. (<code><code><a href="Data-Map.html#v:union">union</a></code> == <code><a href="Data-Map.html#v:unionWith">unionWith</a></code> <code><a href="../base-4.5.1.0/Prelude.html#v:const">const</a></code></code>).
The implementation uses the efficient <em>hedge-union</em> algorithm.
Hedge-union is more efficient on (bigset `<code><a href="Data-Map.html#v:union">union</a></code>` smallset).
</p><pre> union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
</pre></div></div><div class="top"><p class="src"><a name="v:unionWith" class="def">unionWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> a -> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:unionWithKey" class="def">unionWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a -> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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 `<code><a href="Data-Map.html#v:union">union</a></code>` 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></div></div><div class="top"><p class="src"><a name="v:unions" class="def">unions</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => [<a href="Data-Map.html#t:Map">Map</a> k a] -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p>The union of a list of maps:
(<code><code><a href="Data-Map.html#v:unions">unions</a></code> == <code><a href="../base-4.5.1.0/Prelude.html#v:foldl">foldl</a></code> <code><a href="Data-Map.html#v:union">union</a></code> <code><a href="Data-Map.html#v:empty">empty</a></code></code>).
</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></div></div><div class="top"><p class="src"><a name="v:unionsWith" class="def">unionsWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> a -> a) -> [<a href="Data-Map.html#t:Map">Map</a> k a] -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p>The union of a list of maps, with a combining operation:
(<code><code><a href="Data-Map.html#v:unionsWith">unionsWith</a></code> f == <code><a href="../base-4.5.1.0/Prelude.html#v:foldl">foldl</a></code> (<code><a href="Data-Map.html#v:unionWith">unionWith</a></code> f) <code><a href="Data-Map.html#v:empty">empty</a></code></code>).
</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></div></div><h2 id="g:9">Difference
</h2><div class="top"><p class="src"><a name="v:difference" class="def">difference</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:differenceWith" class="def">differenceWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> b -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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 <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code>, the element is discarded (proper set difference). If
it returns (<code><code><a href="../base-4.5.1.0/Data-Maybe.html#v:Just">Just</a></code> y</code>), the element is updated with a new value <code>y</code>.
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></div></div><div class="top"><p class="src"><a name="v:differenceWithKey" class="def">differenceWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> b -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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 <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code>, the element is discarded (proper set difference). If
it returns (<code><code><a href="../base-4.5.1.0/Data-Maybe.html#v:Just">Just</a></code> y</code>), the element is updated with a new value <code>y</code>.
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></div></div><h2 id="g:10">Intersection
</h2><div class="top"><p class="src"><a name="v:intersection" class="def">intersection</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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.
(<code><code><a href="Data-Map.html#v:intersection">intersection</a></code> m1 m2 == <code><a href="Data-Map.html#v:intersectionWith">intersectionWith</a></code> <code><a href="../base-4.5.1.0/Prelude.html#v:const">const</a></code> m1 m2</code>).
</p><pre> intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"
</pre></div></div><div class="top"><p class="src"><a name="v:intersectionWith" class="def">intersectionWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> b -> c) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k c</p><div 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></div></div><div class="top"><p class="src"><a name="v:intersectionWithKey" class="def">intersectionWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> b -> c) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="Data-Map.html#t:Map">Map</a> k c</p><div class="doc"><p><em>O(n+m)</em>. Intersection with a combining function.
Intersection is more efficient on (bigset `<code><a href="Data-Map.html#v:intersection">intersection</a></code>` 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></div></div><h1 id="g:11">Traversal
</h1><h2 id="g:12">Map
</h2><div class="top"><p class="src"><a name="v:map" class="def">map</a> :: (a -> b) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b</p><div 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></div></div><div class="top"><p class="src"><a name="v:mapWithKey" class="def">mapWithKey</a> :: (k -> a -> b) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b</p><div 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></div></div><div class="top"><p class="src"><a name="v:mapAccum" class="def">mapAccum</a> :: (a -> b -> (a, c)) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> (a, <a href="Data-Map.html#t:Map">Map</a> k c)</p><div class="doc"><p><em>O(n)</em>. The function <code><a href="Data-Map.html#v:mapAccum">mapAccum</a></code> 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></div></div><div class="top"><p class="src"><a name="v:mapAccumWithKey" class="def">mapAccumWithKey</a> :: (a -> k -> b -> (a, c)) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> (a, <a href="Data-Map.html#t:Map">Map</a> k c)</p><div class="doc"><p><em>O(n)</em>. The function <code><a href="Data-Map.html#v:mapAccumWithKey">mapAccumWithKey</a></code> 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></div></div><div class="top"><p class="src"><a name="v:mapAccumRWithKey" class="def">mapAccumRWithKey</a> :: (a -> k -> b -> (a, c)) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> (a, <a href="Data-Map.html#t:Map">Map</a> k c)</p><div class="doc"><p><em>O(n)</em>. The function <code>mapAccumR</code> threads an accumulating
argument through the map in descending order of keys.
</p></div></div><div class="top"><p class="src"><a name="v:mapKeys" class="def">mapKeys</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k2 => (k1 -> k2) -> <a href="Data-Map.html#t:Map">Map</a> k1 a -> <a href="Data-Map.html#t:Map">Map</a> k2 a</p><div class="doc"><p><em>O(n*log n)</em>.
<code><code><a href="Data-Map.html#v:mapKeys">mapKeys</a></code> f s</code> is the map obtained by applying <code>f</code> to each key of <code>s</code>.
</p><p>The size of the result may be smaller if <code>f</code> 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></div></div><div class="top"><p class="src"><a name="v:mapKeysWith" class="def">mapKeysWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k2 => (a -> a -> a) -> (k1 -> k2) -> <a href="Data-Map.html#t:Map">Map</a> k1 a -> <a href="Data-Map.html#t:Map">Map</a> k2 a</p><div class="doc"><p><em>O(n*log n)</em>.
<code><code><a href="Data-Map.html#v:mapKeysWith">mapKeysWith</a></code> c f s</code> is the map obtained by applying <code>f</code> to each key of <code>s</code>.
</p><p>The size of the result may be smaller if <code>f</code> maps two or more distinct
keys to the same new key. In this case the associated values will be
combined using <code>c</code>.
</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></div></div><div class="top"><p class="src"><a name="v:mapKeysMonotonic" class="def">mapKeysMonotonic</a> :: (k1 -> k2) -> <a href="Data-Map.html#t:Map">Map</a> k1 a -> <a href="Data-Map.html#t:Map">Map</a> k2 a</p><div class="doc"><p><em>O(n)</em>.
<code><code><a href="Data-Map.html#v:mapKeysMonotonic">mapKeysMonotonic</a></code> f s == <code><a href="Data-Map.html#v:mapKeys">mapKeys</a></code> f s</code>, but works only when <code>f</code>
is strictly monotonic.
That is, for any values <code>x</code> and <code>y</code>, if <code>x</code> < <code>y</code> then <code>f x</code> < <code>f y</code>.
<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 <code>f</code> maps distinct original keys to distinct resulting keys.
This function has better performance than <code><a href="Data-Map.html#v:mapKeys">mapKeys</a></code>.
</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></div></div><h1 id="g:13">Folds
</h1><div class="top"><p class="src"><a name="v:foldr" class="def">foldr</a> :: (a -> b -> b) -> b -> <a href="Data-Map.html#t:Map">Map</a> k a -> b</p><div class="doc"><p><em>O(n)</em>. Fold the values in the map using the given right-associative
binary operator, such that <code><code><a href="Data-Map.html#v:foldr">foldr</a></code> f z == <code><a href="../base-4.5.1.0/Prelude.html#v:foldr">foldr</a></code> f z . <code><a href="Data-Map.html#v:elems">elems</a></code></code>.
</p><p>For example,
</p><pre> elems map = foldr (:) [] map
</pre><pre> let f a len = len + (length a)
foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
</pre></div></div><div class="top"><p class="src"><a name="v:foldl" class="def">foldl</a> :: (a -> b -> a) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> a</p><div class="doc"><p><em>O(n)</em>. Fold the values in the map using the given left-associative
binary operator, such that <code><code><a href="Data-Map.html#v:foldl">foldl</a></code> f z == <code><a href="../base-4.5.1.0/Prelude.html#v:foldl">foldl</a></code> f z . <code><a href="Data-Map.html#v:elems">elems</a></code></code>.
</p><p>For example,
</p><pre> elems = reverse . foldl (flip (:)) []
</pre><pre> let f len a = len + (length a)
foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
</pre></div></div><div class="top"><p class="src"><a name="v:foldrWithKey" class="def">foldrWithKey</a> :: (k -> a -> b -> b) -> b -> <a href="Data-Map.html#t:Map">Map</a> k a -> b</p><div class="doc"><p><em>O(n)</em>. Fold the keys and values in the map using the given right-associative
binary operator, such that
<code><code><a href="Data-Map.html#v:foldrWithKey">foldrWithKey</a></code> f z == <code><a href="../base-4.5.1.0/Prelude.html#v:foldr">foldr</a></code> (<code><a href="../base-4.5.1.0/Data-Tuple.html#v:uncurry">uncurry</a></code> f) z . <code><a href="Data-Map.html#v:toAscList">toAscList</a></code></code>.
</p><p>For example,
</p><pre> keys map = foldrWithKey (\k x ks -> k:ks) [] map
</pre><pre> let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
</pre></div></div><div class="top"><p class="src"><a name="v:foldlWithKey" class="def">foldlWithKey</a> :: (a -> k -> b -> a) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> a</p><div class="doc"><p><em>O(n)</em>. Fold the keys and values in the map using the given left-associative
binary operator, such that
<code><code><a href="Data-Map.html#v:foldlWithKey">foldlWithKey</a></code> f z == <code><a href="../base-4.5.1.0/Prelude.html#v:foldl">foldl</a></code> (\z' (kx, x) -> f z' kx x) z . <code><a href="Data-Map.html#v:toAscList">toAscList</a></code></code>.
</p><p>For example,
</p><pre> keys = reverse . foldlWithKey (\ks k x -> k:ks) []
</pre><pre> let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"
</pre></div></div><h2 id="g:14">Strict folds
</h2><div class="top"><p class="src"><a name="v:foldr-39-" class="def">foldr'</a> :: (a -> b -> b) -> b -> <a href="Data-Map.html#t:Map">Map</a> k a -> b</p><div class="doc"><p><em>O(n)</em>. A strict version of <code><a href="Data-Map.html#v:foldr">foldr</a></code>. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
</p></div></div><div class="top"><p class="src"><a name="v:foldl-39-" class="def">foldl'</a> :: (a -> b -> a) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> a</p><div class="doc"><p><em>O(n)</em>. A strict version of <code><a href="Data-Map.html#v:foldl">foldl</a></code>. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
</p></div></div><div class="top"><p class="src"><a name="v:foldrWithKey-39-" class="def">foldrWithKey'</a> :: (k -> a -> b -> b) -> b -> <a href="Data-Map.html#t:Map">Map</a> k a -> b</p><div class="doc"><p><em>O(n)</em>. A strict version of <code><a href="Data-Map.html#v:foldrWithKey">foldrWithKey</a></code>. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
</p></div></div><div class="top"><p class="src"><a name="v:foldlWithKey-39-" class="def">foldlWithKey'</a> :: (a -> k -> b -> a) -> a -> <a href="Data-Map.html#t:Map">Map</a> k b -> a</p><div class="doc"><p><em>O(n)</em>. A strict version of <code><a href="Data-Map.html#v:foldlWithKey">foldlWithKey</a></code>. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
</p></div></div><h2 id="g:15">Legacy folds
</h2><div class="top"><p class="src"><a name="v:fold" class="def">fold</a> :: (a -> b -> b) -> b -> <a href="Data-Map.html#t:Map">Map</a> k a -> b</p><div class="doc"><p><em>O(n)</em>. Fold the values in the map using the given right-associative
binary operator. This function is an equivalent of <code><a href="Data-Map.html#v:foldr">foldr</a></code> and is present
for compatibility only.
</p><p><em>Please note that fold will be deprecated in the future and removed.</em>
</p></div></div><div class="top"><p class="src"><a name="v:foldWithKey" class="def">foldWithKey</a> :: (k -> a -> b -> b) -> b -> <a href="Data-Map.html#t:Map">Map</a> k a -> b</p><div class="doc"><p><em>O(n)</em>. Fold the keys and values in the map using the given right-associative
binary operator. This function is an equivalent of <code><a href="Data-Map.html#v:foldrWithKey">foldrWithKey</a></code> and is present
for compatibility only.
</p><p><em>Please note that foldWithKey will be deprecated in the future and removed.</em>
</p></div></div><h1 id="g:16">Conversion
</h1><div class="top"><p class="src"><a name="v:elems" class="def">elems</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> [a]</p><div 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></div></div><div class="top"><p class="src"><a name="v:keys" class="def">keys</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> [k]</p><div 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></div></div><div class="top"><p class="src"><a name="v:keysSet" class="def">keysSet</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Set.html#t:Set">Set</a> k</p><div 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></div></div><div class="top"><p class="src"><a name="v:assocs" class="def">assocs</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> [(k, a)]</p><div 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></div></div><h2 id="g:17">Lists
</h2><div class="top"><p class="src"><a name="v:toList" class="def">toList</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> [(k, a)]</p><div 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></div></div><div class="top"><p class="src"><a name="v:fromList" class="def">fromList</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p><em>O(n*log n)</em>. Build a map from a list of key/value pairs. See also <code><a href="Data-Map.html#v:fromAscList">fromAscList</a></code>.
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></div></div><div class="top"><p class="src"><a name="v:fromListWith" class="def">fromListWith</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> a -> a) -> [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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 <code><a href="Data-Map.html#v:fromAscListWith">fromAscListWith</a></code>.
</p><pre> fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
fromListWith (++) [] == empty
</pre></div></div><div class="top"><p class="src"><a name="v:fromListWithKey" class="def">fromListWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> a -> a) -> [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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 <code><a href="Data-Map.html#v:fromAscListWithKey">fromAscListWithKey</a></code>.
</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></div></div><h2 id="g:18">Ordered lists
</h2><div class="top"><p class="src"><a name="v:toAscList" class="def">toAscList</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> [(k, a)]</p><div 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></div></div><div class="top"><p class="src"><a name="v:toDescList" class="def">toDescList</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> [(k, a)]</p><div class="doc"><p><em>O(n)</em>. Convert to a descending list.
</p></div></div><div class="top"><p class="src"><a name="v:fromAscList" class="def">fromAscList</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> k => [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:fromAscListWith" class="def">fromAscListWith</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> k => (a -> a -> a) -> [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:fromAscListWithKey" class="def">fromAscListWithKey</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> k => (k -> a -> a -> a) -> [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:fromDistinctAscList" class="def">fromDistinctAscList</a> :: [(k, a)] -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><h1 id="g:19">Filter
</h1><div class="top"><p class="src"><a name="v:filter" class="def">filter</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:filterWithKey" class="def">filterWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:partition" class="def">partition</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="Data-Map.html#t:Map">Map</a> k a, <a href="Data-Map.html#t:Map">Map</a> k a)</p><div 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 <code><a href="Data-Map.html#v:split">split</a></code>.
</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></div></div><div class="top"><p class="src"><a name="v:partitionWithKey" class="def">partitionWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="Data-Map.html#t:Map">Map</a> k a, <a href="Data-Map.html#t:Map">Map</a> k a)</p><div 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 <code><a href="Data-Map.html#v:split">split</a></code>.
</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></div></div><div class="top"><p class="src"><a name="v:mapMaybe" class="def">mapMaybe</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> b) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b</p><div class="doc"><p><em>O(n)</em>. Map values and collect the <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Just">Just</a></code> 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></div></div><div class="top"><p class="src"><a name="v:mapMaybeWithKey" class="def">mapMaybeWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> b) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b</p><div class="doc"><p><em>O(n)</em>. Map keys/values and collect the <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Just">Just</a></code> 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></div></div><div class="top"><p class="src"><a name="v:mapEither" class="def">mapEither</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> <a href="../base-4.5.1.0/Data-Either.html#t:Either">Either</a> b c) -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="Data-Map.html#t:Map">Map</a> k b, <a href="Data-Map.html#t:Map">Map</a> k c)</p><div class="doc"><p><em>O(n)</em>. Map values and separate the <code><a href="../base-4.5.1.0/Data-Either.html#v:Left">Left</a></code> and <code><a href="../base-4.5.1.0/Data-Either.html#v:Right">Right</a></code> 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></div></div><div class="top"><p class="src"><a name="v:mapEitherWithKey" class="def">mapEitherWithKey</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (k -> a -> <a href="../base-4.5.1.0/Data-Either.html#t:Either">Either</a> b c) -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="Data-Map.html#t:Map">Map</a> k b, <a href="Data-Map.html#t:Map">Map</a> k c)</p><div class="doc"><p><em>O(n)</em>. Map keys/values and separate the <code><a href="../base-4.5.1.0/Data-Either.html#v:Left">Left</a></code> and <code><a href="../base-4.5.1.0/Data-Either.html#v:Right">Right</a></code> 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></div></div><div class="top"><p class="src"><a name="v:split" class="def">split</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="Data-Map.html#t:Map">Map</a> k a, <a href="Data-Map.html#t:Map">Map</a> k a)</p><div class="doc"><p><em>O(log n)</em>. The expression (<code><code><a href="Data-Map.html#v:split">split</a></code> k map</code>) is a pair <code>(map1,map2)</code> where
the keys in <code>map1</code> are smaller than <code>k</code> and the keys in <code>map2</code> larger than <code>k</code>.
Any key equal to <code>k</code> is found in neither <code>map1</code> nor <code>map2</code>.
</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></div></div><div class="top"><p class="src"><a name="v:splitLookup" class="def">splitLookup</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> (<a href="Data-Map.html#t:Map">Map</a> k a, <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a, <a href="Data-Map.html#t:Map">Map</a> k a)</p><div class="doc"><p><em>O(log n)</em>. The expression (<code><code><a href="Data-Map.html#v:splitLookup">splitLookup</a></code> k map</code>) splits a map just
like <code><a href="Data-Map.html#v:split">split</a></code> but also returns <code><code><a href="Data-Map.html#v:lookup">lookup</a></code> k map</code>.
</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></div></div><h1 id="g:20">Submap
</h1><div class="top"><p class="src"><a name="v:isSubmapOf" class="def">isSubmapOf</a> :: (<a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a) => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(n+m)</em>.
This function is defined as (<code><code><a href="Data-Map.html#v:isSubmapOf">isSubmapOf</a></code> = <code><a href="Data-Map.html#v:isSubmapOfBy">isSubmapOfBy</a></code> (==)</code>).
</p></div></div><div class="top"><p class="src"><a name="v:isSubmapOfBy" class="def">isSubmapOfBy</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> b -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(n+m)</em>.
The expression (<code><code><a href="Data-Map.html#v:isSubmapOfBy">isSubmapOfBy</a></code> f t1 t2</code>) returns <code><a href="../base-4.5.1.0/Data-Bool.html#v:True">True</a></code> if
all keys in <code>t1</code> are in tree <code>t2</code>, and when <code>f</code> returns <code><a href="../base-4.5.1.0/Data-Bool.html#v:True">True</a></code> when
applied to their respective values. For example, the following
expressions are all <code><a href="../base-4.5.1.0/Data-Bool.html#v:True">True</a></code>:
</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 <code><a href="../base-4.5.1.0/Data-Bool.html#v:False">False</a></code>:
</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></div></div><div class="top"><p class="src"><a name="v:isProperSubmapOf" class="def">isProperSubmapOf</a> :: (<a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a) => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(n+m)</em>. Is this a proper submap? (ie. a submap but not equal).
Defined as (<code><code><a href="Data-Map.html#v:isProperSubmapOf">isProperSubmapOf</a></code> = <code><a href="Data-Map.html#v:isProperSubmapOfBy">isProperSubmapOfBy</a></code> (==)</code>).
</p></div></div><div class="top"><p class="src"><a name="v:isProperSubmapOfBy" class="def">isProperSubmapOfBy</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => (a -> b -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k b -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(n+m)</em>. Is this a proper submap? (ie. a submap but not equal).
The expression (<code><code><a href="Data-Map.html#v:isProperSubmapOfBy">isProperSubmapOfBy</a></code> f m1 m2</code>) returns <code><a href="../base-4.5.1.0/Data-Bool.html#v:True">True</a></code> when
<code>m1</code> and <code>m2</code> are not equal,
all keys in <code>m1</code> are in <code>m2</code>, and when <code>f</code> returns <code><a href="../base-4.5.1.0/Data-Bool.html#v:True">True</a></code> when
applied to their respective values. For example, the following
expressions are all <code><a href="../base-4.5.1.0/Data-Bool.html#v:True">True</a></code>:
</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 <code><a href="../base-4.5.1.0/Data-Bool.html#v:False">False</a></code>:
</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></div></div><h1 id="g:21">Indexed
</h1><div class="top"><p class="src"><a name="v:lookupIndex" class="def">lookupIndex</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div 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 <code><a href="Data-Map.html#v:size">size</a></code> 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></div></div><div class="top"><p class="src"><a name="v:findIndex" class="def">findIndex</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => k -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div 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 <code><a href="Data-Map.html#v:size">size</a></code> of the map. Calls <code><a href="../base-4.5.1.0/Prelude.html#v:error">error</a></code> when
the key is not a <code><a href="Data-Map.html#v:member">member</a></code> 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></div></div><div class="top"><p class="src"><a name="v:elemAt" class="def">elemAt</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Map.html#t:Map">Map</a> k a -> (k, a)</p><div class="doc"><p><em>O(log n)</em>. Retrieve an element by <em>index</em>. Calls <code><a href="../base-4.5.1.0/Prelude.html#v:error">error</a></code> 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></div></div><div class="top"><p class="src"><a name="v:updateAt" class="def">updateAt</a> :: (k -> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p><em>O(log n)</em>. Update the element at <em>index</em>. Calls <code><a href="../base-4.5.1.0/Prelude.html#v:error">error</a></code> 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></div></div><div class="top"><p class="src"><a name="v:deleteAt" class="def">deleteAt</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div class="doc"><p><em>O(log n)</em>. Delete the element at <em>index</em>.
Defined as (<code><code><a href="Data-Map.html#v:deleteAt">deleteAt</a></code> i map = <code><a href="Data-Map.html#v:updateAt">updateAt</a></code> (k x -> <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code>) i map</code>).
</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></div></div><h1 id="g:22">Min/Max
</h1><div class="top"><p class="src"><a name="v:findMin" class="def">findMin</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> (k, a)</p><div class="doc"><p><em>O(log n)</em>. The minimal key of the map. Calls <code><a href="../base-4.5.1.0/Prelude.html#v:error">error</a></code> if the map is empty.
</p><pre> findMin (fromList [(5,"a"), (3,"b")]) == (3,"b")
findMin empty Error: empty map has no minimal element
</pre></div></div><div class="top"><p class="src"><a name="v:findMax" class="def">findMax</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> (k, a)</p><div class="doc"><p><em>O(log n)</em>. The maximal key of the map. Calls <code><a href="../base-4.5.1.0/Prelude.html#v:error">error</a></code> if the map is empty.
</p><pre> findMax (fromList [(5,"a"), (3,"b")]) == (5,"a")
findMax empty Error: empty map has no maximal element
</pre></div></div><div class="top"><p class="src"><a name="v:deleteMin" class="def">deleteMin</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:deleteMax" class="def">deleteMax</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:deleteFindMin" class="def">deleteFindMin</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> ((k, a), <a href="Data-Map.html#t:Map">Map</a> k a)</p><div 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></div></div><div class="top"><p class="src"><a name="v:deleteFindMax" class="def">deleteFindMax</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> ((k, a), <a href="Data-Map.html#t:Map">Map</a> k a)</p><div 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></div></div><div class="top"><p class="src"><a name="v:updateMin" class="def">updateMin</a> :: (a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:updateMax" class="def">updateMax</a> :: (a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:updateMinWithKey" class="def">updateMinWithKey</a> :: (k -> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:updateMaxWithKey" class="def">updateMaxWithKey</a> :: (k -> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="Data-Map.html#t:Map">Map</a> k a</p><div 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></div></div><div class="top"><p class="src"><a name="v:minView" class="def">minView</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (a, <a href="Data-Map.html#t:Map">Map</a> k a)</p><div 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 <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code> if passed an
empty map.
</p><pre> minView (fromList [(5,"a"), (3,"b")]) == Just ("b", singleton 5 "a")
minView empty == Nothing
</pre></div></div><div class="top"><p class="src"><a name="v:maxView" class="def">maxView</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (a, <a href="Data-Map.html#t:Map">Map</a> k a)</p><div 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 <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code> if passed an
</p><pre> maxView (fromList [(5,"a"), (3,"b")]) == Just ("a", singleton 3 "b")
maxView empty == Nothing
</pre></div></div><div class="top"><p class="src"><a name="v:minViewWithKey" class="def">minViewWithKey</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> ((k, a), <a href="Data-Map.html#t:Map">Map</a> k a)</p><div 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 <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code> if passed an empty map.
</p><pre> minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
minViewWithKey empty == Nothing
</pre></div></div><div class="top"><p class="src"><a name="v:maxViewWithKey" class="def">maxViewWithKey</a> :: <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> ((k, a), <a href="Data-Map.html#t:Map">Map</a> k a)</p><div 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 <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code> if passed an empty map.
</p><pre> maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
maxViewWithKey empty == Nothing
</pre></div></div><h1 id="g:23">Debugging
</h1><div class="top"><p class="src"><a name="v:showTree" class="def">showTree</a> :: (<a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> k, <a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> a) => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-String.html#t:String">String</a></p><div class="doc"><p><em>O(n)</em>. Show the tree that implements the map. The tree is shown
in a compressed, hanging format. See <code><a href="Data-Map.html#v:showTreeWith">showTreeWith</a></code>.
</p></div></div><div class="top"><p class="src"><a name="v:showTreeWith" class="def">showTreeWith</a> :: (k -> a -> <a href="../base-4.5.1.0/Data-String.html#t:String">String</a>) -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a> -> <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-String.html#t:String">String</a></p><div class="doc"><p><em>O(n)</em>. The expression (<code><code><a href="Data-Map.html#v:showTreeWith">showTreeWith</a></code> showelem hang wide map</code>) shows
the tree that implements the map. Elements are shown using the <code>showElem</code> function. If <code>hang</code> is
<code><a href="../base-4.5.1.0/Data-Bool.html#v:True">True</a></code>, a <em>hanging</em> tree is shown otherwise a rotated tree is shown. If
<code>wide</code> is <code><a href="../base-4.5.1.0/Data-Bool.html#v:True">True</a></code>, 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></div></div><div class="top"><p class="src"><a name="v:valid" class="def">valid</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> k => <a href="Data-Map.html#t:Map">Map</a> k a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div 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></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.11.0</p></div></body></html>
distrib
>
Mageia
>
5
>
i586
>
media
>
core-release
>
by-pkgid
>
6e204a966e8c42d976f99a1700ce5f20
>
files
>
2592
