Recursion de queue à Erlang

Question

J'ai vraiment du mal à comprendre la récurrence de la queue à Erlang.

Je le test eunit suivant:

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

Et voici ma mise en œuvre:

-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([]) -> 
    []. 

est mon queue de mise en œuvre récursive et sinon, comment puis-je faire cela?

Merci à l'avance

Answer 1

Votre implémentation n'est pas récursive queue car append doit tenir sur la tête de la liste lors du calcul de la queue. Pour qu'une fonction soit récursive en arrière, la valeur de retour ne doit pas s'appuyer sur une valeur autre que celle renvoyée par l'appel de fonction.

vous pouvez réécrire comme ceci:

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 

Notez que tout le travail est terminé une fois que l'appel récursif de la queue se produit. Ainsi, la fonction d'ajout peut oublier dans le corps de la fonction et n'a besoin que de se souvenir des valeurs des arguments qu'elle passe dans l'appel suivant.

Notez également que j'ai mis la clause de terminaison avant la clause récursive. Erlang évalue les clauses dans l'ordre et puisque les clauses de terminaison sont typiquement plus spécifiques, les clauses récursives moins spécifiques les cacheront, empêchant ainsi la fonction de revenir, ce qui n'est pas du tout le comportement désiré.