list - 列表串联 “the correct”的方法(使用尾递归)

Question

我正在进行以下Erlang练习:

Write a function that, given a list of lists, will concatenate them. Example:

concatenate([[1,2,3], [], [4,five]]) ⇒ [1,2,3,4,five].

我想出了这个:

concatenate([]) ->
    [];
concatenate([[H]|Tail]) ->
    [H|concatenate(Tail)];
concatenate([[]|Tail]) ->
    concatenate(Tail);
concatenate([[H|T]|Tail]) ->
    [H|concatenate([T|Tail])].

哪个可行，但是我注意到我正在做这个 [T|Tail]事情。

第一个问题

仍然认为这是直接递归吗？

在那之后，我摆脱了那个 [T|Tail]，而是使用了一个累加器(如下所示)。

第二个问题

现在是否将第二个代码视为尾递归？

book hints使用辅助函数(第二个代码正在执行该操作)，但看起来很冗长。是因为我想念什么吗？

concatenate([]) ->
    [];
concatenate([[H]|Tail]) ->
    [H|concatenate(Tail)];
concatenate([[]|Tail]) ->
    concatenate(Tail);
concatenate([[H|T]|Tail]) ->
    [H|concatenate(T,Tail)].

concatenate([],Tail) ->
    concatenate(Tail);
concatenate([H],Tail) ->
    [H|concatenate(Tail)];
concatenate([H|T],Tail) ->
    [H|concatenate(T,Tail)].

Answer 1

正如@Yasir解释的那样，它们都不是尾递归的，但是我不必为此担心(请参阅下文)。使用辅助函数可以消除输入列表的部分重建，从而改善代码。您的代码有些冗长，可以通过删除conc/1中的一些不必要的子句并始终调用conc/2来简化:

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

conc([H|T], Rest) -> [H|conc(T, Rest)];
conc([], Rest) -> conc(rest).

然后使用累加器拆分尾递归版本将变为:

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

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

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

现在，速度上的差异现在比以前要小得多，请参阅 Myth: Tail-recursive functions are MUCH faster than recursive functions，因此最好使用看起来更清晰的样式。我个人宁愿不要使用蓄电池，除非必须这样做。