Haskell Hierarchical Libraries (base package)ContentsIndex
Data.FiniteMap
Portability portable
Stability provisional
Maintainer libraries@haskell.org
Contents
The FiniteMap type
Construction
Lookup operations
Adding elements
Deleting elements
Combination
Extracting information
Other operations
Description
A finite map implementation, derived from the paper: Efficient sets: a balancing act, S. Adams, Journal of functional programming 3(4) Oct 1993, pp553-562
Synopsis
data FiniteMap key elt
emptyFM :: FiniteMap key elt
unitFM :: key -> elt -> FiniteMap key elt
listToFM :: Ord key => [(key, elt)] -> FiniteMap key elt
lookupFM :: Ord key => FiniteMap key elt -> key -> Maybe elt
lookupWithDefaultFM :: Ord key => FiniteMap key elt -> elt -> key -> elt
elemFM :: Ord key => key -> FiniteMap key elt -> Bool
addToFM :: Ord key => FiniteMap key elt -> key -> elt -> FiniteMap key elt
addToFM_C :: Ord key => (elt -> elt -> elt) -> FiniteMap key elt -> key -> elt -> FiniteMap key elt
addListToFM :: Ord key => FiniteMap key elt -> [(key, elt)] -> FiniteMap key elt
addListToFM_C :: Ord key => (elt -> elt -> elt) -> FiniteMap key elt -> [(key, elt)] -> FiniteMap key elt
delFromFM :: Ord key => FiniteMap key elt -> key -> FiniteMap key elt
delListFromFM :: Ord key => FiniteMap key elt -> [key] -> FiniteMap key elt
plusFM :: Ord key => FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt
plusFM_C :: Ord key => (elt -> elt -> elt) -> FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt
fmToList :: FiniteMap key elt -> [(key, elt)]
keysFM :: FiniteMap key elt -> [key]
eltsFM :: FiniteMap key elt -> [elt]
sizeFM :: FiniteMap key elt -> Int
isEmptyFM :: FiniteMap key elt -> Bool
minusFM :: Ord key => FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt
foldFM :: (key -> elt -> a -> a) -> a -> FiniteMap key elt -> a
intersectFM :: Ord key => FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt
intersectFM_C :: Ord key => (elt1 -> elt2 -> elt3) -> FiniteMap key elt1 -> FiniteMap key elt2 -> FiniteMap key elt3
mapFM :: (key -> elt1 -> elt2) -> FiniteMap key elt1 -> FiniteMap key elt2
filterFM :: Ord key => (key -> elt -> Bool) -> FiniteMap key elt -> FiniteMap key elt
foldFM_GE :: Ord key => (key -> elt -> a -> a) -> a -> key -> FiniteMap key elt -> a
fmToList_GE :: Ord key => FiniteMap key elt -> key -> [(key, elt)]
keysFM_GE :: Ord key => FiniteMap key elt -> key -> [key]
eltsFM_GE :: Ord key => FiniteMap key elt -> key -> [elt]
The FiniteMap type
data FiniteMap key elt
A mapping from keys to elts.
Instances
(Eq key, Eq elt) => Eq (FiniteMap key elt)
Construction
emptyFM :: FiniteMap key elt
An empty FiniteMap.
unitFM :: key -> elt -> FiniteMap key elt
A FiniteMap containing a single mapping
listToFM :: Ord key => [(key, elt)] -> FiniteMap key elt
Makes a FiniteMap from a list of (key,value) pairs. In the case of duplicates, the last is taken
Lookup operations
lookupFM :: Ord key => FiniteMap key elt -> key -> Maybe elt
Looks up a key in a FiniteMap, returning Just v if the key was found with value v, or Nothing otherwise.
lookupWithDefaultFM :: Ord key => FiniteMap key elt -> elt -> key -> elt
Looks up a key in a FiniteMap, returning elt if the specified key was not found.
elemFM :: Ord key => key -> FiniteMap key elt -> Bool
Returns True if the specified key has a mapping in this FiniteMap, or False otherwise.
Adding elements
addToFM :: Ord key => FiniteMap key elt -> key -> elt -> FiniteMap key elt
Adds an element to a FiniteMap. Any previous mapping with the same key is overwritten.
addToFM_C :: Ord key => (elt -> elt -> elt) -> FiniteMap key elt -> key -> elt -> FiniteMap key elt
Adds an element to a FiniteMap. If there is already an element with the same key, then the specified combination function is used to calculate the new value. The already present element is passed as the first argument and the new element to add as second.
addListToFM :: Ord key => FiniteMap key elt -> [(key, elt)] -> FiniteMap key elt
Adds a list of elements to a FiniteMap, in the order given in the list. Overwrites previous mappings.
addListToFM_C :: Ord key => (elt -> elt -> elt) -> FiniteMap key elt -> [(key, elt)] -> FiniteMap key elt
A list version of addToFM_C. The elements are added in the order given in the list.
Deleting elements
delFromFM :: Ord key => FiniteMap key elt -> key -> FiniteMap key elt
Deletes an element from a FiniteMap. If there is no element with the specified key, then the original FiniteMap is returned.
delListFromFM :: Ord key => FiniteMap key elt -> [key] -> FiniteMap key elt
List version of delFromFM.
Combination
plusFM :: Ord key => FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt
Combine two FiniteMaps. Mappings in the second argument shadow those in the first.
plusFM_C :: Ord key => (elt -> elt -> elt) -> FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt
Combine two FiniteMaps. The specified combination function is used to calculate the new value when there are two elements with the same key.
Extracting information
fmToList :: FiniteMap key elt -> [(key, elt)]
Convert a FiniteMap to a [(key, elt)] sorted by Ord key
keysFM :: FiniteMap key elt -> [key]

Extract the keys from a FiniteMap, in the order of the keys, so

 keysFM == map fst . fmToList
eltsFM :: FiniteMap key elt -> [elt]

Extract the elements from a FiniteMap, in the order of the keys, so

 eltsFM == map snd . fmToList
sizeFM :: FiniteMap key elt -> Int
isEmptyFM :: FiniteMap key elt -> Bool
Other operations
minusFM :: Ord key => FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt
(minusFM a1 a2) deletes from a1 any mappings which are bound in a2
foldFM :: (key -> elt -> a -> a) -> a -> FiniteMap key elt -> a
intersectFM :: Ord key => FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt
(intersectFM a1 a2) returns a new FiniteMap containing mappings from a1 for which a2 also has a mapping with the same key.
intersectFM_C :: Ord key => (elt1 -> elt2 -> elt3) -> FiniteMap key elt1 -> FiniteMap key elt2 -> FiniteMap key elt3
Returns the interesction of two mappings, using the specified combination function to combine values.
mapFM :: (key -> elt1 -> elt2) -> FiniteMap key elt1 -> FiniteMap key elt2
filterFM :: Ord key => (key -> elt -> Bool) -> FiniteMap key elt -> FiniteMap key elt
foldFM_GE :: Ord key => (key -> elt -> a -> a) -> a -> key -> FiniteMap key elt -> a
Fold through all elements greater than or equal to the supplied key, in increasing order.
fmToList_GE :: Ord key => FiniteMap key elt -> key -> [(key, elt)]
List elements greater than or equal to the supplied key, in increasing order
keysFM_GE :: Ord key => FiniteMap key elt -> key -> [key]
List keys greater than or equal to the supplied key, in increasing order
eltsFM_GE :: Ord key => FiniteMap key elt -> key -> [elt]
List elements corresponding to keys greater than or equal to the supplied key, in increasing order of key.
Produced by Haddock version 0.6