如何在不使用lists模块的情况下编写Erlang的列表连接？

Question

我正在读的关于Erlang的书在它的后面有练习,一个是重新创建列表:追加功能.

我可以简单地使用++运算符来做这个,但这不是很慢吗？我认为练习的重点是使用我编写的列表操作来完成.

到目前为止,我能想到的唯一方法是执行以下操作:

concat([], _, Results)->
  Results;
concat(_, [], Results)->
  Results;
concat([Ah|At],B,Results) ->
  concat(At,B,[Ah|Results]).

但我知道这是不正确的......

关于如何做到这一点的任何建议？

编辑:澄清问题,这是一个示例输入和输出:

输入:[[1,2,3],[],[4,5],[6]]输出:[1,2,3,4,5,6]

工作一段时间后,我想出了这个代码:

append([A|[B|[T|[]]]]) ->
  append([A++B|T]);
append([H|T]) ->
  H++T.

但是,这仅适用于列表大小为3的情况.如何修改此值以使其适用于任意给定数量的随机大小的列表？

Answer 1

++错误地使用时速度很慢,小心使用它就像你手工制作的任何东西一样快.您必须确保以正确的方向处理列表,否则结果附加为O(N ^ 2).当我们执行X ++ Y时,我们必须复制X,然后将其添加到未复制的Y.

在此函数中,累加器出现在++的左侧,因此附加效率不高.

concatl(Lst) ->
    concatl(Lst, []).
concatl([], Acc) ->
    Acc;
concatl([H|T], Acc) ->
    concatl(T, Acc ++ H).

这个函数执行得更好,即使它不是尾递归.

concat([]) -> [];
concat([H|T]) ->
    H ++ concat(T).

在这种情况下,重写为尾递归只是一个适度的改进:

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

大输入列表上的时间显示了改进的巨大程度.(时间以微秒为单位.)

41> Time(fun() -> test:concatl([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end).
14539061
40> Time(fun() -> test:concat([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end).
245356
42> Time(fun() -> test:concat2([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end).
211571

Answer 2

您的 concat 函数只需要两个参数，因为您将附加到其中一个参数，这就是您最终将返回的内容。像（未经测试）的东西：

concat(L,[]) ->
   L;
concat(L,[H|T]) ->
   concat(L ++ [H],T).

++ 是追加运算符，您必须这样做才能提高效率。

（上面的想法是，如果我们没有剩下的参数，则返回 left 参数，或者在将其中一个元素从右向左移动后再次调用）。反向执行追加然后最终反转答案可能会更有效率，但是嘿......）

（刚刚看到您的编辑，当然我的编辑仅适用于要附加的两件事，但您可以通过上述函数对列表列表中的每个元素进行递归...）