Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Prolog Discussion :

inversion de liste avec accumulateur


Sujet :

Prolog

  1. #1
    Membre actif
    inversion de liste avec accumulateur
    Bonjour,

    Je cherche à recoder le prédicat reverse/2, en utilisant un accumulateur.
    Le lien https://www.developpez.net/forums/d198010/autres-langages/autres-langages/prolog/d-butant-inverser-liste/ offre une solution, mais qui est insatisfaisante sur les listes imbriquées.
    Par exemple inverse([x,[y,z]],L) va donner [z,y,x], et non [[z,y],x].

    J'ai fini par trouver un document qui semble traiter cette question, ici https://www.cril.univ-artois.fr/~sai...ologCours2.pdf.
    Mais en fait, le résultat sur le même exemple ne donne toujours pas le bon résultat.
    Le prédicat dans ce document est codé comme ceci :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    reverseRec(L,I):- reversRecAcc(L, [], I).
    reverseRecAcc([],I, I).
    reverseRecAcc([X|L1],I1, I2):-
         atom(X),
         reverseRecAcc(L1, [X|I1], I2).
    reverseRecACC([X|L1], I1, I2):-
         not(atom(X)),
         reverseRec(X, I1, I3),
         reverseRec(L1, I3, I2).


    Est-ce que quelqu'un aurait une idée ?

  2. #2
    Rédacteur/Modérateur

    Bonjour
    Tu as presque tout dans ce code :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    my_reverse(L1,L2) :- my_rev(L1,L2,[]).
    my_rev([],L2,L2):-!.
    my_rev([X|Xs],L2,Acc) :- my_rev(Xs,L2,[X|Acc]).
    Il suffit de tester si X est un atome ou pas !
    Voilà le squelette :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    my_reverse(L1,L2) :- my_rev(L1,L2,[]).
    my_rev([],L2,L2):-!.
    my_rev([X|Xs],L2,Acc) :-
         atom(X),
         .....
     
    % ici X est une liste :
    my_rev([X|Xs],L2,Acc) :-
         .....
         ......
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  3. #3
    Membre actif
    Merci Trap D, mais c'est exactement le même squelette.
    Je m'aperçois que j'ai fait quelques coquilles dans la recopie du code, mais sauf la position de l'accumulateur - en dernière place dans ton squelette, au milieu dans le mien, il s'agit des mêmes trames.

    Le problème vient justement du cas où on n'est pas dans un atome.
    Que mettre après avoir vérifé que X n'est pas un atome ?
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    not(atom(X)),
     ...


    J'avoue que je suis perplexe !

  4. #4
    Rédacteur/Modérateur

    Peut-être qu'en testant si X est une liste avec is_list/1 on peut faire quelque chose ...
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  5. #5
    Membre actif
    Citation Envoyé par Trap D Voir le message
    Peut-être qu'en testant si X est une liste avec is_list/1 on peut faire quelque chose ...
    Bon, j'ai fini par trouver une solution.
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    renverseAcc(L,R):- renverseAcc(L,R,[]).
    renverseAcc([],R,Acc) :- R=Acc.
    renverseAcc([T|Q],R,Acc) :- not(is_list(T)), renverseAcc(Q,R,[T|Acc]).
    renverseAcc([T|Q],R,Acc) :- is_list(T), renverseAcc(T,RT,[]), renverseAcc(Q,R,[RT|Acc]).


    Ce n'est pas l'utilisation de is_list/1 qui change grand chose, du moins pour le type d'essais que j'ai fait.
    Un appel renverseAcc([x,[y,z]],L). produit bien le résultat attendu : [[z,y],x].

    Merci

  6. #6
    Rédacteur/Modérateur

    Ce n'est pas l'utilisation de is_list/1 qui change grand chose, du moins pour le type d'essais que j'ai fait.
    Bien sur puisque le test atom/1 échoue.
    Voici le code auquel j'étais arrivé !
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    my_reverse(L1,L2) :- my_rev(L1,L2,[]).
    my_rev([],L2,L2).
    my_rev([X|Xs],L2,Acc) :-
         atom(X),
         my_rev(Xs,L2,[X|Acc]).
     
    my_rev([X|Xs],L2,Acc) :-
         my_reverse(X, RX),
         my_rev(Xs, L2, [RX|Acc]).
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

###raw>template_hook.ano_emploi###