Erlang: Can this be done without lists:reverse?

Question

I am a beginner learning Erlang. After reading about list comprehensions and recursion in Erlang, I wanted to try to implement my own map function, which turned out like this:

% Map: Map all elements in a list by a function
map(List,Fun) -> map(List,Fun,[]).
map([],_,Acc) -> lists:reverse(Acc);
map([H|T],Fun,Acc) -> map(T,Fun,[Fun(H)|Acc]).

My question is: It feels wrong to build up a list through the recursive function, and then reverse it at the end. Is there any way to build up the list in the right order, so we don't need the reverse ?

Answer 1

In oder to understand why accumulating and reversing is quite fast you have to understand how lists are build in Erlang. Erlangs lists like those in Lisp are build out of cons cells (look at the picture in the link).

In a singly linked list like the Erlang lists it is very cheap to prepend a element (or a short list). This is was the List = [H|T] construct does.

Reversing a singly linked list made of cons cells is quite fast since you only need one pass along the list, just prepending the next element to you already reversed partial result. And as was already mentioned, it is also implemented in C in Erlang.

Also building a result in reverse order often can be accomplished by a tail recursive function which means that no stack is built up and (in old versions of Erlang only!) therefore some memory can be saved.

Having said all this: it is one of The Eight Myths of Erlang Performance that it is always better to build in reverse in a tail recursive function and call lists:reverse/1 at the end.

Here is a body recursive version without lists:reverse/1 this would use more memory on Erlang versions before 12 but not so on current versions:

map([H|T], Fun) ->
    [ Fun(H) | map(T,Fun) ];
map([],_) -> [].

And here is a version of map using list comprehensions:

map(List, Fun) ->
    [ Fun(X) || X <- List ].

As you can see this is so simple because map is just a built in part of the list comprehension, so you would use the list comprehension directly and have no need for map anymore.

As an extra a pure Erlang implementation that shows how reversing a list of cons cells wors efficiently (in Erlang its always faster to call lists:reverse/1 because it is in C, but does the same thing).

reverse(List) ->
    reverse(List, []).

reverse([H|T], Acc) ->
    reverse(T, [H|Acc]);
reverse([], Acc) ->
    Acc.

As you can see there are only [A|B] operations on the list, taking cons cells apart (when pattern matching) and building new when doing the [H|Acc].