Erlang:这可以在没有列表的情况下完成:反向吗？

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中的那些Erlangs列表是由cons单元构建的(查看链接中的图片).

在像Erlang列表这样的单链表中,前置元素(或短列表)非常便宜.这是List = [H|T]构造所做的.

反转由cons单元组成的单链表是非常快的,因为你只需要在列表中传递一个,只需将下一个元素添加到已经反转的部分结果中.正如已经提到的,它也在Erlang的C中实现.

通过尾递归函数也可以实现以相反顺序构建结果,这意味着不会构建堆栈并且(仅在旧版本的Erlang中!)因此可以保存一些内存.

说完这一切:它是Erlang Performance的八大神话之一,在尾部递归函数中反向构建并lists:reverse/1在最后调用总是更好.

这是一个正文递归版本没有lists:reverse/1这将在12之前的Erlang版本上使用更多的内存,但在当前版本上不是这样:

map([H|T], Fun) ->
    [ Fun(H) | map(T,Fun) ];
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单元分开(当模式匹配时)并在执行时构建new [H|Acc].