Как правильно сделать конкатенацию списков (используя tail-recursion)

Question

Я работаю над следующим упражнением Эрланга:

Напишите функцию, которая, учитывая список списки, объединю их. Пример:

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] и вместо этого использовал аккумулятор (как показано ниже).

Второй вопрос

Теперь второй код считается хвостовой рекурсией?

Книга намекает на использование вспомогательной функции (которую выполняет второй код), но она кажется довольно многословной. Это потому что я что-то упустил?

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

Теперь разница в скорости намного меньше, чем раньше, см. Миф: рекурсивные функции с хвостом намного НАМНОГО быстрее, чем рекурсивные функции , поэтому лучше всегоиспользуйте стиль, который кажется более понятным.Лично я предпочитаю не использовать аккумулятор, если мне не нужно.

Answer 2

Оба [H|concatenate([T|Tail])] и [H|concatenate(T,Tail)] не являются хвостово-рекурсивными вызовами, потому что оба вызова являются частью другого выражения, и, следовательно, управление будет возвращено выражению, которое включает в себя вызов вашего concatenate/1,2.

Правильная хвостовая рекурсия conc может выглядеть примерно так:

-module(concat).
-export([concatenate/1]).

concatenate(L) ->
     conc(L, []).

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

Здесь, в conc/2, вызов самого себя является последней операцией в теле функции, и функция никогда не вернется.

РЕДАКТИРОВАТЬ : Если мы забудем об оптимизации нерекурсивных вызовов, на данный момент @Robert упомянул, что в результате мы можем получить переполнение памяти из-за обратных адресов вызывающих функций, передаваемых в стек (куча?). Это может произойти, если вы вызвали свою нерекурсивную функцию, передав ей список со значительной длиной в системе с недостаточным объемом памяти для хранения такого количества адресов возврата.

Answer 3

Я также реализовал конкатенацию списков в Стиль прохождения продолжения :

-module(concat).
-export([concat_cps/2]).

concat_cps([], F) ->
     F([]);
concat_cps([H|T], F) ->
     concat_cps_1(H, T, F).

concat_cps_1([H|T], Rest, F) ->
     concat_cps_1(T, Rest, fun(X) -> F([H|X]) end);
concat_cps_1([], Rest, F) ->
     concat_cps(Rest, F).

Так что, если кому-то достаточно просто рекурсии, он может повысить управление потокомс замыканиями и продолжениями , как показано выше.

Тест:

1> concat:concat_cps([[1,2,3], [], [4,5]], fun(X) -> X end).
[1,2,3,4,5]

Второй аргумент concat_cps/2 - это продолжение, которое,когда concat_cps/2 сделано, принимает результат последнего.Тогда элемент управления concat_cps/2 никогда не возвращается.

В приведенном выше примере мы просто использовали морфизм идентичности , хотя мы могли бы передать любое другое допустимое продолжение, которое принимает плоский списокНапример:

2> concat:concat_cps([[1,2,3], [], [4,5]], fun(X) -> length(X) end).
5

Answer 4

Очевидное решение состоит в том, чтобы использовать стандартную библиотеку, если есть такая функциональность, которая в данном случае представляет собой списки: append / 1. Специфика реализации может меняться с годами, но сегодняшняя версия очень проста (и не является рекурсивной):

%% append(L) appends the list of lists L

-spec append([[T]]) -> [T].

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