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
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. |
Constructors:
The empty finite map.
|
Construct a finite map with only a single element.
|
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.
|
Throws away any previous bindings and stores the new ones given. The items are added starting with the first one in the list |
Instead of throwing away the old binding, addToFM_C combines the new element with the old one.
|
Combine with a list of tuples (key,element), cf. addToFM_C |
Deletes key from finite map. Deletion doesn't complain if you try to delete something which isn't there |
Deletes a list of keys from finite map. Deletion doesn't complain if you try to delete something which isn't there |
Efficiently add key/element mappings of two maps into a single one. Bindings in right argument shadow those in the left |
Efficiently combine key/element mappings of two maps into a single one, cf. addToFM_C |
Filters only those keys that are bound in both of the given maps. The elements will be taken from the second map. |
Filters only those keys that are bound in both of the given maps and combines the elements as in addToFM_C. |
How many elements does given map contain?
|
Retrieves element bound to given key. If the element is not contained in map, return default value. |
Retrieves the ordering on which the given finite map is built. |
Retrieves the smallest key/element pair in the finite map according to the basic key ordering. |
Retrieves the greatest key/element pair in the finite map according to the basic key ordering. |
Builds a list of key/element pairs. The list is ordered by the initially given irreflexive order predicate on keys. |
Retrieves a list of keys contained in finite map. The list is ordered by the initially given irreflexive order predicate on keys. |
Retrieves a list of elements contained in finite map. The list is ordered by the initially given irreflexive order predicate on keys. |
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.
|
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. |