Haskell Core Libraries (base package)ParentContentsIndex
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
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.
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
Produced by Haddock version 0.4