24 ....
---------- -----------



 

------- ------ ﴿ ----- ﴿ ﴾-----


 | 
 

 Concatnation de listes

   
ranim


avatar

: 1413
: 1
: 30
:

: Concatnation de listes    19, 2010 8:05 am

Le prochain exemple est la concatnation de listes, reprsente par le prdicat append en Prolog. Le principe est le suivant :
1. Isoler le premier lment de la liste.
2. Rsoudre rcursivement le prdicat pour concatner le reste de la liste avec la seconde liste.
3. Ajouter au dbut de la liste rsultante llment qui avait t isol la premire tape.
Traduit en Prolog, le programme obtenu est le suivant :
append([],X,X).
append([X|Xs],Y,[X|Zs]):- append(Xs,Y,Zs).
Ce qui est intressant avec ce programme est que lunification, puisquelle ne fait pas de distinction entre les donnes et les rsultats, permet diffrents usages du mme programme :
?- append([a,b,c],[d,e],R).
R = [a,b,c,d,e]
?- append(X,[d,e],[a,b,c,d,e]).
X = [a,b,c]
?- append(X,Y,[a,b,c]).
X = []
Y = [a,b,c] ;
X = [a]
Y = [b,c] ;
X = [a,b]
Y = [c] ;
X = [a,b,c]
Y = [] ;
No
La figure 8 montre les dtails de la rsolution de la dernire requte. La figure 9 montre la situation au moment du premier retour arrire. Finalement, la figure 10 montre ltat au second retour arrire.

FIG. 8 Rsolution de append(X,Y,[a,b,c])
Aussi trange que cela puisse paratre, on peut mme utiliser le prdicat append avec des variables non instancies pour les deux derniers arguments :

FIG. 9 Rsolution de append(X,Y,[a,b,c])

FIG. 10 Rsolution de append(X,Y,[a,b,c])
?- append([1,2],X,Y).
X = K
Y = [1,2|K]

6.4 Exercices
6.1 Soit les faits suivants :
suivant(a,b).
suivant(b,c).
suivant(c,d).
...
suivant(y,z).
suivant(z,a).
Écrivez un programme Prolog qui utilise ces faits pour encoder un nom en suivant lalgorithme suivant. Soit n la position dune lettre dans lalphabet. Chaque lettre du nom est substitue par la lettre qui est la position n + x dans lalphabet, o x est spcifi dans lappel du programme. Par exemple, si x = 3, la lettre d sera substitue par la lettre g, et la lettre z par la lettre c. Le programme reoit une liste de lettres qui reprsente le nom et retourne une liste de lettres qui reprsente le nom encod :
?- encoder([m,i,c,h,e,l],3,X).
X = [p,l,f,k,h,o]

6.2 Soit le programme suivant :
mystere(N,Res):- magique(N,[],L), reverse(L,L2), append(L,[N|L2],Res).
magique(1,L,L).
magique(N,A,L):- N2 is N-1, magique(N2,[N2|A],L)).
a) Quel sera le rsultat retourn pour la requte suivante :
?- mystere(4,L).
b) Quel sera le rsultat si on demande une seconde solution ?
c) Modifiez le programme de manire ce quil ne puisse pas retourner plus dune solution.

6.3 Soit le programme suivant :
mystere(X,Y,Z):- myst1(X,Y,Z).
myst1([ ],[ ],[ ]).
myst1([X|Reste],[X|R1],R2):- myst2(Reste,R1,R2).
myst2([ ],[ ],[ ]).
myst2([X|Reste],R1,[X|R2]):- myst1(Reste,R1,R2).
a) Quel sera le rsultat retourn pour la requte suivante :
?- mystere([t,b,u,e,d,m,o],X,Y).
b) Quel sera le rsultat retourn pour la requte suivante :
?- mystere(X,[1],Z),
c) Quel sera le rsultat si on demande une seconde solution pour la requte de b) ?
6.4 On reprsente une matrice n n par une liste de listes, o chaque liste correspond une range de la matrice. Soit par exemple la matrice suivante :

Voici la reprsentation de cette matrice :
[ [a, b, c],
[d, e, f],
[g, h, i] ]
La position dun lment de la matrice est reprsente par une paire (x, y), o (0, 0) dsigne le coin suprieur gauche et (n, n) le coin infrieur droit. Dans lexemple, les lments aux positions (0, 0) et (3, 3) sont a e i, respectivement.
Dfinissez en Prolog le prdicat chercher(X,Y,Matrice,Elem), qui instancie Elem avec llment qui se trouve la position (X,Y) dans la matrice :
?- chercher(2,2,[[a,b,c],[d,e,f],[g,h,i]],Z).
Z = e
6.5 Soit le programme suivant :
p(X,[],[X]).
p(X,[Y|L],[X,Y|L]):-
X < Y.
p(X,[Y|L],[Y|R]):-
p(X,L,R).
a) Quel sera le rsultat retourn pour la requte suivante :
?- p(5,[2,3,9],Z).
b) Quel sera le rsultat si on demande une seconde solution ?

6.6 Soit larbre gnalogique suivant :

Une manire de reprsenter cet arbre est une liste de termes forms par les foncteurs pere et mere.
Dfinissez un prdicat descendant_communqui reoit trois arguments. Les deux premiers sont les noms de deux personnes. Le troisime est un arbre gnalogique qui est reprsent par une liste qui contient toutes les relations de parent, en utilisant les foncteurs pere et mere. Par exemple :
?- descendant_commun(ana,leo,
[pere(jorge,maria), mere(maria,leo),
mere(maria,luis), pere(pedro,ana),
mere(ana,rui), pere(leo,rui)]).
Yes
?- descendant_commun(pedro,jorge,
[pere(jorge,maria), mere(maria,leo),
mere(maria,luis), pere(pedro,ana),
mere(ana,rui), pere(leo,rui)]).
Yes
?- descendant_commun(pedro,luis,
[pere(jorge,maria), mere(maria,leo),
mere(maria,luis), pere(pedro,ana),
mere(ana,rui), pere(leo,rui)]).
No

6.7 Supposons une reprsentation en Prolog dune base de connaissances en logique propositionnelle, qui utilise les oprateurs ∧, ∨ et . Ces oprateurs sont reprsents par les termes fonctionnels and et or, qui prennent deux arguments, et neg, qui nen prend quun seul. Un argument peut tre une proposition ou une expression. Par exemple, supposons la base de connaissances suivante :
P
S ∧ Q
P ∨ (T ∧ R)
Cette base serait reprsente par la liste suivante :
[p, and(neg(s),q), or(p,neg(and(t,r)))]
Dfinissez un prdicat verif(F,I), o F est la liste qui reprsente la base de connaissances et I une interprtation, cest--dire la liste des propositions vraies. La rsolution doit retourner avec succs si la base est vraie selon linterprtation I. Si une proposition se trouve dans la liste I, elle est vraie, sinon elle est considre fausse. Voici des exemples dexcution qui montrent comment doit se comporter le programme :
?- verif([p, and(neg(s),q), or(p,neg(and(t,r)))],[p,q]).

Yes
?- verif([p, and(neg(s),q), or(p,neg(and(t,r)))],[p,s,q]).
No

7 Interprtations dclarative et procdurale
En Prolog, il y a deux manires danalyser un programme. La premire est une interprtation dclarative, o les rgles reprsentent un tat du monde. Elles sont utilises pour dterminer si une situation est vraie ou fausse. Le prdicat member dfini auparavant est peru de manire dclarative quand on fait une requte du type member(2, [1,2,3,4]). Linterprtation dclarative, dans ce cas, est la suivante : un lment est membre dune liste sil est le premier ou sil est membre du reste de la liste.
Lautre interprtation, dite procdurale, considre les rgles comme des recettes pour atteindre un certain objectif. Une rgle du type A :- B,C. est comprise de la manire suivante : pour rsoudre A, il faut rsoudre B et ensuite C. Par exemple, le prdicat append(L1,L2,L3)suggre naturellement une interprtation procdurale : pour concatner L1 e L2, on doit dabord concatner la queue de L1 avec L2, ajouter le premier lment de L1 la tte du rsultat obtenu et unifier le tout avec L3. En rsum, on a une interprtation procdurale quand on tient compte de lalgorithme de rsolution de Prolog pour comprendre le programme. Entre autres, on doit alors tenir compte de lordre dapparition des buts durant la rsolution. Dun autre ct, on a une interprtation dclarative quand on peut comprendre un programme en faisant compltement abstraction de lalgorithme de rsolution. Pour mieux comprendre ces concepts, nous allons tudier quelques exemples.
Soit le programme suivant :
plus(0,X,X).
plus(suc(X),Y,suc(Z)):-
plus(X,Y,Z).
Dans une interprtation dclarative, il est vu comme un programme qui dtermine si la somme des deux premiers arguments est gale au troisime :
?- plus(suc(suc(0)),suc(suc(0)), suc(suc(suc(suc(0))))).
Yes
?- plus(suc(suc(0)),suc(suc(0)), suc(suc(0))).
No
Dans une interprtation procdurale, il peut tre utilis pour calculer la somme de deux nombres :
?- plus(suc(suc(0)),suc(suc(0)), X).
X = suc(suc(suc(suc(0))))
Étant donn quun clause en Prolog ne distingue pas les entres des sorties, elle peut avoir plusieurs interprtations diffrentes. Par exemple, le prdicat plus peut tre utilis pour raliser une addition, tout comme une soustraction :
?- plus(suc(suc(0)),X , suc(suc(suc(suc(0))))).
X = suc(suc(0))
Considrons maintenant le programme factoriel prsent antrieurement :
factoriel(0,1).
factoriel(X,F):- Y is X-1,factoriel(Y,Fy), F is Fy * X.
Nous avons dj utilis ce programme avec une interprtation procdurale. Apparemment, il permet aussi une interprtation dclarative, puisquil peut tre utilis pour vrifier si 4! = 24 :
?- factoriel(4,24).
Yes
Mais cela est une illusion, puisquen fait, dans les cas o il devrait chouer, avec la requte factoriel(3,24) par exemple, il entrera plutt dans une boucle infinie (pourquoi ?). Pour rsoudre ce problme, il faut ajouter un autre test dans la dernire clause :
factoriel(0,1).
factoriel(X,F):- X > 0, Y is X-1, factoriel(Y,Fy), F is Fy * X.
Remarquez que cette nouvelle version naccepte pas toutes les possibilits de requte. Par exemple, on ne peut pas lutiliser pour identifier le nombre x tel que
x! = 24 :
?- factoriel(X,24).
ERROR: Arguments are not sufficiently instantiated
^ Exception: (7) _G311 is _G239-1 ?
Le problme ici est que loprateur is exige quil ny ait aucune variable libre sa droite. Pour obtenir un programme qui fonctionne correctement, il faut ajouter une clause dans la dfinition et ajouter des tests pour dterminer si le premier argument est une variable libre :
factoriel(0,1).
factoriel(X,Y):- var(X), proc_fact(0,Y,X).
factoriel(X,F):- nonvar(X), X > 0, Y is X-1, factoriel(Y,Fy), F is Fy * X.
proc_fact(X,Y,X):- factoriel(X,Y).
proc_fact(X,Y,R):- X2 is X+1, X2 =< Y, proc_fact(X2,Y,R).
Remarquons que la seconde clause utilise un prdicat intermdiaire proc_fact, qui calcule itrativement le factoriel de tous les nombres partir de 0, jusqu ce que lon tombe sur une valeur qui correspond lentre Y ou quon dpasse cette valeur (dans ce dernier cas, il aura chec). Pour terminer cette discussion, voyons un dernier exemple qui permet lui aussi les deux interprtations. Il sagit du prdicat next(X,L,Y), qui russit si Y suit immdiatement X dans la liste L. Voici le programme :
next(X,[X,N|_],N).
next(X,[_|Reste],N):- next(X,Reste,N).
On peut facilement vrifier que ce programme permet linterprtation dclarative pour dterminer si deux lments sont voisins dans une liste :
?- next(2,[1,2,3,4],3).
Yes
?- next(2,[1,2,3,4],4).
No
Il permet aussi toutes les combinaisons possibles dinstances pour les variables X et Y :
?- next(2,[1,2,3,4],X).
X = 3
?- next(X,[1,2,3,4],4).
X = 3
?- next(X,[1,2,3,4],Y).
X = 1
Y = 2 ;
X = 2
Y = 3 ;
X = 3
Y = 4 ;
No
Notons que les programmes nont pas tous une interprtation dclarative. Un bon exemple est le prdicat liste_femmes, que nous avons prsent antrieurement. Lutilisation des prdicats write et fail forcent une interprtation procdurale du programme.

8 Construction de nouvelles structures
8.1 Appariement
Un appariement entre une structure donne et une structure produite permet la construction de cette dernire paralllement au parcours de la structure donne. Lide est la suivante : pour chaque lment de la structure donne en entre, on produit un lment qui se retrouvera la position correspondante dans la structure qui sera retourne comme rsultat. On peut ventuellement avoir des cas o un item trait dans la structure dentre na aucun correspondant dans la structure de sortie. Il se peut aussi que litem ait plusieurs valeurs qui lui correspondent dans la structure de sortie. Limportant ici est quil doit y avoir un paralllisme entre les lments de la structure dentre et ceux de la structure de sortie.
Exemples :
Programme pour extraire dune liste les nombres infrieurs une valeur fixe :
filtrer([],_,[]).
filtrer([X|R],Max,[X|R2]):- X < Max, filtrer(R,Max,R2).
filtrer([X|R],Max,R2):- X > Max, filtrer(R,Max,R2).
?- filtrer([4,10,5,0,7,3], 5, L).
L = [4,5,0,3]
Programme pour liminer tous les nombre rpts dune liste :
eliminer_rep([],[]).
eliminer_rep([X,X|R],L):-
eliminer_rep([X|R],L).
eliminer_rep([X|R],[X|R2]):-
eliminer_rep(R,R2).
?- eliminer_rep([1,2,2,2,3,6,7,7,10],L).
L = [1,2,3,6,7,10]
?- eliminer_rep([1,2,2,2,3,6,2,2,2,7,7,10],L).
L = [1,2,3,6,2,7,10]
Attention : voici une autre dfinition du prdicat eliminer_rep qui apparemment fonctionne bien mais qui est incorrecte si on veut liminer uniquement les rptitions conscutives :
eliminer_rep([],[]).
eliminer_rep([X|R],L):- member(X,R), eliminer_rep(R,L).
eliminer_rep([X|R],[X|L]):- eliminer_rep(R,L).
Dfini ainsi, le programme retirera toutes les rptitions, quelles soient conscutives ou non :
?- eliminer_rep([1,2,2,2,3,6,7,7,10],L).
L = [1,2,3,6,7,10]
?- eliminer_rep([1,2,2,2,3,6,2,2,2,7,7,10],L).
L = [1,2,3,6,7,10]
Programme pour construire une expression arithmtique :
const_exp(Liste,Exp):- const(Liste,Exp,[]).
const([(|Liste],exp(A1,Op,A2),Reste):- chercher_arg(Liste,A1,[Op|R1]),
chercher_arg(R1,A2,[)|Reste]).
chercher_arg([X|Reste],X,Reste):- X \= (.
chercher_arg([(|Reste],Exp,R2):- const([(|Reste],Exp,R2).
?- const_exp([(,3,*, (,4,-,a,),)],Exp).
Exp = exp(3,*,exp(4,-,a))

8.2 Utilisation dun accumulateur :
On utilise un accumulateur quand on ne peut pas construire une nouvelle structure paralllement la structure fournie en entre, ou encore pour obtenir une rcursivit plus efficace. À chaque pas, on mmorise une structure intermdiaire que lon construit graduellement. Le programme retourne la structure construite quand il arrive la fin du processus rcursif.
Exemples :
Exemple classique de linversion dune liste :
inverser(X,L):- inv(X,[],L).
inv([],L,L).
inv([X|R],L,L2):- inv(R,[X|L],L2).
?- inverser([5,4,3,2],X).
X = [2,3,4,5]
Tri par insertion :
inserer([],X,[X]).
inserer([X|R],Y,[Y,X|R]):- Y < X.
inserer([X|R],Y,[X|R2]):- Y > X,inserer(R,Y,R2).
trier(L,Lord):-tri_ins(L,[],Lord).
tri_ins([],L,L).
tri_ins([X|R],L,Lord):-inserer(L,X,L2),tri_ins(R,L2,Lord).
?- trier([3,7,5,9,10,2],X).
X = [2,3,5,7,9,10]

8.3 Autres exemples :
Évaluation dune expression arithmtique :
eval(X,_,X):-number(X).
eval(X,Env,Val):-atom(X),
member([X,Val],Env).
eval(exp(X,Op,Y),Env,Val):-eval(X,Env,X1),
49
eval(Y,Env,Y1),
apply(Op,X1,Y1,Val).
apply(+,X,Y,Val):- Val is X+Y.
apply(-,X,Y,Val):- Val is X-Y.
apply(*,X,Y,Val):- Val is X*Y.
apply(/,X,Y,Val):- Val is X/Y.
?- eval(exp(3,*,exp(4,-,a)),[[a,2],[b,8]],X).
X = 6
Pour valuer une expression, le programme reoit deux structures. Lune est lexpression, qui peut contenir des constantes qui ne sont pas des nombres mais qui reprsentent plutt des variables (ne pas confondre avec des variables Prolog). Lautre est une liste qui indique la valeur associe chaque "variable" que contient lexpression.
Remarque : Dans cet exemple, on utilise les prdicat pr-dfinis (voir la section 15, qui dcrit ces prdicats) number(X) et atom(X).
Voici un programme pour extraire dune liste les lments qui suivent immdiatement un lment spcifi :
sousliste_apres(X, [X|Reste], Reste).
sousliste_apres(X,[_|Reste], R):-
sousliste_apres(X,Reste,R).
?- sousliste_apres(4,[1,2,3,4,5,3,2,1],L).
L= [5,3,2,1]
Le problme avec ce programme est que si un lment apparat deux fois, nous aimerions que la liste retourne soit celle qui suit la dernire occurrence de cet lment :
?- sousliste_apres(3,[1,2,3,4,5,3,2,1],L).
L= [2,1]
Pour obtenir ce comportement, il faut modifier le programme, en utilisant le prdicat pr-dfini \+, qui reprsente la ngation (voir la section 12.3) :
sousliste_apres(X, [X|Reste], Reste):- \+ member(X,Reste).
sousliste_apres(X,[_|Reste], R):- sousliste_apres(X,Reste,R).

8.4 Exercices
8.1 Écrivez un programme pour dupliquer les lments dune liste :
?- dupliquer([a,c,f],X).
X = [a,a,c,c,f,f]
8.2 Soit un programme pour calculer la somme dune liste de nombres :
?- somme([3,7,9],X).
X = 19
a) Écrivez une version rcursive de ce programme qui nutilise pas la technique de laccumulateur.
b) Écrivez une nouvelle version qui utilise la technique de laccumulateur.
8.3 Écrivez un programme qui reoit une valeur et partitionne une liste, retournant une liste qui contient toutes les items qui sont infrieurs ou gaux a cette valeur, et une autre liste qui contient les nombres suprieurs cette valeur :
?- partition([3,24,0,10,12],8,X,Y).
X = [3,0]
Y = [24,10,12]
8.4 Écrivez un programme qui dtermine si une liste est une sous-liste dune autre
liste :
?- sousliste([a,f],[w,z,a,f,u]).
Yes
?- sousliste([a,u],[w,z,a,f,u]).
No
8.5 Écrivez un programme qui dtermine si tous les lments dune liste sont inclus dans une autre liste :
?- inclus([a,u],[w,z,a,f,u,h]).
Yes
?- inclus([a,k],[w,z,a,f,u,h]).
No
8.6 Écrivez un programme qui traduit en franais une liste de mots en anglais et vice-versa :
?- traduire([i,eat,an,orange],P).
P = [je,mange,une,orange]
?- traduire(E,[je,suis,ici]).
E = [i,am,here]
*8.7 Modifiez le programme prcdent pour traiter les cas o un mot correspond plus dun mot dans lautre langue :
?- traduire2([paul,will,go,to,montral],F).
P = [paul,ira,,montral]
?- traduire2([paul,talked,to,robert],F).
P = [paul,a,parle,,robert]
?- traduire2(E,[je,cherche,la,salle,de,bain]).
E = [i,am,looking,for,the, bathroom]
8.8 Écrivez une programme qui concatne une liste de listes :
?- concatener([[a,b],[c,d,e],[f,g]],L).
L = [a,b,c,d,e,f,g]
?- concatener([[],[1,2]],L).
L = [1,2]
?- concatener([[],[]],L).
L = []
?- concatener([],L).
L = []
*8.9 Écrivez un programme qui effectue un tri par slection.
8.10 Écrivez un programme qui reoit une liste et qui retourne une liste ne contenant que les lments qui se retrouvent plus dune fois dans la liste fournie :
?- elem_repetes([a,b],L).
L = []
?- elem_repetes([a,a,b],L).
L = [a]
?- elem_repetes([a,b,c,c,d,e,c,d,d,k,l,e],L).
L = [c,d,e]
8.11 Écrivez un programme qui intercale les lments de deux listes. Si elles sont de tailles diffrentes, on complte avec les items restants dans la liste de plus grande taille.
?- intercaler([],[], L).
L = []
?- intercaler([a],[], L).
L = [a]
?- intercaler([],[1,2], L).
L = [1,2]
?- intercaler([1,2],[], L).
L = [1,2]
?- intercaler([a,b],[1,2,3,4], L).
L = [a,1,b,2,3,4]
?- intercaler([a,b,c,d],[1,2,3,4], L).
L = [a,1,b,2,c,3,d,4]
8.12 Écrivez un programme qui aplatit une liste pouvant contenir un nombre indfini de listes imbriques. (essayez dcrire une version efficace qui nutilise pas le prdicat append) :
?- aplatir([1,2,[3,4],5],L).
L = [1,2,3,4,5]
?- aplatir([1,2,[],[2,[6,7,[10]]]], L).
L = [1,2,2,6,7,10]
?- aplatir([[[]]], L).
L = []
8.13 Écrivez un programme qui reoit une liste et qui retourne une liste de paires, o chaque paire indique le nombre de fois quun lment apparat dans la liste. (indice : essayez dutiliser un accumulateur et le prdicat num_occ de la section 9) :
?- num_app([a,b,a,d,c,c,a,d],L).
L = [[c,2],[d,2],[b,1],[a,3]]
8.14 Modifiez le programme de lexercice 3.2 pour obtenir le chemin qui permet de sortir dune salle :
connexe(salle1,salle2).
connexe(salle2,salle4).
connexe(salle4,exterieur).
connexe(salle5,salle1).
connexe(salle5,exterieur).
connexe(salle6,salle3).
connexe(salle3,salle7).
connexe(salle7,salle6).
?- sortir(salle1,Chemin).
Chemin = [salle1, salle2, salle4]
?- sortir(salle3,Chemin).
No
8.15 Transformez le programme factoriel de la section 6 en utilisant la technique de laccumulateur.
8.16 Soit un programme qui retourne la valeur maximale dune liste de nombres.
a) Écrivez une version rcursive de ce programme qui nutilise pas la technique de laccumulateur.
b) Écrivez une version qui utilise la technique de laccumulateur.

9 Ordre des clauses
Un aspect important ne pas oublier, quand on programme en Prolog, est lordre des clauses. Cet ordre dtermine quelle sera la premire solution retourne. Voyons, par exemple, lutilisation de member avec une variable libre comme premier argument :
member(X,[X|_]).
member(X,[_|Y]):-
member(X,Y).
?- member(Z,[a,b,c]).
Z = a ;
Z = b ;
Z = c ;
No
Si on inverse lordre des clauses, lordre des solutions retournes est aussi invers :
member(X,[_|Y]):-
member(X,Y).
member(X,[X|_]).
?- member(Z,[a,b,c]).
Z = c ;
Z = b ;
Z = a ;
No
Dans dautres cas, lordre peut faire en sorte que le processus rcursif ne sarrte jamais :
append([X|Xs],Y,[X|Zs]):-
append(Xs,Y,Zs).
append([],X,X).
?- append(X,[1,2],Y).
... (boucle infinie)
Finalement, si lordre est incorrect, on peut obtenir des rponses errones. Supposons que nous voulons crire un programme qui calcule le nombre de fois quun lment apparat dans une liste. Le programme correct est le suivant :
num_occ(_,[],0).
num_occ(X,[X|Reste],Num):-
num_occ(X,Reste,N),
Num is N + 1.
num_occ(X,[_|Reste],Num):-
num_occ(X,Reste,Num).
?- num_occ(b,[a,b,f,b,f,k,b,a],X).
X = 3
La premire classe traite le cas de la liste vide. La seconde traite le cas o llment recherch est le premier de la liste. Dans ce cas, on rsout rcursivement le prdicat avec le reste de la liste et on retourne le rsultat obtenu + 1. Finalement, si on na affaire aucun de ces cas, on rsout rcursivement le prdicat et on retourne la valeur obtenue.
Voyons maintenant le mme programme, mais avec les deux dernires clauses inverses :
num_occ(_,[],0).
num_occ(X,[_|Reste],Num):- num_occ(X,Reste,Num).
num_occ(X,[X|Reste],Num):-num_occ(X,Reste,N),Num is N + 1.
Si on se limite une interprtation dclarative, les deux programmes sont quivalents. Par contre, ce nest pas du tout le cas, si on considre linterprtation procdurale, o lordre des clauses est pris en compte. On obtient tout simplement une rponse errone :
?- num_occ(b,[a,b,f,b,f,k,b,a],X).
X = 0
La raison de ce comportement est que la seconde clause russit toujours lorsque la liste nest pas vide. Alors, le processus rcursif se poursuit toujours avec la deuxime clause, jusqu quon atteigne la condition darrt reprsente par la premire clause.
Remarque : Le programme, mme avec lordre correct des clauses, retourne de nouvelles solutions errones, si on force le retour arrire :
?- num_occ(b,[a,b,f,b],X).
X = 2 ;
X = 1 ;
X = 1 ;
X = 0 ;
No
Essayons de comprendre pourquoi on obtient ces rponses errones. Dabord, voici la situation lorsque la premire solution est retourne (les points de choix sont toujours indiqus en italique) :

Pour fournir la seconde solution, linterprteur Prolog recule au dernier point de choix : le but num_occ(b,[b],Num2), qui peut tre unifi avec la dernire clause. La suite de la rsolution nous amne donc au rsultat suivant :


*****************************************************************
[img][/img]
    
sofia benmassaoud




: 1
: 0
: 24
: student

: : Concatnation de listes    21, 2017 10:12 am

Svp je veux la correction de ces exercices
    
 
Concatnation de listes
    
1 1

:
 ::   ::  -