Performance horrors

[Adrian Hey]

Hello Folks,

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!

I was going to say I sure hope nobody uses this in real programs,
but I thought I'd better check first and I see that darcs seems to
use it in a few places. Hmm..

How did we ever get stuff like this in the standard libs? I can only
imagine this is relic from the days when Haskell was only used for
research or pedagogical purposes only (not for real programs).

Seeing as practically all Eq instances are also Ord instances, at
the very least we could have O(n*(log n)) definitions for ..

nub :: Ord a => [a] -> [a]
nub = nubBy compare

nubBy :: (a -> a -> Ordering) -> [a] -> [a]
nubBy cmp xs ys = -- something using an AVL tree perhaps.

..or even better using the generalised trie stuff Jamie Brandon
has been working on.

Of course I'm not actually advocating this as it's probably bad policy
to have a simple standard lib dependent on any complex non-standard lib.
But if it just isn't possible to implement some functions with
reasonable efficiency using simple definitions only then I think they
really shouldn't be there at all. Instead we should make users "roll
their own" using whatever complex non-standard lib they want.

So could nub and nubBy be deprecated and an appropriate health warning
added to the Haddock?

In the mean time I think I'll put appropriate alternative definitions
in the next AVL release and ask Jamie Brandon to consider doing the same
in his generalised tries lib (GMap).

Also, looking at a few other functions there like union(By) and
intersection(By) make me quite suspicious. Maybe we need a thorough
performance audit to get rid of implementations that are so insanely
inefficient they should *never* be used.

Regards
--
Adrian Hey