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.

--      BUILDING
emptyFM         :: FiniteMap key elt
singletonFM     :: 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
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]