Discussion :

[loic911]

Bonjour à tous,
Je commence (difficilement) a digérer les bases (des bases) de la programmation Prolog.
J'ai essayé avec succès quelques petits exercices de bases (dernier élément de la liste? listes égales? ...).

Mais voilà que je bloque à un exercice:
Il faut définir insere-elem(Xs,E,Ys) tel que:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
insere-elem([titanic,a,coule],stop,X).
X = [titanic,stop,a,stop,coule,stop];

En gros, il faut intercaller entre chaque membre de la liste Xs, l'élément E. Le tout doit donner la liste Ys.

Voilà la solution (qui marche).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
Insere_elem( [  ] ,  _  , [  ]).
Insere_elem( [X|Xs], Y, [X,Y|Ys] ) :-insere_elem( Xs,Y,Ys ).

Ce que je ne comprend pas c'est qu'avec "[X,Y|Ys]", on devrait rajouter au fur a mesure les éléments de la liste Xs (+ Y) au début de Ys.
Alors on aurait: coulé stop a stop titanic stop. Hors ici on a le résultat correct titanic stop a stop coulé stop.

Explication:
Xs = titanic, a, coulé
E = stop

Insere_elem( [X|Xs], Y, [X,Y|Ys] ) :-insere_elem( Xs,Y,Ys )
X = titanic
Xs = a, coulé
Y = stop
[X,Y|Ys] = titanic,stop

Insere_elem( [X|Xs], Y, [X,Y|Ys] ) :-insere_elem( Xs,Y,Ys )
X = a
Xs = coulé
Y = stop
[X,Y|Ys] = a, stop, titanic,stop

1. Donc, j'ai faux dans mon résonnement...mais ou? et en quoi?


Par ailleur, la solution que j'avais trouvé en premier en gribouillant sur ma feuille (sans regarder celle fournit par le prof) était:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
Insere_elem( [  ] ,  _  , [  ]).
Insere_elem( [X|Xs], Y, Ys ) :-insere_elem( Xs,Y,[X,Y|Ys] ).

En gros c'est la même, si ce n'est que Ys et [X,Y|Ys] ont été échangé. Pourquoi ce raisonnement est-il incorrect et ne marche il pas?

Merci d'avance.
Bonne journée!

[Trap D]

Observe les arguments que tu passes à insere_elem :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
insere_elem([X|Xs], Y, Ys ) :-
	insere_elem(Xs,Y,[X,Y|Ys]).

Tu appelles insere_elem en construisant une liste [X,Y|Ys] alors que la liste initiale perd un élément.
Ce qui fait que lorsqu'il n'y a plus d'élément dans le premier argument, Prolog devrait utiliser la règle insere_elem([] , _,[]). mais il ne peut pas puisqu'elle lui est passée avec une liste en phase de construction, c'est pour celà qu'il te répond No.

Avec une règle du style insere_elem([] , _,[])., on sous-entend que la liste résultat est construite en sortie de récursion. On la récupère donc, c'est pour celà que le bon prédicat est

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
insere_elem([X|Xs], Y, ,[X,Y|Ys]) :-
	insere_elem(Xs,Y, Ys).

Ys est la liste obtenue à partir de XS, donc si on remonte à partir de [] .
Au sortir de la clause insere_elem([X|Xs], Y, ... on construit le résultat en ajoutant en te^te de la liste Ys le mot X, et le mot Y.
J'espère avoir été à peu près clair

[loic911]

le bon prédicat est

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
insere_elem([X|Xs], Y, ,[X,Y|Ys]) :-
	insere_elem(Xs,Y, Ys).

Ys est la liste obtenue à partir de XS, donc si on remonte à partir de [] .
Au sortir de la clause insere_elem([X|Xs], Y, ... on construit le résultat en ajoutant en te^te de la liste Ys le mot X, et le mot Y.
J'espère avoir été à peu près clair

Je comprend très bien l'explication du premier point. Mais pas celle du deuxième (que j'ai mis en citation de ce message).

Justement, tu dis que c'est en Tête de le liste qu'on met le mot X et Y. Hors on parcour Xs [titanic,a,coulé] de gauche a droite. Donc on devrait se retrouver avec coulé,stop,a,stop,titanic,stop. Vu qu'on ajoute au fur et a mesure les X et Y en tête de la liste Ys.

Mais sinon merci de ton aide

[Trap D]

Trace l'exécution du programme :

étape 1 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
insere_elem([titanic | reste], stop, [titanic, stop | Ys]) :-
	insere_elem(reste, stop, Ys).

avec reste = [a, coule]

étape 2 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
insere_elem([a| reste], stop, [a, stop | Ys]) :-
	insere_elem(reste, stop, Ys).

avec reste = [coule]

étape 3 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
insere_elem([coule| reste], stop, [coule, stop | Ys]) :-
	insere_elem(reste, stop, Ys).

avec reste = []

On utilise la première clause

insere_elem([], _X, []).

On a donc YS = []

Remonte maintenant la récursion

etape 3 l'argument de sortie est [coule, stop | YS] avec Ys = [] donc [coule, stop]

etape 2 l'argument de sortie est [a, stop | Ys] avec Ys = [coule, stop] donc [a, stop, coule, stop]

etape 3 l'argument de sortie est [titanic, stop | Ys] avec Ys = [a, stop, coule, stop] donc [titanic, stop, a, stop, coule, stop]