Data.Map, Data.IntMap documentation

Isaac Dupree isaacdupree at
Wed Aug 15 16:52:31 EDT 2007

Andriy Palamarchuk wrote:
> Ross, thanks a lot for the feedback.
> Sorry I'm late with the response.
> --- ross at wrote:
>> I rather liked having the complexity at the start of
>> the description:
>> it allows one to find this important information at
>> a glance.
> My rationale was that the complexity information,
> while  important, is probably one of the last things
> most of the people are looking for.
> I doubt anybody would e.g. search for all the O(log n)
> operations ;-)
> I'll keep the complexity information at the end of
> description unless there are more votes against this.

On the contrary, I have gone looking through entries solely to see their 
complexity (since I already know about what the functions _do_), 
especially when comparing two different collections or just looking. 
They are very short and I like them being the most introductory thing, 
myself.  If you know anything about what complexities the data structure 
gives for various operations, it can actually suggest quite a bit about 
what the operation does! (e.g., an O(log(n)) operation CANNOT be a map...)

Maybe it's because I have general data structures experience already 
from other languages, but... complexity is very important to me, it is 
often the first thing I want to see (it comes after the operation's name 
anyway!),  O(n) lookup is almost as bad as no lookup, O(n^2) behavior, 
say, with (++)s is generally fatal, worthy of being called a bug in my 
program. (Practical speed observations like "IntMaps are fast even with 
not so large sizes" are very important too)


More information about the Libraries mailing list