FiniteMap performance

[Mieszko Lis]

On Fri, 2003-02-07 at 21:25, Magnus Lindberg wrote:
> I am using the FiniteMap datatype and since Haskell never modifies
> variables but rather copies them (?) I wonder what the performance of
> the FiniteMap type is in Haskell. Lookup is of course done in O(log n)
> but is insertion done in O(n) or O(log n)?
> 
> For example, does the function
> 
> addToFM	:: Ord key => FiniteMap key elt ->
>                       key -> elt  -> FiniteMap key elt
> 
> belong to O(n) or O(log n) (where n is the size of the map) ?

Insertion seems to take O(log n) time (measure it!).

This is because that you don't need to copy all the nodes in the tree --
just the nodes whose values or descendants have changed, which is
(roughly*) the path from the root of the tree to the insertion point. 
The subtrees that have not changed are safe to share even if you hold on
to the old tree, because you know they'll never be modified.

Cheers,
-- Mieszko

*modulo rotations required to keep the tree approximately balanced, but
those are along the insertion path too.