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.