Status of nubOrd (Proposal #2629)

Gwern Branwen gwern0 at gmail.com
Mon Mar 1 14:35:33 EST 2010


On Sun, Feb 28, 2010 at 9:39 PM, Leon Smith <leon.p.smith at gmail.com> wrote:
> 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.

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


More information about the Libraries mailing list