Status of nubOrd (Proposal #2629)

[Leon Smith]

On Wed, Feb 24, 2010 at 3:23 PM, Gwern Branwen <gwern0 at gmail.com> 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.

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