containers - Data.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

containers - Data.Map  

Deprecated. As of version 0.5, replaced by foldr.

O(n). Fold the values in the map using the given right-associative binary operator. This function is an equivalent of foldr and is present for compatibility only.

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

containers - Data.Map.Lazy  

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

containers - Data.Map.Strict  

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

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

lens - Data.Map.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:

>>> Map.fromList [(1, "world")] ^.at 1
Just "world"
>>> at 1 .~ Just "world" $ Map.empty
fromList [(1,"world")]
>>> at 0 ?~ "hello" $ Map.empty
fromList [(0,"hello")]

We can traverse, fold over, and map over key-value pairs in a Map, thanks to its TraversableWithIndex, FoldableWithIndex, and FunctorWithIndex instances.

>>> imap const $ Map.fromList [(1, "Venus")]
fromList [(1,1)]
>>> ifoldMap (\i _ -> Sum i) $ Map.fromList [(2, "Earth"), (3, "Mars")]
Sum {getSum = 5}
>>> itraverse_ (curry print) $ Map.fromList [(4, "Jupiter")]
(4,"Jupiter")
>>> itoList $ Map.fromList [(5, "Saturn")]
[(5,"Saturn")]

A related class, Ixed, allows us to use ix to traverse a value at a particular key.

>>> ix 2 %~ ("New " ++) $ Map.fromList [(2, "Earth")]
fromList [(2,"New Earth")]
>>> preview (ix 8) $ Map.empty
Nothing

Additionally, Map has TraverseMin and TraverseMax instances, which let us traverse over the value at the least and greatest keys, respectively.

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

containers - Data.Map.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

containers - Data.Map.Lazy  

O(n). Fold the values in the map using the given left-associative binary operator, such that foldl f z == foldl f z . elems.

For example,

 elems = reverse . foldl (flip (:)) []
 let f len a = len + (length a)
 foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
foldl :: (a -> b -> a) -> a -> Map k b -> a

containers - Data.Map.Strict  

O(n). Fold the values in the map using the given left-associative binary operator, such that foldl f z == foldl f z . elems.

For example,

 elems = reverse . foldl (flip (:)) []
 let f len a = len + (length a)
 foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4

containers - Data.Map.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

containers - Data.Map.Lazy  

O(n). The expression (showTreeWith showelem hang wide map) shows the tree that implements the map. Elements are shown using the 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

containers - Data.Map.Strict  

O(n). The expression (showTreeWith showelem hang wide map) shows the tree that implements the map. Elements are shown using the 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

containers - Data.Map.Lazy  

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

containers - Data.Map.Lazy  

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

containers - Data.Map.Strict  

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

containers - Data.Map.Strict  

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

containers - Data.Map  

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.

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

containers - Data.Map.Lazy  

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.