Proposal: Add Data.List.sortNub and sortNubBy
stefanor at cox.net
Mon Mar 12 23:25:07 EDT 2007
On Tue, Mar 13, 2007 at 03:16:44AM +0000, Neil Mitchell wrote:
> 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
> , 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
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?
More information about the Libraries