# Module Data.Map

A finite map is an efficient purely functional data structure to store a mapping from keys to values.

This version was ported from a corresponding Haskell library

Author: Frank Huch, Bernd Brassel

Version: March 2013

## Summary of exported operations:

 ```empty :: Map a b``` The empty map. ```singleton :: a -> b -> Map a b``` Construct a map with only a single element. ```fromList :: Ord a => [(a,b)] -> Map a b``` Builts a map from given list of tuples (key,element). ```insert :: Ord a => a -> b -> Map a b -> Map a b``` Throws away any previous binding and stores the new one given. ```insertWith :: Ord a => (b -> b -> b) -> a -> b -> Map a b -> Map a b``` Instead of throwing away the old binding, insertWith combines the new element with the old one. ```insertList :: Ord a => [(a,b)] -> Map a b -> Map a b``` Throws away any previous bindings and stores the new ones given. ```insertListWith :: Ord a => (b -> b -> b) -> [(a,b)] -> Map a b -> Map a b``` Combine with a list of tuples (key, element), cf. ```delete :: Ord a => a -> Map a b -> Map a b``` Deletes key from map. ```deleteAll :: Ord a => [a] -> Map a b -> Map a b``` Deletes a list of keys from map. ```adjust :: Ord a => (b -> b) -> a -> Map a b -> Map a b``` Applies a function to element bound to given key. ```splitLookup :: Ord a => a -> Map a b -> (Map a b,Maybe b,Map a b)``` Combines delFrom and lookup. ```union :: Ord a => Map a b -> Map a b -> Map a b``` Efficiently add key/element mappings of two maps into a single one. ```unionWith :: Ord a => (b -> b -> b) -> Map a b -> Map a b -> Map a b``` Efficiently combine key/element mappings of two maps into a single one, cf. ```difference :: Ord a => Map a b -> Map a c -> Map a b``` (difference a1 a2) deletes from a1 any bindings which are bound in a2 ```intersection :: Ord a => Map a b -> Map a b -> Map a b``` Filters only those keys that are bound in both of the given maps. ```intersectionWith :: Ord a => (b -> c -> d) -> Map a b -> Map a c -> Map a d``` Filters only those keys that are bound in both of the given maps and combines the elements as in insertWith. ```foldrWithKey :: (a -> b -> c -> c) -> c -> Map a b -> c``` Folds map by given function. ```mapWithKey :: (a -> b -> c) -> Map a b -> Map a c``` Applies a given function on every element in the map. ```filterWithKey :: Ord a => (a -> b -> Bool) -> Map a b -> Map a b``` Yields a new map with only those key/element pairs matching the given predicate. ```size :: Map a b -> Int``` How many elements does given map contain? ```null :: Map a b -> Bool``` Is the given finite map empty? ```member :: Ord a => a -> Map a b -> Bool``` Does given map contain given key? ```lookup :: Ord a => a -> Map a b -> Maybe b``` Retrieves element bound to given key ```findWithDefault :: Ord a => b -> a -> Map a b -> b``` Retrieves element bound to given key. ```lookupMin :: Map a b -> Maybe (a,b)``` Retrieves the smallest key/element pair in the finite map according to the basic key ordering. ```lookupMax :: Map a b -> Maybe (a,b)``` Retrieves the greatest key/element pair in the finite map according to the basic key ordering. ```toList :: Map a b -> [(a,b)]``` Builds a list of key/element pairs. ```keys :: Map a b -> [a]``` Retrieves a list of keys contained in map. ```elems :: Map a b -> [b]``` Retrieves a list of elements contained in map. ```toPreOrderList :: Map a b -> [(a,b)]``` Retrieves list of key/element pairs in preorder of the internal tree. ```sortWithMap :: Ord a => [a] -> [a]``` Sorts a given list by inserting and retrieving from map.

Map

Constructors:

## Exported operations:

 ```empty :: Map a b``` The empty map. Further infos: solution complete, i.e., able to compute all solutions
 ```singleton :: a -> b -> Map a b``` Construct a map with only a single element. Example call: `(singleton k a)` Parameters: `k` : key of `a` : the single element to form Further infos: solution complete, i.e., able to compute all solutions
 ```fromList :: Ord a => [(a,b)] -> Map a b``` Builts a map from given list of tuples (key,element). For multiple occurences of key, the last corresponding element of the list is taken.
 ```insert :: Ord a => a -> b -> Map a b -> Map a b``` Throws away any previous binding and stores the new one given.
 ```insertWith :: Ord a => (b -> b -> b) -> a -> b -> Map a b -> Map a b``` Instead of throwing away the old binding, insertWith combines the new element with the old one. Example call: `(insertWith combiner k a m)` Parameters: `combiner` : a function combining to elements `k` : the key of the elements to be combined `a` : the new element `m` : a map
 ```insertList :: Ord a => [(a,b)] -> Map a b -> Map a b``` Throws away any previous bindings and stores the new ones given. The items are added starting with the first one in the list
 ```insertListWith :: Ord a => (b -> b -> b) -> [(a,b)] -> Map a b -> Map a b``` Combine with a list of tuples (key, element), cf. insertWith
 ```delete :: Ord a => a -> Map a b -> Map a b``` Deletes key from map. Deletion doesn't complain if you try to delete something which isn't there
 ```deleteAll :: Ord a => [a] -> Map a b -> Map a b``` Deletes a list of keys from map. Deletion doesn't complain if you try to delete something which isn't there
 ```adjust :: Ord a => (b -> b) -> a -> Map a b -> Map a b``` Applies a function to element bound to given key.
 ```splitLookup :: Ord a => a -> Map a b -> (Map a b,Maybe b,Map a b)``` Combines delFrom and lookup.
 ```union :: Ord a => Map a b -> Map a b -> Map a b``` Efficiently add key/element mappings of two maps into a single one. CHANGED: Bindings in left argument shadow those in the right
 ```unionWith :: Ord a => (b -> b -> b) -> Map a b -> Map a b -> Map a b``` Efficiently combine key/element mappings of two maps into a single one, cf. insertWith
 ```difference :: Ord a => Map a b -> Map a c -> Map a b``` (difference a1 a2) deletes from a1 any bindings which are bound in a2
 ```intersection :: Ord a => Map a b -> Map a b -> Map a b``` Filters only those keys that are bound in both of the given maps. CHANGED: The elements will be taken from the first map.
 ```intersectionWith :: Ord a => (b -> c -> d) -> Map a b -> Map a c -> Map a d``` Filters only those keys that are bound in both of the given maps and combines the elements as in insertWith.
 ```foldrWithKey :: (a -> b -> c -> c) -> c -> Map a b -> c``` Folds map by given function.
 ```mapWithKey :: (a -> b -> c) -> Map a b -> Map a c``` Applies a given function on every element in the map.
 ```filterWithKey :: Ord a => (a -> b -> Bool) -> Map a b -> Map a b``` Yields a new map with only those key/element pairs matching the given predicate.
 ```size :: Map a b -> Int``` How many elements does given map contain? Further infos: solution complete, i.e., able to compute all solutions
 ```null :: Map a b -> Bool``` Is the given finite map empty?
 ```member :: Ord a => a -> Map a b -> Bool``` Does given map contain given key?
 ```lookup :: Ord a => a -> Map a b -> Maybe b``` Retrieves element bound to given key
 ```findWithDefault :: Ord a => b -> a -> Map a b -> b``` Retrieves element bound to given key. If the element is not contained in map, return default value.
 ```lookupMin :: Map a b -> Maybe (a,b)``` Retrieves the smallest key/element pair in the finite map according to the basic key ordering.
 ```lookupMax :: Map a b -> Maybe (a,b)``` Retrieves the greatest key/element pair in the finite map according to the basic key ordering.
 ```toList :: Map a b -> [(a,b)]``` Builds a list of key/element pairs. The list is ordered by the "Ord" context on keys.
 ```keys :: Map a b -> [a]``` Retrieves a list of keys contained in map. The list is ordered by the "Ord" context on keys.
 ```elems :: Map a b -> [b]``` Retrieves a list of elements contained in map. The list is ordered by the "Ord" context on keys.
 ```toPreOrderList :: Map a b -> [(a,b)]``` Retrieves list of key/element pairs in preorder of the internal tree. Useful for lists that will be retransformed into a tree or to match any elements regardless of basic order. Further infos: solution complete, i.e., able to compute all solutions
 ```sortWithMap :: Ord a => [a] -> [a]``` Sorts a given list by inserting and retrieving from map. Duplicates are deleted.