| Haskell Hierarchical Libraries (base package) | Contents | Index

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
NOTE: Data.FiniteMap is DEPRECATED, please use Data.Map instead. 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 elt1 -> FiniteMap key elt2 -> FiniteMap key elt1
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]
foldFM_LE :: Ord key => (key -> elt -> a -> a) -> a -> key -> FiniteMap key elt -> a
fmToList_LE :: Ord key => FiniteMap key elt -> key -> [(key, elt)]
keysFM_LE :: Ord key => FiniteMap key elt -> key -> [key]
eltsFM_LE :: Ord key => FiniteMap key elt -> key -> [elt]
minFM :: Ord key => FiniteMap key elt -> Maybe key
maxFM :: Ord key => FiniteMap key elt -> Maybe key

The `FiniteMap` type
data FiniteMap key elt

A mapping from `key`s to `elt`s.
Instances

Typeable2 FiniteMap
Functor (FiniteMap k)
(Data a, Data b, Ord a) => Data (FiniteMap a b)
(Eq key, Eq elt) => Eq (FiniteMap key elt)
(Show k, Show e) => Show (FiniteMap k e)

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 `FiniteMap`s. 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 `FiniteMap`s. 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 elt1 -> FiniteMap key elt2 -> FiniteMap key elt1
`(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 intersection 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.
foldFM_LE :: Ord key => (key -> elt -> a -> a) -> a -> key -> FiniteMap key elt -> a
Fold through all elements less than or equal to the supplied key, in decreasing order.
fmToList_LE :: Ord key => FiniteMap key elt -> key -> [(key, elt)]
List elements greater than or equal to the supplied key, in decreasing order
keysFM_LE :: Ord key => FiniteMap key elt -> key -> [key]
List keys greater than or equal to the supplied key, in decreasing order
eltsFM_LE :: Ord key => FiniteMap key elt -> key -> [elt]
List elements corresponding to keys greater than or equal to the supplied key, in decreasing order of key.
minFM :: Ord key => FiniteMap key elt -> Maybe key
Extract minimum key, or Nothing if the map is empty.
maxFM :: Ord key => FiniteMap key elt -> Maybe key
Extract maximum key, or Nothing if the map is empty.
Produced by Haddock version 0.7