On Sun, Feb 28, 2010 at 9:39 PM, Leon Smith wrote:

On Wed, Feb 24, 2010 at 3:23 PM, Gwern Branwen wrote:

...

nub . sort (and the reverse) are very frequent. The attached sort.txt was produced by

   find bin/ -name "*.hs" -exec sh -c "grep sort {} | grep nub && echo {}" \; > sort.txt

It's very crude and obviously produces lots of false positives & negatives, but even so, there's at least >50 uses of nub . sort etc.

Incidentally,  data-ordlist has a nubSort implementation that's never more expensive than Data.List.sort.  It's the same mergesort algorithm provided in Data.List except that it removes duplicates as it merges the lists.

Hm. But sort was recently modified with some tricks from nhc, IIRC. Is it up to date?

The library also provides a linear-time nub and nubBy on ordered lists,  however this implementation is not used as part of nubSort.

http://hackage.haskell.org/package/data-ordlist

Best, Leon

Thanks for the pointers. I briefly looked at data-ordlist during the searching, but I didn't take the time to figure out what exactly it was doing. -- gwern