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"?

OK, I looked up "group" and didn't see any Ord constraint analog. I give up. What is the common idiom? I was stupidly using nub even though I already have an Ord constraint. I have rewritten it to: unique :: Ord a => [a] -> [a] unique (x:y:z) = (if x < y then (x:) else id) (unique (y:z)) unique xyz = xyz uniqueSort = unique . sort but I would much rather use the "common idiom" than this dreck. Help a poor guy out? :) Dan Paul Johnson wrote:

Andrew Coppin wrote:

...

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...) Yes, although it only works on instances of Ord then, because of the sorting.

Its actually quite a common idiom, and worth figuring out for yourself. Hint: look at "group".

Paul. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Rodrigo Queiro wrote:

group collects equal elements in sublists. Thus, unique can be implemented as: unique = map head . group i.e. taking the first of each group of equal elements.

(Yet) another way of doing this, is a modified quicksort:

qsort [] = [] qsort (x:xs) = qsort (filter (x) xs)

At each step, this will ignore all elements equal to the pivot value.

Yes, both good ways to go. Note that nub, as implemented, appears that it should run faster on a sorted list anyway. (Because elem will be faster at finding an element only just added to the output list.) Note also that as someone else pointed out, you can use Data.Set to achieve the same thing with very good complexity: module Main where import Data.Set main = interact $ unlines . toAscList . fromList . words