[Haskell-cafe] Short and sweet

Andrew Coppin andrewcoppin at btinternet.com
Sat May 19 04:20:05 EDT 2007


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) ++ [x] ++ 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



More information about the Haskell-Cafe mailing list