Proposal: Add Data.List.sortNub and sortNubBy

[Stefan O'Rear]

On Tue, Mar 13, 2007 at 03:16:44AM +0000, 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.

ordNub = flip evalState S.empty . filterM (State . tst)
 where tst x st = (not $ S.member x st, S.insert x st)

ordNub ls = ordNub' ls S.empty
 where
  ordNub' (x:xs) set | S.member x set = ordNub' xs set
                     | otherwise      = x : ordNub' xs (S.insert x set)
  ordNub' [] set = []

O(n log n), doesn't change order.  Perhaps also worthy?

Stefan