Performance horrors

[Adrian Hey]

Gwern Branwen wrote:
> FWIW, when I tested out a number of nub/uniq definitions, the map head version performed the worst, much worse than the O(n^2) one everyone is complaining about. It's a neat definition, but not performant.

When did you try this? IIRC correctly even the old sort was O(n^2), but
someone had the sense to replace it a while ago.

With ghci now on my machine..
  length $ map head $ group $ sort [1..100000]
finishes "instantly", but..
  length $ nub [1..100000]
takes about 90 seconds.

Regards
--
Adrian Hey