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.

Exported datatypes:


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.