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

[Ivan Carmenates Garcia]

Yes well, nothing to say about that. I was in a high moment of "foundment".
If that word even exists lol.



-----Original Message-----
From: Richard A. O'Keefe [mailto:ok@REDACTED] 
Sent: Wednesday, October 7, 2015 7:39 PM
To: Ivan Carmenates Garcia
Cc: erlang-questions@REDACTED
Subject: Re: [erlang-questions] Coming Back (maybe improving
lists:reverse/1)


On 8/10/2015, at 7:39 am, Ivan Carmenates Garcia <co7eb@REDACTED> 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.=