[erlang-questions] re moving nth element from a list

[Richard A. O'Keefe]

On 25 Jun 2008, at 2:40 am, anupamk wrote:

> can you please let me know what would be a more efficient approach to
> removing nth element from a list.

(Have the rest of the program) pretend it is gone.

That's actually a serious reply.  More generally, why do you want to
do this?  Removing the nth element from a list is going to be O(n)
no matter what you do; perhaps some kind of tree structure would
suit your needs better.

If you were going for clarity, then

remove_nth1(List, N) ->
     remove_nth0(List, N-1).

remove_nth0(List, N) ->
     {Front, [_|Back]} = lists:split(N, List),
     Front ++ Back.

I think that's what you were trying to do with remove_nth_2/2,
but the clarity just wasn't there.  For example,
"lists:sublist(Split_right, length(Split_right))"
is a slow and confusing way of writing "Split_right".

If you were really going all out for speed, something like

remove_nth1(List, N) when integer(N), N >= 1 ->
     remove_nth0_loop(N-1, List).

remove_nth0(List, N) when integer(N), N >= 0 ->
     remove_nth0_loop(N, List).

remove_nth0_loop(N, [A,B,C,D|Xs]) when N >= 4 ->
     [A,B,C,D | remove_nth0_loop(N-4, Xs)];
remove_nth0_loop(3, [A,B,C,_|Xs]) -> [A,B,C|Xs];
remove_nth0_loop(2, [A,B,_  |Xs]) -> [A,B  |Xs];
remove_nth0_loop(1, [A,_    |Xs]) -> [A    |Xs];
remove_nth0_loop(0, [_      |Xs]) ->        Xs .

This is (currently) body-recursive, not tail-recursive
(although there is no reason in principle why it _couldn't_
be tail-recursive; the Prolog equivalent is), but if your
lists are short enough that you are willing to put up with
the function at all, they are short enough that this should
not be a problem.