[erlang-questions] Coming Back (maybe improving lists:reverse/1)

Richard A. O'Keefe <>
Thu Oct 8 01:39:19 CEST 2015


On 8/10/2015, at 7:39 am, Ivan Carmenates Garcia <> wrote:
> So I can imagine Erlang implement lists using double linked lists for obvious purposes,

(a) Why would you imagine that?  That's a horrible thing to imagine.
(b) WHAT obvious purposes?
(c) Doubly linked lists cannot be used the way Erlang uses lists
without massive copying overheads.

> I haven’t see the source code so I am just guessing here, so for example when doing length you must spend one O(N) to transverse the list, one O(1) for each element to count them and one final O(1) to return the list.

Yes, it takes O(N) time to traverse a list.
That is also true of doubly linked lists.

> So when using lists:reverse/1 it takes four times what lengths does,

Four times *what*?  lists:reverse/1 may well be implemented in C by
now, but in Erlang we can write

    length(L) -> length_plus(L, 0).

    length_plus([_|Xs], N) -> length_plus(Xs, 1+N);
    length_plus([],     N) -> N.

    reverse(L) -> reverse_append(L, []).

    reverse_append([X|Xs], Ys) -> reverse_append(Xs, [X|Ys]);
    reverse_append([],     Ys) -> Ys.

This is a *single* traversal.  The two algorithms are essentially
the same.  Such extra cost as there is in reverse/1 compared with
length/1 has to do with allocating and initialising memory; using
doubly linked lists would only increase that cost.

> so I can play guess, and just that, that you are using indeed a double linked list so you spend one O(n) to transverse the list, three O(1), which is an O(1) in total of course I am just counting the operations as well, to swap the preview and next pointers for each node so the list will be in the reverse order and other O(1) to return the new list which is a pointer of course to the old list just reversed.

There is no changing of pointers in Erlang lists.  There is no possibility
of in-place updates of lists.  If I do

    L = [1,2,3],
    R = lists:reverse(L)

then I expect L to be completely unaltered.  No Erlang operation is
permitted to (visibly) alter any reachable value in any (detectable)
way.


More information about the erlang-questions mailing list