Finding unique elements of a list
Fri Dec 3 14:37:27 CET 2004
The optimization leads to (with renaming)
(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?
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([X|Xs]) ->
> [X|drop(X, Xs)];
> rem_dups() ->
> drop(X, [X|Xs]) ->
> drop(X, Xs);
> drop(X, Ys) ->
> The code above seems to work, but could be optimized
> further; which is left as an exercise to the reader.
> Do you Yahoo!?
> Meet the all-new My Yahoo! - Try it today!
More information about the erlang-questions