Efficient list rotation
Richard A. O'Keefe
Mon Apr 18 04:06:56 CEST 2005
Let's consider the problem abstractly first.
We are given
X - an element to look for
L - a list to look for X in
Suppose we can decompose
L = A ++ [X] ++ Z
where A is as short as possible.
Then to rotate L so that X is at the end is
to return Z ++ A ++ [X]
If we cannot decompose L that way, X does not
occur, and following usual Erlang practice,
"just let it crash".
rotate_to_end(L, X) ->
rotate_to_end_aux(L, X, ).
rotate_to_end_aux([X|Z], X, ReversedA) ->
Z ++ reverse_append(ReversedA, [X]);
rotate_to_end_aux([H|T], X, ReversedA) ->
rotate_to_end_aux(T, X, [H|ReversedA]).
reverse_append(, R) -> R;
reverse_append([H|T], R) ->
This code has been tested. It builds length(L)+length(A) cons
cells, of which length(L) are retained.
More information about the erlang-questions