Module FiniteMap

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

FM

Constructors:

Exported operations:

 emptyFM :: (a -> a -> Bool) -> FM a b    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 :: (a -> a -> Bool) -> a -> b -> FM a b    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 :: (a -> a -> Bool) -> [(a,b)] -> FM a b    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 :: FM a b -> a -> b -> FM a b    Throws away any previous binding and stores the new one given.
 addListToFM :: FM a b -> [(a,b)] -> FM 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
 addToFM_C :: (a -> a -> a) -> FM b a -> b -> a -> FM b a    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 :: (a -> a -> a) -> FM b a -> [(b,a)] -> FM b a    Combine with a list of tuples (key,element), cf. addToFM_C
 delFromFM :: FM a b -> a -> FM a b    Deletes key from finite map. Deletion doesn't complain if you try to delete something which isn't there
 delListFromFM :: FM a b -> [a] -> FM a b    Deletes a list of keys from finite map. Deletion doesn't complain if you try to delete something which isn't there
 updFM :: FM a b -> a -> (b -> b) -> FM a b    Applies a function to element bound to given key.
 splitFM :: FM a b -> a -> Maybe (FM a b,(a,b))    Combines delFrom and lookup.
 plusFM :: FM a b -> FM a b -> FM a b    Efficiently add key/element mappings of two maps into a single one. Bindings in right argument shadow those in the left
 plusFM_C :: (a -> a -> a) -> FM b a -> FM b a -> FM b a    Efficiently combine key/element mappings of two maps into a single one, cf. addToFM_C
 minusFM :: FM a b -> FM a b -> FM a b    (minusFM a1 a2) deletes from a1 any bindings which are bound in a2
 intersectFM :: FM a b -> FM a b -> FM a b    Filters only those keys that are bound in both of the given maps. The elements will be taken from the second map.
 intersectFM_C :: (a -> b -> c) -> FM d a -> FM d b -> FM d c    Filters only those keys that are bound in both of the given maps and combines the elements as in addToFM_C.
 foldFM :: (a -> b -> c -> c) -> c -> FM a b -> c    Folds finite map by given function.
 mapFM :: (a -> b -> c) -> FM a b -> FM a c    Applies a given function on every element in the map.
 filterFM :: (a -> b -> Bool) -> FM a b -> FM a b    Yields a new finite map with only those key/element pairs matching the given predicate.
 sizeFM :: FM a b -> Int    How many elements does given map contain? Further infos: solution complete, i.e., able to compute all solutions
 eqFM :: FM a b -> FM a b -> Bool    Do two given maps contain the same key/element pairs?
 isEmptyFM :: FM a b -> Bool    Is the given finite map empty?
 elemFM :: a -> FM a b -> Bool    Does given map contain given key?
 lookupFM :: FM a b -> a -> Maybe b    Retrieves element bound to given key
 lookupWithDefaultFM :: FM a b -> b -> a -> b    Retrieves element bound to given key. If the element is not contained in map, return default value.
 keyOrder :: FM a b -> a -> a -> Bool    Retrieves the ordering on which the given finite map is built. Further infos: solution complete, i.e., able to compute all solutions
 minFM :: FM a b -> Maybe (a,b)    Retrieves the smallest key/element pair in the finite map according to the basic key ordering.
 maxFM :: FM a b -> Maybe (a,b)    Retrieves the greatest key/element pair in the finite map according to the basic key ordering.
 fmToList :: FM a b -> [(a,b)]    Builds a list of key/element pairs. The list is ordered by the initially given irreflexive order predicate on keys.
 keysFM :: FM a b -> [a]    Retrieves a list of keys contained in finite map. The list is ordered by the initially given irreflexive order predicate on keys.
 eltsFM :: FM a b -> [b]    Retrieves a list of elements contained in finite map. The list is ordered by the initially given irreflexive order predicate on keys.
 fmToListPreOrder :: FM 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
 fmSortBy :: (a -> a -> Bool) -> [a] -> [a]    Sorts a given list by inserting and retrieving from finite map. Duplicates are deleted.
 showFM :: FM a b -> String    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 :: (a -> a -> Bool) -> String -> FM a b    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.