Proposal: Add Data.List.sortNub and sortNubBy

Bjorn Bringert bringert at cs.chalmers.se
Wed Mar 14 04:46:32 EDT 2007


On Mar 13, 2007, at 4:16 , Neil Mitchell wrote:

> Hi,
>
> http://hackage.haskell.org/trac/ghc/ticket/1218
>
> I propose the addition of sortNub and sortNubBy.
>
> Semantically sortNub = sort . nub
>
> Practically, if you are doing both a sort and a nub, this can be  
> implemented as:
>
> sortNub = map head . group . sort
>
> This is O(n log n) [time to sort], rather than O(n^2) [time to nub].
>
> I have seen this around several times, often called snub. People have
> also used snub to mean other things, snub itself has a meaning, and
> sortNub is a more accurate name (following the concatMap tradition).
>
> I personally have defined this function at least 25 times, I suspect
> others have to. I can find 5 identical versions of it on google code
> [1], and I know google code is lying because it's missing ones it
> found earlier.
>
> Thanks
>
> Neil
>
> [1] http://www.google.com/codesearch?hl=en&lr=&q=lang%3Ahaskell+% 
> 22map+head+.+group+.+sort%22&btnG=Search

Yes! I've written those several times myself.

/Björn


More information about the Libraries mailing list