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"?
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
