Erlang：这可以没有列表吗？ [英] Erlang: Can this be done without lists:reverse?
问题描述
映射函数，其原理如下： ％Map：通过函数映射列表中的所有元素
map（List，Fun） - >地图（列表，趣味，[]）。
map（[]，_，Acc） - >列表：反向（ACC）;
地图（[H | T]，Fun，Acc） - >地图（T，趣味，[趣（H）|度Acc]）。
我的问题是：通过递归函数建立列表感觉错误，然后反转最后。有没有办法以正确的顺序建立清单，所以我们不需要相反的？
为了了解为什么累积和倒转相当快，您必须了解Erlang中的列表是如何构建的。 Erlangs列表像Lisp中的列表是由 cons cells 构建的（查看链接中的图片）
在像Erlang列表这样的单链接列表中，添加元素（或 列表）非常便宜。这是 List = [H | T] 构造。
反转由cons构成的单链表单元格是相当快的，因为您只需要一个列表中的一个通行证，只需将下一个元素添加到已经反转的部分结果。正如已经提到的，它也在Erlang中的C中实现。
同样以相反的顺序构建结果通常可以通过尾递归函数来实现，这意味着没有堆栈被建立，（仅在Erlang的旧版本中），因此可以保存一些内存。
Erlang性能的八大神话之一，总是更好地构建在一个尾递归函数中反向调用，最后调用列表：reverse / 1 。
这是一个没有列表的正文递归版本：reverse / 1 这将在12之前的Erlang版本上使用更多内存但目前的版本不是这样：
map（[H | T]，Fun））>
[Fun（H）| map（T，Fun）];
map（[]，_） - > []。
这里是使用列表推导的地图版本：
map（List，Fun） - >
[Fun（X）|| X< - 列表]。
正如你所看到的那样简单，因为 map 只是列表理解的一部分，所以你可以直接使用list comprehension，而不需要 map 。
作为一个额外的纯Erlang实现，显示如何反转一个cons单元列表更有效率（在Erlang它总是更快地调用列表：reverse / 1 因为它是在C，但做同样的事情）。
reverse（List） - >
reverse（List，[]）。
reverse（[H | T]，Acc） - >
reverse（T，[H | Acc]）;
reverse（[]，Acc） - >
加
如您所见，只有 [A | B] 在列表中执行操作，将cons细胞分开（模式匹配时），并在执行 [H | Acc] 时构建新的操作。
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 ?
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].
这篇关于Erlang：这可以没有列表吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
