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) ++ [x] ++ qsort (filter (>x) xs)
At each step, this will ignore all elements equal to the pivot value.
On 18/05/07,
Dan Weston <westondan@imageworks.com> wrote:
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
>
>
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe