Efficient list rotation

[Ulf Wiger]

Nice, although my preference in stead of reverse_append/2
would be lists:reverse([X|ReversedA]). Not that saving
3 lines of code is necessarily that important. Whatever
feels the most elegant is of course the solution to pick.

/Uffe


Den 2005-04-18 04:06:56 skrev Richard A. O'Keefe <ok@REDACTED>:

> 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.
>
>
>