Finding unique elements of a list

[Joe Armstrong]

The optimization leads to (with renaming)

unique(Xs) ->
     remove_consequative(lists:sort(Xs)).

remove_consequative([H,H|T]) ->
     remove_consequative([H|T]);
remove_consequative([H|T]) ->
     [H|remove_consequative(T)];
remove_consequative([]) ->
     [].


   (Now this is  the way I wrote  this years ago - seems  like my brain
has an optimizing partical evaluator built-in).

   << extra prize - can you write a program which automatically transforms
the latter program to the former? >>

<<aside - question is this way of writing things even better
   or is the compiler smart enough to recognise that [H|T] does
not need rebuilding?

remove_consequative([H,X=[H|T]]) ->
     remove_consequative(X);
remove_consequative([H|T]) ->
     [H|remove_consequative(T)];
remove_consequative([]) ->
     [].

>>

   /Joe



On Thu, 2 Dec 2004, Thomas Lindgren wrote:

>
> Here is a straightforward version with good O(.):
> first sort the list, then drop consecutive duplicates.
>
> Complexity is given by the sort (assuming unit cost of
> comparing elements). O(N log N), presumably?
>
> unique(Xs) ->
>    rem_dups(lists:sort(Xs)).
>
> rem_dups([X|Xs]) ->
>    [X|drop(X, Xs)];
> rem_dups([]) ->
>    [].
>
> drop(X, [X|Xs]) ->
>    drop(X, Xs);
> drop(X, Ys) ->
>    rem_dups(Ys).
>
> The code above seems to work, but could be optimized
> further; which is left as an exercise to the reader.
>
> Best,
> Thomas
>
>
>
>
> __________________________________
> Do you Yahoo!?
> Meet the all-new My Yahoo! - Try it today!
> http://my.yahoo.com
>
>