Efficient list rotation

[Richard A. O'Keefe]

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) ->
	reverse_append(T, [H|R]).

This code has been tested.  It builds length(L)+length(A) cons
cells, of which length(L) are retained.