Performance horrors

Adrian Hey ahey at
Wed Aug 27 04:05:41 EDT 2008

Jeremy Shaw wrote:
> At Tue, 26 Aug 2008 08:38:45 +0100,
> Adrian Hey wrote:
>> I was looking at the definitions of nub (and hence nubBy) recently
>> in connection with a trac ticket and realised that this is O(n^2)
>> complexity! Ouch!
> Can we modify Data.List to include the big-O notation for all the
> functions similar to Data.Set, Data.Map, and bytestring?

I'm sure this is possible. I have no idea how to do this though.

Perhaps somone else can explain. But patches submitted by ordinary
users (even bug fixes) tend to languish in obscurity for some reason.
I don't even know where the source code is or if we're using darcs or
git or what these days (but I dare say I could find out if I was
sufficiently motivated :-).

Adrian Hey

More information about the Libraries mailing list