Proposal: Add Data.List.sortNub and sortNubBy

Ian Lynagh igloo at earth.li
Tue Mar 13 20:09:41 EDT 2007


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



More information about the Libraries mailing list