Data.Map documentation lacks a bit of precision

Daan Leijen daan at
Tue Apr 5 01:03:01 EDT 2005

Jesper Louis Andersen wrote:

>I am not sure this is the correct mailing list. But the old Data.FiniteMap
>implementation states for the function ``addToFM'' (in the haddock
>Adds an element to a FiniteMap. Any previous mapping with the same key is 
>Whereas the equivalent ``insert'' in the new Data.Map module States:
>O(log n). Insert a new key and value in the map.
You are right, this is not very clear. Can someone on this list update 
the documentation?

The libraries for Data.Map, Data.Set, Data.IntMap, etc. are consistently 
using the following
two rules for all operations:
1) operations are left-biased 
2) the data structure comes as a last parameter

Due to (2), the signature of "insert" takes the "Map" as its last 
parameter, and therefore,
it overwrites an existing value (due to (1)). Same holds for "union" for 

I hope this helps,
-- Daan Leijen.

>I think it is good that there now is a running time asymptotic bound, but
>I do not know what happens if the (key, value) pair is already there. There
>is no information about this in the haddock documentation at all. It could
>either overwrite silently, or it could raise some kind of error. Both
>options are plausible, since one could just use ``Data.Map.adjust'' like:
>f :: Ord k -> k -> a -> Map k a -> Map k a 
>f k a fm = Data.Map.adjust (\_ -> a) k fm
>And gain the explicit behaviour. I do not currently have a GHC 6.4
>installed here, so I cannot test this behaviour, but some code I am working
>on needs to be fairly compatible. Therefore we have a layer on top of 
>Data.FiniteMap which implements the new map structure. This difference just
>caught my eye. It also makes it rather hard to update the documentation 
>myself and provide a patch. Where is the official repository located?

More information about the Libraries mailing list