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: July 2024

Summary of exported operations:

empty :: Map a b  Deterministic 
The empty map.
singleton :: a -> b -> Map a b  Deterministic 
Construct a map with only a single element.
fromList :: Ord a => [(a,b)] -> Map a b  Deterministic 
Builts a map from given list of tuples (key,element).
insert :: Ord a => a -> b -> Map a b -> Map a b  Deterministic 
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  Deterministic 
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  Deterministic 
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  Deterministic 
Combine with a list of tuples (key, element), cf.
delete :: Ord a => a -> Map a b -> Map a b  Deterministic 
Deletes key from map.
deleteAll :: Ord a => [a] -> Map a b -> Map a b  Deterministic 
Deletes a list of keys from map.
adjust :: Ord a => (b -> b) -> a -> Map a b -> Map a b  Deterministic 
Applies a function to element bound to given key.
splitLookup :: Ord a => a -> Map a b -> (Map a b,Maybe b,Map a b)  Deterministic 
Combines delFrom and lookup.
union :: Ord a => Map a b -> Map a b -> Map a b  Deterministic 
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  Deterministic 
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  Deterministic 
(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  Deterministic 
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  Deterministic 
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  Deterministic 
Folds map by given function.
mapWithKey :: (a -> b -> c) -> Map a b -> Map a c  Deterministic 
Applies a given function on every element in the map.
filterWithKey :: Ord a => (a -> b -> Bool) -> Map a b -> Map a b  Deterministic 
Yields a new map with only those key/element pairs matching the given predicate.
size :: Map a b -> Int  Deterministic 
How many elements does given map contain?
null :: Map a b -> Bool  Deterministic 
Is the given finite map empty?
member :: Ord a => a -> Map a b -> Bool  Deterministic 
Does given map contain given key?
lookup :: Ord a => a -> Map a b -> Maybe b  Deterministic 
Retrieves element bound to given key
findWithDefault :: Ord a => b -> a -> Map a b -> b  Deterministic 
Retrieves element bound to given key.
lookupMin :: Map a b -> Maybe (a,b)  Deterministic 
Retrieves the smallest key/element pair in the finite map according to the basic key ordering.
lookupMax :: Map a b -> Maybe (a,b)  Deterministic 
Retrieves the greatest key/element pair in the finite map according to the basic key ordering.
toList :: Map a b -> [(a,b)]  Deterministic 
Builds a list of key/element pairs.
keys :: Map a b -> [a]  Deterministic 
Retrieves a list of keys contained in map.
elems :: Map a b -> [b]  Deterministic 
Retrieves a list of elements contained in map.
toPreOrderList :: Map a b -> [(a,b)]  Deterministic 
Retrieves list of key/element pairs in preorder of the internal tree.
sortWithMap :: Ord a => [a] -> [a]  Deterministic 
Sorts a given list by inserting and retrieving from map.

Exported datatypes:


Map

Constructors:

  • Tip :: Map a b
  • Bin :: a -> b -> Int -> (Map a b) -> (Map a b) -> Map a b

Exported operations:

empty :: Map a b  Deterministic 

The empty map.

Further infos:
  • solution complete, i.e., able to compute all solutions

singleton :: a -> b -> Map a b  Deterministic 

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  Deterministic 

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  Deterministic 

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  Deterministic 

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  Deterministic 

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  Deterministic 

Combine with a list of tuples (key, element), cf. insertWith

delete :: Ord a => a -> Map a b -> Map a b  Deterministic 

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  Deterministic 

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  Deterministic 

Applies a function to element bound to given key.

splitLookup :: Ord a => a -> Map a b -> (Map a b,Maybe b,Map a b)  Deterministic 

Combines delFrom and lookup.

union :: Ord a => Map a b -> Map a b -> Map a b  Deterministic 

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  Deterministic 

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  Deterministic 

(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  Deterministic 

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  Deterministic 

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  Deterministic 

Folds map by given function.

mapWithKey :: (a -> b -> c) -> Map a b -> Map a c  Deterministic 

Applies a given function on every element in the map.

filterWithKey :: Ord a => (a -> b -> Bool) -> Map a b -> Map a b  Deterministic 

Yields a new map with only those key/element pairs matching the given predicate.

size :: Map a b -> Int  Deterministic 

How many elements does given map contain?

Further infos:
  • solution complete, i.e., able to compute all solutions

null :: Map a b -> Bool  Deterministic 

Is the given finite map empty?

member :: Ord a => a -> Map a b -> Bool  Deterministic 

Does given map contain given key?

lookup :: Ord a => a -> Map a b -> Maybe b  Deterministic 

Retrieves element bound to given key

findWithDefault :: Ord a => b -> a -> Map a b -> b  Deterministic 

Retrieves element bound to given key. If the element is not contained in map, return default value.

lookupMin :: Map a b -> Maybe (a,b)  Deterministic 

Retrieves the smallest key/element pair in the finite map according to the basic key ordering.

lookupMax :: Map a b -> Maybe (a,b)  Deterministic 

Retrieves the greatest key/element pair in the finite map according to the basic key ordering.

toList :: Map a b -> [(a,b)]  Deterministic 

Builds a list of key/element pairs. The list is ordered by the "Ord" context on keys.

keys :: Map a b -> [a]  Deterministic 

Retrieves a list of keys contained in map. The list is ordered by the "Ord" context on keys.

elems :: Map a b -> [b]  Deterministic 

Retrieves a list of elements contained in map. The list is ordered by the "Ord" context on keys.

toPreOrderList :: Map a b -> [(a,b)]  Deterministic 

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]  Deterministic 

Sorts a given list by inserting and retrieving from map. Duplicates are deleted.