使用递归反向列表

Question

我正在写一本关于Erlang的书的例子。这是任务：不使用BIF编写反向函数。

这是我所做的：

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

这是此函数返回的内容：

(emacs@localhost)3> examples:reverse([1, 2, 3]).
[[[[],3],2],1]

我不明白如何使它返回扁平化列表[3, 2, 1]。有可能吗？

Answer 1

在语法[H | T]中，H是一个元素，T是一个列表（至少对于proplist而言），在您的代码中[reverse(T) | [H]]创建一个列表，该列表的第一个元素是结果reverse(T)，而最后一个尾部是单个元素list [H]。

如果要通过这种方式实现功能，则应使用fenollp提出的语法。

如果要编写高效的代码，则应避免对部分结果进行多次中间复制，并避免进行非尾部递归调用（以限制调用堆栈的大小：

reverse(L) -> reverse(L,[]). % use an accumulator to create a tail recursive function

reverse([],R) -> R;
reverse([H|T],R) -> reverse(T,[H|R]). % all [H|R] can be fully evaluated before recursively calling reverse
                                      % this is what is called a tail recursive function
                                      % in addition, the construction of [H|T]
                                      % does not require to make a copy of T