Efficient list rotation
Mon Apr 18 06:56:20 CEST 2005
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.
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.
More information about the erlang-questions