[Haskell-beginners] Beginners Digest, Vol 45, Issue 35

[Chaddaï Fouché]

The evident solution is :

> unique xs = [x | x <- xs, isIn x xs 2]
>
> isIn _ _ 0 = True
> isIn _ [] _ = False
> isIn y (x:xs) n
> 	| y == x    = isIn y xs (n-1)
> 	| otherwise = isIn y xs n

which is quite obviously O(n^2)... (same idea but just a bit faster
than Lorenzo one-liner)
The solution proposed here is slightly better : for each element,
either he is unique and then it is useless to compare the following
elements to it, either he isn't and so none of his subsequent
occurrences may be unique, we may proceed with the tail of the list
without these occurrences. Note that the second solution of franco00
is wrong because it doesn't remove the subsequent occurrences. Still
it is O(n^2) as a sum(k from k=n to k=1).

Still, we can get better : O(n log n) with a solution based on a sort
or Data.Map :

> unique xs = nub (sort xs)

-- 
Jedaï