Hello!
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) ?
If it belongs to O(n), aren't the maps really really useless?
If it belongs to O(log n), how is this achieved?
(my guess is that it is O(n) of course : )
Best regards,
Magnus Lindberg
_______________________________________________
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
