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

Paulo Sérgio Almeida <>
Tue Jun 24 21:45:24 CEST 2008


This is one of those cases where it is not necessarily better to use 
tail calls; one must measure what happens. Here are two versions:

Body recursive:

remove(_, []) -> [];
remove(1, [_|T]) -> T;
remove(N, [H|T]) -> [H | remove(N-1, T)].

Tail recursive:

remove2(N, L) -> remove2(N, L, []).
remove2(_, [], Acc) -> lists:reverse(Acc);
remove2(1, [_|T], Acc) -> lists:reverse(Acc, T);
remove2(N, [H|T], Acc) -> remove2(N-1, T, [H|Acc]).

The second one seems to be better for removing near the end of a large 
list, due to lists:reverse being builtin.

Regards,
Paulo

Nick Gerakines wrote:
> There might be a better way to do it, but this is what I use:
> 
> -module(remelem).
> -compile(export_all).
> 
> remove_element(1, List) ->
>     [_ | TheRest] = List, TheRest;
> remove_element(ElemPos, List) when length(List) == ElemPos ->
>     [_ | TheRest] = lists:reverse(List), lists:reverse(TheRest);
> remove_element(ElemPos, List) ->
>     {ListA, ListB} = lists:split(ElemPos - 1, List),
>     [_, ElemB | ListC] = ListB,
>     ListResB = [ElemB | ListC],
>     ListA ++ ListResB.
> 
> # Nick Gerakines
> 
> On Tue, Jun 24, 2008 at 7:51 AM, Jesper Louis Andersen
> <> wrote:
>> On Tue, Jun 24, 2008 at 4:40 PM, anupamk <> wrote:
>>> hi all,
>>>
>>> can you please let me know what would be a more efficient approach to
>>> removing nth element from a list.
>> If your list is rather small, say N < 20, then I would suggest you use
>> something along the
>> lines of your first implementation. If your list is extremely big and
>> performance matters, then
>> I suggest you look for another data structure. With a list there is
>> only so much you can do: You
>> have to dig into the list in order to get to the Nth element and that
>> will cost you O(n).
>> _______________________________________________
>> erlang-questions mailing list
>> 
>> http://www.erlang.org/mailman/listinfo/erlang-questions
>>
> _______________________________________________
> erlang-questions mailing list
> 
> http://www.erlang.org/mailman/listinfo/erlang-questions
> 




More information about the erlang-questions mailing list