Module
Map

*Note:* You should use Data.Map.Strict instead of this module if:

- You will eventually need all the values stored.
- The stored values don't represent large virtual data structures to be lazily computed.

An efficient implementation of ordered maps from keys to values (dictionaries).

These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.

import qualified Data.Map as Map

The implementation of `Map`

is based on *size balanced* binary trees (or
trees of *bounded balance*) as described by:

- Stephen Adams, "
*Efficient sets: a balancing act*", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/. - J. Nievergelt and E.M. Reingold,
"
*Binary search trees of bounded balance*", SIAM journal of computing 2(1), March 1973.

Note that the implementation is *left-biased* -- the elements of a
first argument are always preferred to the second, for example in
`union`

or `insert`

.

Operation comments contain the operation time complexity in the Big-O notation (http://en.wikipedia.org/wiki/Big_O_notation).

fold
:: (a -> b -> b) -> b -> Map k a -> b

map
:: (a -> b) -> Map k a -> Map k b

*O(n)*. Map a function over all values in the map.

map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]

map
:: (a -> b) -> Map k a -> Map k b

*O(n)*. Map a function over all values in the map.

map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]

Data
Map

A Map from keys `k`

to values `a`

.

Data
Map

A Map from keys `k`

to values `a`

.

Module
Lens

One of most commonly-asked questions about this package is whether
it provides lenses for working with `Map`

. It does, but their uses
are perhaps obscured by their genericity. This module exists to provide
documentation for them.

`Map`

is an instance of `At`

, so we have a lenses
on values at keys:

`>>>`

Just "world"`Map.fromList [(1, "world")] ^.at 1`

`>>>`

fromList [(1,"world")]`at 1 .~ Just "world" $ Map.empty`

`>>>`

fromList [(0,"hello")]`at 0 ?~ "hello" $ Map.empty`

We can traverse, fold over, and map over key-value pairs in a
`Map`

, thanks to its `TraversableWithIndex`

,
`FoldableWithIndex`

, and
`FunctorWithIndex`

instances.

`>>>`

fromList [(1,1)]`imap const $ Map.fromList [(1, "Venus")]`

`>>>`

Sum {getSum = 5}`ifoldMap (\i _ -> Sum i) $ Map.fromList [(2, "Earth"), (3, "Mars")]`

`>>>`

(4,"Jupiter")`itraverse_ (curry print) $ Map.fromList [(4, "Jupiter")]`

`>>>`

[(5,"Saturn")]`itoList $ Map.fromList [(5, "Saturn")]`

A related class, `Ixed`

, allows us to use
`ix`

to traverse a value at a particular key.

`>>>`

fromList [(2,"New Earth")]`ix 2 %~ ("New " ++) $ Map.fromList [(2, "Earth")]`

`>>>`

Nothing`preview (ix 8) $ Map.empty`

Additionally, `Map`

has `TraverseMin`

and
`TraverseMax`

instances, which let us traverse over
the value at the least and greatest keys, respectively.

`>>>`

Just "Saturn"`preview traverseMin $ Map.fromList [(5, "Saturn"), (6, "Uranus")]`

`>>>`

Just "Uranus"`preview traverseMax $ Map.fromList [(5, "Saturn"), (6, "Uranus")]`

Module
Strict

An efficient implementation of ordered maps from keys to values (dictionaries).

API of this module is strict in both the keys and the values.
If you need value-lazy maps, use Data.Map.Lazy instead.
The `Map`

type is shared between the lazy and strict modules,
meaning that the same `Map`

value can be passed to functions in
both modules (although that is rarely needed).

These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.

import qualified Data.Map.Strict as Map

The implementation of `Map`

is based on *size balanced* binary trees (or
trees of *bounded balance*) as described by:

- Stephen Adams, "
*Efficient sets: a balancing act*", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/. - J. Nievergelt and E.M. Reingold,
"
*Binary search trees of bounded balance*", SIAM journal of computing 2(1), March 1973.

Note that the implementation is *left-biased* -- the elements of a
first argument are always preferred to the second, for example in
`union`

or `insert`

.

Operation comments contain the operation time complexity in the Big-O notation (http://en.wikipedia.org/wiki/Big_O_notation).

Be aware that the `Functor`

, `Traversable`

and `Data`

instances
are the same as for the Data.Map.Lazy module, so if they are used
on strict maps, the resulting maps will be lazy.

foldl
:: (a -> b -> a) -> a -> Map k b -> a

foldl
:: (a -> b -> a) -> a -> Map k b -> a

Module
Lazy

An efficient implementation of ordered maps from keys to values (dictionaries).

API of this module is strict in the keys, but lazy in the values.
If you need value-strict maps, use Data.Map.Strict instead.
The `Map`

type itself is shared between the lazy and strict modules,
meaning that the same `Map`

value can be passed to functions in
both modules (although that is rarely needed).

These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.

import qualified Data.Map.Lazy as Map

The implementation of `Map`

is based on *size balanced* binary trees (or
trees of *bounded balance*) as described by:

- Stephen Adams, "
*Efficient sets: a balancing act*", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/. - J. Nievergelt and E.M. Reingold,
"
*Binary search trees of bounded balance*", SIAM journal of computing 2(1), March 1973.

Note that the implementation is *left-biased* -- the elements of a
first argument are always preferred to the second, for example in
`union`

or `insert`

.

Operation comments contain the operation time complexity in the Big-O notation (http://en.wikipedia.org/wiki/Big_O_notation).

showTreeWith
:: (k -> a -> String) -> Bool -> Bool -> Map k a -> String

*O(n)*. The expression (

) shows
the tree that implements the map. Elements are shown using the `showTreeWith`

showelem hang wide map`showElem`

function. If `hang`

is
`True`

, a *hanging* tree is shown otherwise a rotated tree is shown. If
`wide`

is `True`

, an extra wide version is shown.

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,())

showTreeWith
:: (k -> a -> String) -> Bool -> Bool -> Map k a -> String

*O(n)*. The expression (

) shows
the tree that implements the map. Elements are shown using the `showTreeWith`

showelem hang wide map`showElem`

function. If `hang`

is
`True`

, a *hanging* tree is shown otherwise a rotated tree is shown. If
`wide`

is `True`

, an extra wide version is shown.

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,())

foldlWithKey
:: (a -> k -> b -> a) -> a -> Map k b -> a

*O(n)*. Fold the keys and values in the map using the given left-associative
binary operator, such that

.
`foldlWithKey`

f z == `foldl`

(\z' (kx, x) -> f z' kx x) z . `toAscList`

For example,

keys = reverse . foldlWithKey (\ks k x -> k:ks) []

let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")" foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"

foldrWithKey
:: (k -> a -> b -> b) -> b -> Map k a -> b

*O(n)*. Fold the keys and values in the map using the given right-associative
binary operator, such that

.
`foldrWithKey`

f z == `foldr`

(`uncurry`

f) z . `toAscList`

For example,

keys map = foldrWithKey (\k x ks -> k:ks) [] map

let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")" foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"

foldrWithKey
:: (k -> a -> b -> b) -> b -> Map k a -> b

*O(n)*. Fold the keys and values in the map using the given right-associative
binary operator, such that

.
`foldrWithKey`

f z == `foldr`

(`uncurry`

f) z . `toAscList`

For example,

keys map = foldrWithKey (\k x ks -> k:ks) [] map

let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")" foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"

foldlWithKey
:: (a -> k -> b -> a) -> a -> Map k b -> a

*O(n)*. Fold the keys and values in the map using the given left-associative
binary operator, such that

.
`foldlWithKey`

f z == `foldl`

(\z' (kx, x) -> f z' kx x) z . `toAscList`

For example,

keys = reverse . foldlWithKey (\ks k x -> k:ks) []

let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")" foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"

foldWithKey
:: (k -> a -> b -> b) -> b -> Map k a -> b

*Deprecated.* As of version 0.4, replaced by `foldrWithKey`

.

*O(n)*. Fold the keys and values in the map using the given right-associative
binary operator. This function is an equivalent of `foldrWithKey`

and is present
for compatibility only.

null
:: Map k a -> Bool

containers - Data.Map.Lazy Data.Map.Strict

*O(1)*. Is the map empty?

Data.Map.null (empty) == True Data.Map.null (singleton 1 'a') == False

foldMapWithKey
:: (k -> a -> m) -> Map k a -> m

*O(n)*. Fold the keys and values in the map using the given monoid, such that

`foldMapWithKey`

f =`fold`

.`mapWithKey`

f

This can be an asymptotically faster than `foldrWithKey`

or `foldlWithKey`

for some monoids.