[Haskell-cafe] Short and sweet

Andrew Coppin andrewcoppin at btinternet.com
Fri May 18 15:31:27 EDT 2007


Neil Mitchell wrote:
> nub requires Eq and not Ord,

Indeed. I had that fact clearly in my mind while I was pondering this...

> therefore you can prove that _any_ nub, no matter how good it is, must 
> be O(n^2).

Really? (I suck at this kind of thing! Oh wait - you noticed...)

It occurs to me that if you want a sorted list of only unique elements, 
it would seem (to me) to be efficient to do the sorting and the uniquing 
at the same time. Does any library function do this? (I imagine it 
wouldn't be hard to write it yourself...)

BTW, is there any sane reason why it's called "nub" instead of... gee, I 
don't know... "unique"?



More information about the Haskell-Cafe mailing list