Хвостовая рекурсия в Эрланге

Question

Я действительно изо всех сил пытаюсь понять хвостовую рекурсию в Эрланге.

У меня есть следующий тест Eunit:

db_write_many_test() ->
    Db = db:new(),
    Db1 = db:write(francesco, london, Db),
    Db2 = db:write(lelle, stockholm, Db1),
    ?assertEqual([{lelle, stockholm},{francesco, london}], Db2).

А вот моя реализация:

-module(db) .
-include_lib("eunit/include/eunit.hrl").
-export([new/0,write/3]).

new() ->
    [].

write(Key, Value, Database) ->
    Record = {Key, Value},
    [Record|append(Database)].

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

Является ли мой хвост реализации рекурсивным, и если нет, то как я могу это сделать?

Заранее спасибо

Answer 1

Ваша реализация не является хвостовой рекурсивной, потому что append должен удерживаться в начале списка при вычислении хвоста. Для того чтобы функция была хвостовой рекурсивной, возвращаемое значение не должно полагаться на значение, отличное от того, которое возвращается из вызова функции.

Вы можете переписать это так:

append(Acc, []) -> %% termination;
    Acc;
append(Acc, [H|T]) ->
    Acc2 = Acc ++ dosomethingto(H); %% maybe you meant this to be your write function?
    append(Acc2, T); %% tail rercursive

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

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