# Module Data.FiniteMap

IMPORTANT NOTE: This library is deprecated and included only for compatibility with older programs. Use library `Data.Map` (in package `containers`) instead!

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: January 2019

## 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 :: Eq a => (a -> a -> Bool) -> [(a,b)] -> FM a b``` Builts a finite map from given list of tuples (key,element). ```addToFM :: Eq a => FM a b -> a -> b -> FM a b``` Throws away any previous binding and stores the new one given. ```addListToFM :: Eq a => FM a b -> [(a,b)] -> FM a b``` Throws away any previous bindings and stores the new ones given. ```addToFM_C :: Eq a => (b -> b -> b) -> FM a b -> a -> b -> FM a b``` Instead of throwing away the old binding, addToFM_C combines the new element with the old one. ```addListToFM_C :: Eq a => (b -> b -> b) -> FM a b -> [(a,b)] -> FM a b``` Combine with a list of tuples (key,element), cf. ```delFromFM :: Eq a => FM a b -> a -> FM a b``` Deletes key from finite map. ```delListFromFM :: Eq a => FM a b -> [a] -> FM a b``` Deletes a list of keys from finite map. ```updFM :: Eq a => FM a b -> a -> (b -> b) -> FM a b``` Applies a function to element bound to given key. ```splitFM :: Eq a => FM a b -> a -> Maybe (FM a b,(a,b))``` Combines delFrom and lookup. ```plusFM :: Eq a => FM a b -> FM a b -> FM a b``` Efficiently add key/element mappings of two maps into a single one. ```plusFM_C :: Eq a => (b -> b -> b) -> FM a b -> FM a b -> FM a b``` Efficiently combine key/element mappings of two maps into a single one, cf. ```minusFM :: Eq a => FM a b -> FM a b -> FM a b``` (minusFM a1 a2) deletes from a1 any bindings which are bound in a2 ```intersectFM :: Eq a => FM a b -> FM a b -> FM a b``` Filters only those keys that are bound in both of the given maps. ```intersectFM_C :: Eq a => (b -> c -> d) -> FM a b -> FM a c -> FM a d``` 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 :: Eq a => (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 :: (Eq a, Eq b) => 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 :: Eq a => a -> FM a b -> Bool``` Does given map contain given key? ```lookupFM :: Eq a => FM a b -> a -> Maybe b``` Retrieves element bound to given key ```lookupWithDefaultFM :: Eq a => 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 :: Eq a => (a -> a -> Bool) -> [a] -> [a]``` Sorts a given list by inserting and retrieving from finite map. ```showFM :: (Show a, Show b) => FM a b -> String``` Transforms a finite map into a string. ```readFM :: (Read a, Read b) => (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 :: Eq a => (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 :: Eq a => FM a b -> a -> b -> FM a b``` Throws away any previous binding and stores the new one given.
 ```addListToFM :: Eq a => 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 :: Eq a => (b -> b -> b) -> FM a b -> a -> b -> FM a b``` 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 :: Eq a => (b -> b -> b) -> FM a b -> [(a,b)] -> FM a b``` Combine with a list of tuples (key,element), cf. addToFM_C
 ```delFromFM :: Eq a => 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 :: Eq a => 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 :: Eq a => FM a b -> a -> (b -> b) -> FM a b``` Applies a function to element bound to given key.
 ```splitFM :: Eq a => FM a b -> a -> Maybe (FM a b,(a,b))``` Combines delFrom and lookup.
 ```plusFM :: Eq a => 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 :: Eq a => (b -> b -> b) -> FM a b -> FM a b -> FM a b``` Efficiently combine key/element mappings of two maps into a single one, cf. addToFM_C
 ```minusFM :: Eq a => FM a b -> FM a b -> FM a b``` (minusFM a1 a2) deletes from a1 any bindings which are bound in a2
 ```intersectFM :: Eq a => 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 :: Eq a => (b -> c -> d) -> FM a b -> FM a c -> FM a d``` 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 :: Eq a => (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 :: (Eq a, Eq b) => 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 :: Eq a => a -> FM a b -> Bool``` Does given map contain given key?
 ```lookupFM :: Eq a => FM a b -> a -> Maybe b``` Retrieves element bound to given key
 ```lookupWithDefaultFM :: Eq a => 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 :: Eq a => (a -> a -> Bool) -> [a] -> [a]``` Sorts a given list by inserting and retrieving from finite map. Duplicates are deleted.
 ```showFM :: (Show a, Show b) => 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 :: (Read a, Read b) => (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.