# Proposal: Add Data.List.sortNub and sortNubBy

John Meacham john at repetae.net
Mon Mar 12 23:43:25 EDT 2007

```On Mon, Mar 12, 2007 at 08:25:07PM -0700, Stefan O'Rear wrote:
> On Tue, Mar 13, 2007 at 03:16:44AM +0000, Neil Mitchell wrote:
> > Hi,
> >
> >
> > 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?

not only does it preserve order, but it works on infinite lists and is
lazy :)

John

--
John Meacham - ⑆repetae.net⑆john⑈
```