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

栏目: Erlang · 发布时间: 5年前

内容简介:翻译自:https://stackoverflow.com/questions/6179469/erlang-can-this-be-done-without-listsreverse

我是初学者,学习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]).

我的问题是:通过递归函数构建列表感觉是错误的,然后在最后反转它.有没有办法按正确的顺序建立列表,所以我们不需要反过来?

为了理解为什么累积和反转非常快,你必须了解如何在Erlang中构建列表.像Lisp中的那些Erlangs列表是在 cons cells

中构建的(查看链接中的图片).

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

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

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

说完这一切: The Eight Myths of Erlang Performance 之一是在尾部递归函数和调用列表中反向构建总是更好:最后反向/ 1.

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

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

这是使用列表推导的地图版本:

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

正如你所看到的那样,这很简单,因为map只是列表推导的一部分,所以你可以直接使用list comprehension,不再需要map.

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

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

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

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

翻译自:https://stackoverflow.com/questions/6179469/erlang-can-this-be-done-without-listsreverse


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

ACM/ICPC程序设计与分析

ACM/ICPC程序设计与分析

沈云付 / 清华大学 / 2010-7 / 39.50元

《ACM/ICPC程序设计与分析(C++实现)》介绍ACM国际大学生程序设计竞赛概况及程序设计基础,系统介绍数论、组合数学、动态规划、计算几何、搜索、图论和网络流等专题的典型算法,挑选历年竞赛中许多有代表性的竞赛题作为例题进行分析,便于学生编程时模仿学习。每章的例题和习题都配有输入输出样例,方便学生在编程时测试与调试程序。《ACM/ICPC程序设计与分析(C++实现)》以C++为程序设计语言,以提......一起来看看 《ACM/ICPC程序设计与分析》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换