Erlang:这可以在没有 list:reverse 的情况下完成吗？

Question

我是学习 Erlang 的初学者。在阅读了 Erlang 中的列表推导式和递归之后，我想尝试实现我自己的 map函数，结果是这样的:

% 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]).

我的问题是:通过递归函数建立一个列表，然后在最后反转它，感觉是错误的。有没有办法以正确的顺序建立列表，所以我们不需要相反的？

Answer 1

为了理解为什么累加和反转非常快，您必须了解列表是如何在 Erlang 中构建的。类似于 Lisp 中的 Erlang 列表是基于 cons cells 构建的(查看链接中的图片)。

在像 Erlang 列表这样的单向链表中，在前面添加一个元素(或一个短列表)是非常便宜的。这是 List = [H|T]构造。

反转由 cons 单元组成的单链表非常快，因为您只需要遍历列表一次，只需将下一个元素添加到您已经反转部分结果的前面。正如已经提到的，它也在 Erlang 中用 C 实现。

此外，以相反的顺序构建结果通常可以通过尾递归函数来完成，这意味着不会构建堆栈(仅在旧版本的 Erlang 中!)因此可以节省一些内存。

说了这么多:它是 The Eight Myths of Erlang Performance 之一最好在尾递归函数中反向构建并调用 lists:reverse/1在末尾。

这是一个没有 lists:reverse/1 的主体递归版本这将在 12 之前的 Erlang 版本上使用更多内存，但在当前版本上则不然:

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

这是使用列表推导式的 map 版本:

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

正如你所看到的，这很简单，因为 map只是列表理解的内置部分，因此您可以直接使用列表理解而无需 map了。

作为一个额外的纯 Erlang 实现，它显示了如何有效地反转 cons 单元列表(在 Erlang 中调用 lists:reverse/1 总是更快，因为它是在 C 中，但做同样的事情)。

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

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

如您所见，只有 [A|B]列表上的操作，将 cons 单元分开(模式匹配时)并在执行 [H|Acc] 时构建新单元格.