3.2. The FiniteMap type

What functional programmers call a finite map, everyone else calls a lookup table.

Out code is derived from that in this paper: "S Adams "Efficient sets: a balancing act" Journal of functional programming 3(4) Oct 1993, pages 553-562" Guess what? The implementation uses balanced trees.

data FiniteMap key elt -- abstract -- BUILDING emptyFM :: FiniteMap key elt unitFM :: key -> elt -> FiniteMap key elt listToFM :: Ord key => [(key,elt)] -> FiniteMap key elt -- In the case of duplicates, the last is taken -- ADDING AND DELETING -- Throws away any previous binding -- In the list case, the items are added starting with the -- first one in the list addToFM :: Ord key => FiniteMap key elt -> key -> elt -> FiniteMap key elt addListToFM :: Ord key => FiniteMap key elt -> [(key,elt)] -> FiniteMap key elt -- Combines with previous binding -- In the combining function, the first argument is -- the "old" element, while the second is the "new" one. addToFM_C :: Ord key => (elt -> elt -> elt) -> FiniteMap key elt -> key -> elt -> FiniteMap key elt addListToFM_C :: Ord key => (elt -> elt -> elt) -> FiniteMap key elt -> [(key,elt)] -> FiniteMap key elt -- Deletion doesn't complain if you try to delete something -- which isn't there delFromFM :: Ord key => FiniteMap key elt -> key -> FiniteMap key elt delListFromFM :: Ord key => FiniteMap key elt -> [key] -> FiniteMap key elt -- COMBINING -- Bindings in right argument shadow those in the left plusFM :: Ord key => FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt -- Combines bindings for the same thing with the given function plusFM_C :: Ord key => (elt -> elt -> elt) -> FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt minusFM :: Ord key => FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt -- (minusFM a1 a2) deletes from a1 any bindings which are bound in a2 intersectFM :: Ord key => FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt intersectFM_C :: Ord key => (elt -> elt -> elt) -> FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt -- MAPPING, FOLDING, FILTERING foldFM :: (key -> elt -> a -> a) -> a -> FiniteMap key elt -> a mapFM :: (key -> elt1 -> elt2) -> FiniteMap key elt1 -> FiniteMap key elt2 filterFM :: Ord key => (key -> elt -> Bool) -> FiniteMap key elt -> FiniteMap key elt -- INTERROGATING sizeFM :: FiniteMap key elt -> Int isEmptyFM :: FiniteMap key elt -> Bool elemFM :: Ord key => key -> FiniteMap key elt -> Bool lookupFM :: Ord key => FiniteMap key elt -> key -> Maybe elt lookupWithDefaultFM :: Ord key => FiniteMap key elt -> elt -> key -> elt -- lookupWithDefaultFM supplies a "default" elt -- to return for an unmapped key -- LISTIFYING fmToList :: FiniteMap key elt -> [(key,elt)] keysFM :: FiniteMap key elt -> [key] eltsFM :: FiniteMap key elt -> [elt]