Proposal: Add Data.List.sortNub and sortNubBy

[Ian Lynagh]

On Tue, Mar 13, 2007 at 11:31:47PM +0000, Neil Mitchell wrote:
> 
> >    nubSorted :: Eq a => [a] -> [a]
> >    nubSorted (x1:x2:xs)
> >     | x1 == x2 = nubSorted (x1:xs)
> >    nubSorted (x:xs) = x : nubSorted xs
> >    nubSorted [] = []
> 
> I considered this, but nubSorted imposes a precondition, sortNub
> ensures a postcondition. As an interface goes sortNub is harder to get
> wrong.

That's all true, but I'd still prefer to have nubSorted than sortNub
:-)

> Plus sortNub is likely to be substantially more efficient than
> nubSorted . sort - to the point where nubSorted . sort is likely to be
> slower than a normal nub.

Huh? nub is quadratic, sort is (n log n) and nubSorted linear.

Unless you're talking about constant factors with very small lists, in
which case I'd like to see numbers.


Thanks
Ian