Conception d'un prédicat Prolog
Exemple du prédicat addFin
Ce prédicat exprime une relation entre trois données. Pour que la relation soit vérifiée, il faut que la liste située dans le troisième slot soit constituée de la liste située dans le premier slot suivie de la valeur située dans le deuxième slot.
Exemples de buts :
true
false
addFin([1,2],3,[1,2,3]).
addFin([1,2],4,[1,2,3]).
P = [1,2], V = 3
R = [1,2,4]
addFin(P,V,[1,2,3]).
addFin([1,2],4,R).
1. Bien spécifier le prédicat à définir
une liste constituée de la petite liste suivie de la valeur du deuxième slot
une valeur
une liste appelée petite liste
addFin( petite_liste , valeur , grande_liste )
[1,2,3]
[1,2,3,5]
Ce prédicat exprime une relation entre trois données. Pour que la relation soit vérifiée, il faut que la liste située dans le troisième slot soit constituée de la liste située dans le premier slot suivie de la valeur située dans le deuxième slot.
Exemples de buts :
true
false
addFin([1,2],3,[1,2,3]).
addFin([1,2],4,[1,2,3]).
P = [1,2], V = 3
R = [1,2,4]
addFin(P,V,[1,2,3]).
addFin([1,2],4,R).
2. Concevoir une spécification exécutable
L'approche proposée ici n'est pas la seule possible. Elle est particulièrement adaptée aux personnes qui ont une première expérience en algorithmique et programmation récusive
une liste constituée de la petite liste suivie de la valeur du deuxième slot
une valeur
une liste appelée petite liste
addFin( petite_liste , valeur , grande_liste )
Entrée
Sortie
Entrée
On attribue à chaque slot un rôle d'entrée ou de sortie qui correspondent au cas d'utilisation qui nous parait le plus facile à appréhender.
Exemples de but :
R = [1,2,4]
addFin([1,2],4,R).
addFin( , , )
Entrée
Entrée
Entrée
2. Cas trivial
On commence par se demander dans quelle situation on peut obtenir immédiatement le résultat, sans appel récursif.
une liste constituée de la petite liste suivie de la valeur du deuxième slot
une valeur
une liste appelée petite liste
addFin( petite_liste , valeur , grande_liste )
Entrée
Sortie
Entrée
addFin(P,V,[V]).
Quand la petite liste est vide.
addFin([],V, ).
À une liste ayant la valeur du deuxème slot pour seul élément.
À quoi ressemble alors la grande liste ?
2. Cas général
une liste constituée de la petite liste suivie de la valeur du deuxième slot
Puique le cas trivial correspond à une liste d'entrée vide, alors le cas général doit traiter les situations dans lesquelles cette liste n'est pas vide.
une valeur
une liste appelée petite liste
addFin( petite_liste , valeur , grande_liste )
Entrée
Sortie
Entrée
D'autre part, comme dans toute démarche de programmation récursive, on suppose qu'on dispose d'une version du prédicat addFin parfaitement opérationnel avec toute liste d'entrée plus courte que celle actuellement traitée.
La situation semble se prêter à décomposer la liste d'entrée (non vide) en un élément de tête et un reste.
addFin([T|R],V, ) :- ...
addFin([T|R],V,[T|Q]) :- ...
En construction
2. Cas général (suite)
une liste constituée de la petite liste suivie de la valeur du deuxième slot
addFin([T|R],V,[T|Q]) :- ...
Nous avons déterminé la tête de la clause qui représente le cas général de la définition récursive de notre prédicat.
une valeur
une liste appelée petite liste
addFin( petite_liste , valeur , grande_liste )
Entrée
Sortie
Entrée
addFin([T|R],V,[T|Q]) :- addFin(R,V,Q).
Nous devons à présent écrire le corps de cette clause dont le rôle est de produire Q à partir de R et V grâce à un appel récursif du prédicat addFin.
En faisant en sorte que Q soit la liste constituée de R suivie de V.
Comment obtenir le reste Q de la liste de sortie à partir du reste R de la liste d'entrée et de la valeur finale V ?
C'est tout à fait possible !
Il faut que les rôles attribués aux slots correspondent à un cas d'utilisation du prédicat. Ici, celà reviendrait à l'utiliser pour déterminer si une liste connue se décompose en un début, qui est une autre liste connue, plus un élément connu situé à la fin.
Le choix de donner le rôle de sortie au troisième slot a été fait pour des raisons pédagogiques.
Comment construire la liste de sortie ?
La liste de sortie a le même élément de tête que la liste d'entrée, donc on peut déjà donner cette information ici en décrivant cette liste sous la forme [T|Q].
Il restera à "dire" dans le corps de la clause comment on obtient Q.
Prolog : concevoir un prédicat récursif
Olivier Bailleux
Created on April 8, 2024
Start designing with a free template
Discover more than 1500 professional designs like these:
View
Fill in Blanks
View
Countdown
View
Stopwatch
View
Unpixelator
View
Break the Piñata
View
Bingo
View
Create a Secret Code
Explore all templates
Transcript
Conception d'un prédicat Prolog
Exemple du prédicat addFin
Ce prédicat exprime une relation entre trois données. Pour que la relation soit vérifiée, il faut que la liste située dans le troisième slot soit constituée de la liste située dans le premier slot suivie de la valeur située dans le deuxième slot.
Exemples de buts :
true
false
addFin([1,2],3,[1,2,3]).
addFin([1,2],4,[1,2,3]).
P = [1,2], V = 3
R = [1,2,4]
addFin(P,V,[1,2,3]).
addFin([1,2],4,R).
1. Bien spécifier le prédicat à définir
une liste constituée de la petite liste suivie de la valeur du deuxième slot
une valeur
une liste appelée petite liste
addFin( petite_liste , valeur , grande_liste )
[1,2,3]
[1,2,3,5]
Ce prédicat exprime une relation entre trois données. Pour que la relation soit vérifiée, il faut que la liste située dans le troisième slot soit constituée de la liste située dans le premier slot suivie de la valeur située dans le deuxième slot.
Exemples de buts :
true
false
addFin([1,2],3,[1,2,3]).
addFin([1,2],4,[1,2,3]).
P = [1,2], V = 3
R = [1,2,4]
addFin(P,V,[1,2,3]).
addFin([1,2],4,R).
2. Concevoir une spécification exécutable
L'approche proposée ici n'est pas la seule possible. Elle est particulièrement adaptée aux personnes qui ont une première expérience en algorithmique et programmation récusive
une liste constituée de la petite liste suivie de la valeur du deuxième slot
une valeur
une liste appelée petite liste
addFin( petite_liste , valeur , grande_liste )
Entrée
Sortie
Entrée
On attribue à chaque slot un rôle d'entrée ou de sortie qui correspondent au cas d'utilisation qui nous parait le plus facile à appréhender.
Exemples de but :
R = [1,2,4]
addFin([1,2],4,R).
addFin( , , )
Entrée
Entrée
Entrée
2. Cas trivial
On commence par se demander dans quelle situation on peut obtenir immédiatement le résultat, sans appel récursif.
une liste constituée de la petite liste suivie de la valeur du deuxième slot
une valeur
une liste appelée petite liste
addFin( petite_liste , valeur , grande_liste )
Entrée
Sortie
Entrée
addFin(P,V,[V]).
Quand la petite liste est vide.
addFin([],V, ).
À une liste ayant la valeur du deuxème slot pour seul élément.
À quoi ressemble alors la grande liste ?
2. Cas général
une liste constituée de la petite liste suivie de la valeur du deuxième slot
Puique le cas trivial correspond à une liste d'entrée vide, alors le cas général doit traiter les situations dans lesquelles cette liste n'est pas vide.
une valeur
une liste appelée petite liste
addFin( petite_liste , valeur , grande_liste )
Entrée
Sortie
Entrée
D'autre part, comme dans toute démarche de programmation récursive, on suppose qu'on dispose d'une version du prédicat addFin parfaitement opérationnel avec toute liste d'entrée plus courte que celle actuellement traitée.
La situation semble se prêter à décomposer la liste d'entrée (non vide) en un élément de tête et un reste.
addFin([T|R],V, ) :- ...
addFin([T|R],V,[T|Q]) :- ...
En construction
2. Cas général (suite)
une liste constituée de la petite liste suivie de la valeur du deuxième slot
addFin([T|R],V,[T|Q]) :- ...
Nous avons déterminé la tête de la clause qui représente le cas général de la définition récursive de notre prédicat.
une valeur
une liste appelée petite liste
addFin( petite_liste , valeur , grande_liste )
Entrée
Sortie
Entrée
addFin([T|R],V,[T|Q]) :- addFin(R,V,Q).
Nous devons à présent écrire le corps de cette clause dont le rôle est de produire Q à partir de R et V grâce à un appel récursif du prédicat addFin.
En faisant en sorte que Q soit la liste constituée de R suivie de V.
Comment obtenir le reste Q de la liste de sortie à partir du reste R de la liste d'entrée et de la valeur finale V ?
C'est tout à fait possible !
Il faut que les rôles attribués aux slots correspondent à un cas d'utilisation du prédicat. Ici, celà reviendrait à l'utiliser pour déterminer si une liste connue se décompose en un début, qui est une autre liste connue, plus un élément connu situé à la fin.
Le choix de donner le rôle de sortie au troisième slot a été fait pour des raisons pédagogiques.
Comment construire la liste de sortie ?
La liste de sortie a le même élément de tête que la liste d'entrée, donc on peut déjà donner cette information ici en décrivant cette liste sous la forme [T|Q]. Il restera à "dire" dans le corps de la clause comment on obtient Q.