Module FMInt

A finite map is an efficient purely functional data structure to store a mapping from keys to values. In order to store the mapping efficiently, an irreflexive(!) order predicate has to be given, i.e., the order predicate le should not satisfy (le x x) for some key x.

Example: To store a mapping from Int -> String, the finite map needs a Boolean predicate like (<). This version was ported from a corresponding Haskell library

Author: Frank Huch, Bernd Brassel

Version: March 2013

Summary of exported operations:

emptyFM :: FMI   
The empty finite map.
unitFM :: Int -> Int -> FMI   
Construct a finite map with only a single element.
listToFM :: [(Int,Int)] -> FMI   
Builts a finite map from given list of tuples (key,element).
addToFM :: FMI -> Int -> Int -> FMI   
Throws away any previous binding and stores the new one given.
addListToFM :: FMI -> [(Int,Int)] -> FMI   
Throws away any previous bindings and stores the new ones given.
addToFM_C :: (Int -> Int -> Int) -> FMI -> Int -> Int -> FMI   
Instead of throwing away the old binding, addToFM_C combines the new element with the old one.
addListToFM_C :: (Int -> Int -> Int) -> FMI -> [(Int,Int)] -> FMI   
Combine with a list of tuples (key,element), cf.
delFromFM :: FMI -> Int -> FMI   
Deletes key from finite map.
delListFromFM :: FMI -> [Int] -> FMI   
Deletes a list of keys from finite map.
updFM :: FMI -> Int -> (Int -> Int) -> FMI   
Applies a function to element bound to given key.
splitFM :: FMI -> Int -> Maybe (FMI,(Int,Int))   
Combines delFrom and lookup.
plusFM :: FMI -> FMI -> FMI   
Efficiently add key/element mappings of two maps into a single one.
plusFM_C :: (Int -> Int -> Int) -> FMI -> FMI -> FMI   
Efficiently combine key/element mappings of two maps into a single one, cf.
minusFM :: FMI -> FMI -> FMI   
(minusFM a1 a2) deletes from a1 any bindings which are bound in a2
intersectFM :: FMI -> FMI -> FMI   
Filters only those keys that are bound in both of the given maps.
intersectFM_C :: (Int -> Int -> Int) -> FMI -> FMI -> FMI   
Filters only those keys that are bound in both of the given maps and combines the elements as in addToFM_C.
foldFM :: (Int -> Int -> a -> a) -> a -> FMI -> a   
sizeFM :: FMI -> Int   
How many elements does given map contain?
eqFM :: FMI -> FMI -> Bool   
Do two given maps contain the same key/element pairs?
isEmptyFM :: FMI -> Bool   
Is the given finite map empty?
elemFM :: Int -> FMI -> Bool   
Does given map contain given key?
lookupFM :: FMI -> Int -> Maybe Int   
Retrieves element bound to given key
lookupWithDefaultFM :: FMI -> Int -> Int -> Int   
Retrieves element bound to given key.
keyOrder :: FMI -> Int -> Int -> Bool   
Retrieves the ordering on which the given finite map is built.
minFM :: FMI -> Maybe (Int,Int)   
Retrieves the smallest key/element pair in the finite map according to the basic key ordering.
maxFM :: FMI -> Maybe (Int,Int)   
Retrieves the greatest key/element pair in the finite map according to the basic key ordering.
fmToList :: FMI -> [(Int,Int)]   
Builds a list of key/element pairs.
keysFM :: FMI -> [Int]   
Retrieves a list of keys contained in finite map.
eltsFM :: FMI -> [Int]   
Retrieves a list of elements contained in finite map.
fmToListPreOrder :: FMI -> [(Int,Int)]   
Retrieves list of key/element pairs in preorder of the internal tree.
showFM :: FMI -> String   
Sorts a given list by inserting and retrieving from finite map.
readFM :: String -> FMI   
Transforms a string representation of a finite map into a finite map.

Exported datatypes:


FMI

Constructors:


Exported operations:

emptyFM :: FMI   

The empty finite map.

Example call:
(emptyFM le)
Parameters:
  • le : an irreflexive order predicate on the keys.
Further infos:
  • solution complete, i.e., able to compute all solutions

unitFM :: Int -> Int -> FMI   

Construct a finite map with only a single element.

Example call:
(unitFM le key elt)
Parameters:
  • le : an irreflexive order predicate on the keys.
  • key : key of
  • elt : the single element to form
Further infos:
  • solution complete, i.e., able to compute all solutions

listToFM :: [(Int,Int)] -> FMI   

Builts a finite map from given list of tuples (key,element). For multiple occurences of key, the last corresponding element of the list is taken.

Example call:
(listToFM le)
Parameters:
  • le : an irreflexive order predicate on the keys.

addToFM :: FMI -> Int -> Int -> FMI   

Throws away any previous binding and stores the new one given.

addListToFM :: FMI -> [(Int,Int)] -> FMI   

Throws away any previous bindings and stores the new ones given. The items are added starting with the first one in the list

addToFM_C :: (Int -> Int -> Int) -> FMI -> Int -> Int -> FMI   

Instead of throwing away the old binding, addToFM_C combines the new element with the old one.

Example call:
(addToFM_C combiner fm key elt)
Parameters:
  • combiner : a function combining to elements
  • fm : a finite map
  • key : the key of the elements to be combined
  • elt : the new element

addListToFM_C :: (Int -> Int -> Int) -> FMI -> [(Int,Int)] -> FMI   

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

delFromFM :: FMI -> Int -> FMI   

Deletes key from finite map. Deletion doesn't complain if you try to delete something which isn't there

delListFromFM :: FMI -> [Int] -> FMI   

Deletes a list of keys from finite map. Deletion doesn't complain if you try to delete something which isn't there

updFM :: FMI -> Int -> (Int -> Int) -> FMI   

Applies a function to element bound to given key.

splitFM :: FMI -> Int -> Maybe (FMI,(Int,Int))   

Combines delFrom and lookup.

plusFM :: FMI -> FMI -> FMI   

Efficiently add key/element mappings of two maps into a single one. Bindings in right argument shadow those in the left

plusFM_C :: (Int -> Int -> Int) -> FMI -> FMI -> FMI   

Efficiently combine key/element mappings of two maps into a single one, cf. addToFM_C

minusFM :: FMI -> FMI -> FMI   

(minusFM a1 a2) deletes from a1 any bindings which are bound in a2

intersectFM :: FMI -> FMI -> FMI   

Filters only those keys that are bound in both of the given maps. The elements will be taken from the second map.

intersectFM_C :: (Int -> Int -> Int) -> FMI -> FMI -> FMI   

Filters only those keys that are bound in both of the given maps and combines the elements as in addToFM_C.

foldFM :: (Int -> Int -> a -> a) -> a -> FMI -> a   

sizeFM :: FMI -> Int   

How many elements does given map contain?

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

eqFM :: FMI -> FMI -> Bool   

Do two given maps contain the same key/element pairs?

isEmptyFM :: FMI -> Bool   

Is the given finite map empty?

elemFM :: Int -> FMI -> Bool   

Does given map contain given key?

lookupFM :: FMI -> Int -> Maybe Int   

Retrieves element bound to given key

lookupWithDefaultFM :: FMI -> Int -> Int -> Int   

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

keyOrder :: FMI -> Int -> Int -> Bool   

Retrieves the ordering on which the given finite map is built.

minFM :: FMI -> Maybe (Int,Int)   

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

maxFM :: FMI -> Maybe (Int,Int)   

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

fmToList :: FMI -> [(Int,Int)]   

Builds a list of key/element pairs. The list is ordered by the initially given irreflexive order predicate on keys.

keysFM :: FMI -> [Int]   

Retrieves a list of keys contained in finite map. The list is ordered by the initially given irreflexive order predicate on keys.

eltsFM :: FMI -> [Int]   

Retrieves a list of elements contained in finite map. The list is ordered by the initially given irreflexive order predicate on keys.

fmToListPreOrder :: FMI -> [(Int,Int)]   

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

showFM :: FMI -> String   

Sorts a given list by inserting and retrieving from finite map. Duplicates are deleted. Transforms a finite map into a string. For efficiency reasons, the tree structure is shown which is valid for reading only if one uses the same ordering predicate.

readFM :: String -> FMI   

Transforms a string representation of a finite map into a finite map. One has two provide the same ordering predicate as used in the original finite map.