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

问题描述：

我正在阅读的关于Erlang的书在它后面有练习，其中一个是重新创建列表：append函数。如何在不使用列表模块的情况下编写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 。我怎样才能修改它，以便它适用于任意数量的随机大小的列表？

我不使用二郎，但我无法想象`list：append`比'++`快（我认为无论你怎么做都是O（n））。 – Zifre 2009-07-15 12:42:53

`list：append` _is_`++`。 – 2009-07-15 17:54:51

但是如果++的左操作数大于右操作数，++可能效率低下。列表中还会出现这种性能损失：append？ – samoz 2009-07-15 18:21:02

答

你只需要两个参数给你的concat函数，因为你将追加到其中一个参数，这就是你最终会返回的结果。类似于（未测试）：

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

++是append运算符，您将必须这样做才能高效。

（上面的想法是，如果我们没有更多的左边，则返回左边的参数，或者在从右向左移动一个元素之后再次调用）。有可能更多的效率做附加反向，然后最终扭转答案，但嘿...）

（刚刚看到你的编辑，我的当然只适用于两件事情追加，但你可以递归通过以上函数为您的列表中的每个元素...）

答

++只有在使用错误时才会很慢，仔细使用它的速度与您手工制作的任何东西一样快。你必须确保你在正确的方向上完成列表，否则结果是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

答

一个绝妙的方法是使用lists:foldr，

concat(A,B) -> 
    lists:foldr(fun(X,XS) -> [X|XS] end, B, A). 

concat(XS) -> 
    lists:foldr(fun concat/2, [], XS).

这也是一个很好的锻炼; Tibial写自己foldr相似功能...

答

-module(functional). 
    -export([my_append/2,helper/2]). 

    my_append(L1,L2) -> 
     % concatenates lists L1 and L2 
     functional:helper(lists:reverse(L1),L2). 
    helper(L1,L2) -> 
     if 
      L1 == [] -> L2; 
      L2 == [] -> L1; 
      true  -> [H1|T1] = L1, 
         functional:helper(T1,[H1|L2]) 
     end.

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

相关推荐