Как написать конкатенацию списков Эрланга без использования модуля списков?

Question

В книге, которую я читаю об Эрланге, есть упражнения, и одна из них - воссоздать списки: функция добавления.

Я мог бы сделать это просто используя оператор ++, но разве это не очень медленно? И я думаю, что смысл этого упражнения состоит в том, чтобы сделать это, используя операции со списком, которые я пишу.

Пока что единственный подход, о котором я могу подумать, это сделать что-то вроде:

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

Один аккуратный подход заключается в использовании lists:foldr,

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

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

Это также хороший пример написания своей собственной функции сворачивания ...

Answer 3

Вам нужно всего два параметра для вашей функции concat, так как вы добавите один из параметров, и это то, что вы в конечном итоге вернете.Что-то вроде (не проверено):

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

++ - это оператор добавления, вам придется сделать это, чтобы быть эффективным.

(Идея вышеизложенного состоит в том, чтобывернуть левый параметр, если у нас больше не осталось, или вызвать снова после перемещения одного из элементов справа налево).Вероятно, есть больше возможностей сделать обратное добавление, а затем, наконец, поменять ответ, но эй ...)

(Только что видел ваше изменение, и мое, конечно, работает только для добавления двух вещей, но вы можете повторитьчерез вышеуказанную функцию для каждого элемента в вашем списке списков ...)

Answer 4

    -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.