Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.
Listes et coupe choix – découverte
Les activités de découverte consistent à étudier des présentations explicatives et à traiter tous les exercices de découverte proposés. Si vous ne répondez pas correctement à un exercice de découverte, revenez en arrière pour relire les explications et identifier la cause de votre erreur.
Activité de découverte C.dec
Introduction
Nous allons découvrir comment représenter des listes, ce qui ouvre la voie à la modélisation et à la résolution de nombreux problèmes, et comment limiter le nombre de possibilités explorées par Prolog lors de l’évaluation d’un but.
C.dec1 : Représentation des listes
Prolog permet de construire et exploiter des listes représentée de la manière suivante. Une liste est :
- soit vide (on note
[]), - soit composée d’un élément de tête
Tet d’un resteR, qui est une liste pouvant être vide (on note[T|R]).
Par exemple, le but…
[7,5,3] = [T|R].
…donne comme résultat :
R = [5, 3], T = 7
Ou encore, par exemple…
[a|[]] = L.
… produit le résultat :
L = [a]
Cette représentation permet définir des prédicats exploitant des listes, tels que par exemple le prédicat dernier qui permet de récupérer le dernier élément d’une liste :
dernier([D],D).
dernier([_|R],D) :- dernier(R,D).
La première clause représente le cas trivial (ne nécessitant pas d’appel récursif) dans lequel la liste comporte un unique élément.
Le dernier élément d’une liste qui contient un seul élément est cet élément.
La deuxième clause représente le cas d’une liste de plusieurs éléments.
Si D est le dernier élément de la liste
R, alorsDest le dernier élément de toute liste ayant pour resteR.

Une chose intéressante avec ce prédicat est que son deuxième slot peut être utilisé en entrée ou en sortie. Voici deux exemples de buts qui illustrent ces deux situations :
dernier([1,2,3],D). --> D=3
dernier([1,2,3],2). --> false
Dans les deux buts, le premier slot est utilisé en entrée. Le deuxième slot est utilisé en sortie dans le premier but et en entrée dans le deuxième. Le prédicat peut donc permettre de tester si un élément donné est le dernier élément d’une liste et de produire le dernier élément d’une liste.
Dans le cas où la liste d’entrée est vide, le résultat est toujours false :
dernier([],D). --> false
Exercice de découverte C.x1
On veut définir un prédicat addFin tel que si L est une liste connue, F un élément connu et R est une variable de sortie (non instanciée), alors le but…
addFin(L,F,R)
…fait remonter dans R la liste obtenue en ajoutant F à la fin de L.
Par exemple,
addFin([1,2,3],4,L).
…a pour résultat :
L = [1, 2, 3, 4]
voici la définition du prédicat addFin à compléter.
addFin([],F,[F]).
addFin([T|Q],F,[T|R]) :- ……………………………………… .
La première clause dit :
La liste obtenue en ajoutant
Fà la fin d’une liste vide est[F].
La deuxième clause dit :
La liste obtenue (troisième slot) en ajoutant l’élément
Fà la fin d’une liste[T|Q]a
- pour tête
T- et pour reste la liste
Robtenue en… (Tentez de compéter cette phrase.)
La liste obtenue (troisième slot) en ajoutant l’élément
Fà la fin d’une liste[T|Q]a
- pour tête
T- et pour reste la liste
Robtenue en ajoutant F à la fin de Q.
addFin([],F,[F]).
addFin([T|Q],F,[T|R]) :- addFin(Q,F,R).
Bien que, lors de la conception du prédicat, nous ayons raisonné en considérant que le premier et le deuxième slots étaient des entrées et le troisième une sortie, il est parfaitement possible d’utiliser le prédicat de manière différente.
Donnez le but permettant de récupérer dans une variable D le dernier élément de la liste [1,2,3] et dans une variable L tous les éléments de cette même liste sauf le dernier.
addFin(L,D,[1,2,3]).
Le résultat obtenu est :
D = 3, L = [1, 2]
C.dec2 : quelques mots sur l’unification
Dans un esprit de simplification, on peut dire que l’unification est un processus permettant de rendre deux termes identiques en remplaçant toutes les occurrences d’une ou plusieurs variables par des termes. Parce que la définition formelle du concept nous entraînerait au delà des objectifs de cette initiation, nous limiterons à des exemples.
Deux termes sans variable ne s’unifient que s’ils sont identiques. Ceci s’applique aux listes, qui sont des cas particuliers de termes. Par exemple :
[]ne s’unifie qu’avec[][1,2,3]ne s’unifie qu’avec[1,2,3]tartene s’unifie qu’avectarte[tarte, cake]ne s’unifie qu’avec[tarte, cake].
Une variable s’unifie avec elle même et avec n’importe quel terme qui ne la contient pas. Par exemple :
Xs’unifie avec[1,2]. On noteX=[1,2].[](liste vide) s’unifie avecZ. On noteZ=[].[X,5,Y]s’unifie avecZ. On noteZ=[X,5,Y].[X,5,Y]ne s’unifie pas avecX.
Dans le cas de deux termes contenant des variables, on doit rechercher s’il est possible de les rendre identiques en réalisant des substitutions de variables par des termes. Voici quelques exemples :
[1,X]s’unifie avec[1,2]par la substitution notéeX=2.[1,X]ne s’unifie pas avec[1,2,3]car les listes ne comportent pas le même nombre d’éléments.[1|X]s’unifie avec[1,2,3]par la substitutionX=[2,3].[1|X]s’unifie avec[1,2]par la substitutionX=[2]. (Et pas avecX=2. ne confondez pas la virgule qui sépare les éléments d’une liste et le caractère|qui la décompose en un élément de tête et une liste.[1,B|X]s’unifie avec[1,2]par la substitutionB=2etX=[].
Exercice de découverte C.x2
Les termes [T|Q] et [1,2] s’unifient-ils ? Si oui, par quelle substitution ?
Oui, par T=1 et Q=[2].
Les termes [T|Q] et [7] s’unifient-ils ? Si oui, par quelle substitution ?
Oui, par T=7 et Q=[].
Les termes [T|Q] et [] s’unifient-ils ? Si oui, par quelle substitution ?
Non. La liste représentée par le premier terme comporte nécessairement au moins un élément.
Les termes [1,2|Q] et [1|R] s’unifient-ils ? Si oui, par quelle substitution ?
Oui, par R=[2|Q].
C.dec3 : Coupe choix
Le coupe choix est une entorse au caractère déclaratif de Prolog. Il permet de limiter l’exploration des solutions lors de l’évaluation d’un prédicat. Pour comprendre son fonctionnement, examinons un exemple basé sur les deux prédicats suivants :
val(1).
val(2).
p([X,Y]) :- val(X), val(Y).
p([X]) :- val(X).
Pour évaluer le but…
p(L).
…Prolog recherche tous les moyens de satisfaire p(L) avec chacune des deux clauses définissant le prédicat p. Examinons d’abord les étapes de cette recherche avec la première clause, à savoir :
p([X,Y]) :- val(X), val(Y).
Dans un premier temps, Prolog vérifie si la tête de la clause, p([X,Y]) peut s’unifier avec le but p(L). Cette unification réussi et a pour résultat L=[X,Y].
Ensuite, Il recherche toutes les valeurs de X permettant de satisfaire le premier sous-but val(X), puis pour chacune d’elles toutes les valeurs de Y permettant de satisfaire le deuxième sous-but val(Y). Pour représenter de manière plus lisible les quatre cheminement conduisant aux quatre solutions, on peut représenter la clause sous la forme…
$\text{val}(X) \wedge \text{val}(Y) \to \text{p}([X,Y])$
…dans laquelle le symbole $\to$ représente l’implication logique et le symbole $\wedge$ représente le et logique.
Si $\text{val}(X)$ est vrai et si $\text{val}(Y)$ est vrai alors $\text{p}([X,Y])$ est vrai.

Les résultat du but p(L) issu de la première clause sont :
L = [1, 1]
L = [1, 2]
L = [2, 1]
L = [2, 2]
Ces résultats sont complétés par ceux obtenus à l’aide de la deuxième clause, qui sont :
L = [1]
L = [2]
Le coupe choix, noté !, permet d’annuler les explorations qui n’ont pas encore été réalisées au moment où il est atteint. Si par exemple on le place à la fin de la première clause de p, comme ceci…
p([X,Y]) :- val(X), val(Y), !.
p([X]) :- val(X).
…alors le coupe choix est atteint au moment où la première solution issue de la première clause est produite. Toutes les explorations en attente sont annulées :
- celles relatives aux autres manières de satisfaire les buts de la première clause,
- et celles relatives à la deuxième clause.

Le résultat du but p(L) est :
L = [1, 1]
Si on place le coupe choix ici…
p([X,Y]) :- val(X), !, val(Y).
p([X]) :- val(X).
…alors il annule :
- les autres possibilités en attente de satisfaire le but
val(X)situé avant le coupe choix, - et les explorations exploitant la deuxième clause.
Par contre, les deux manières de satisfaire le but val(Y), situé après le coupe choix dans la première clause, sont explorées.

Le résultat du but p(L) est :
L = [1, 1]
L = [1, 2]
Si on place le coupe choix ici…
p([X,Y]) :- val(X), val(Y).
p([X]) :- val(X), !.
…alors il annule les choix en attente après la production du premier résultat issu de la deuxième clause. Le but p(L) a donc pour résultat :
L = [1, 1]
L = [1, 2]
L = [2, 1]
L = [2, 2]
L = [1]
Exercice de découverte C.x3
Cet exercice doit être traité sans utiliser d’interpréteur Prolog.
On place de coupe choix ici :
p([X,Y]) :- !, val(X), val(Y).
p([X]) :- val(X).
Quel sera le résultat du but p(L) ? Pourquoi ?
Le résultat est :
L = [1, 1]
L = [1, 2]
L = [2, 1]
L = [2, 2]
Les possibilités offertes par la première clause, qui correspondent à des buts situés dans la clause après le coupe choix, ne sont pas affectées. Par contre, la deuxième clause de p sera neutralisée.
On définit le prédicat p de la manière suivante :
p([X,Y]) :- val(X), val(Y), Y\==X.
p([X]) :- val(X).
Donnez le résultat du but p(L).
L = [1, 2]
L = [2, 1]
L = [1]
L = [2]
On ajoute un coupe choix ici :
p([X,Y]) :- val(X), val(Y), !, Y\==X.
p([X]) :- val(X).
Quelle est le résultat du but p(L) ?
Rappelez vous bien que les possibilités non explorées situées avant le coupe choix (ainsi que les clauses suivantes du prédicat) sont annulées lorsque le coupe choix est atteint.
Le résultat du but est false. En effet, lorsque le coupe choix est atteint, X et Y ont toutes les deux la valeur 1 et la condition X\==Y échoue. Comme toutes les autres possibilités à explorer sont annulées par le coupe choix, il n’y a aucune solution.
Pensée récursive
Avant d’aller un peu plus loin avec les listes, je vous propose de faire le point sur l’approche récursive de la résolution de problèmes.
Nous appellerons problème tout ensemble d’instances ayant chacune ayant une, plusieurs, ou aucune solution(s).
Quelques exemples :
- Le problème
concat_v1:- Instances : couples de deux listes.
- Solution d’une instance $(A,B)$ : la liste constituée des éléments de $A$ suivis des éléments de $B$, appelée concaténation de $A$ et $B$.
- Le problème
concat_v2:- Instances : triplets de trois listes.
- Solution d’une instance $(A,B,C)$ :
ouisi $C$ est constituée des éléments de $A$ suivis de ceux de $B$,nondans le cas contraire.
- Le problème
somme:- Instances : couples $(L,v)$ où $L$ est une liste d’entiers positifs et $v$ un entier naturel.
- Solution d’un instance $(L,v)$ : toute liste d’éléments de $L$ dont la somme est égale à $v$. Chaque élément de $L$ peut être utilisé au plus une fois.
Pour résoudre récursivement un problème, il faut associer (de manière implicite ou explicite) à chaque instance un nombre que nous appellerons difficulté. Par souci de simplification, nous allons considérer que la difficulté d’une instance est un entier naturel.
Nous avons aussi besoin de deux ingrédients :
- Un moyen de résoudre immédiatement toute instance de difficulté inférieure ou égale à un certain entier $d_\text{triv}$. De telles instances seront dites triviales.
- Un moyen de résoudre toute instance de difficulté $d>d_\text{triv}$ en utilisant des solutions d’instances de difficultés inférieures à $d$.
Par exemple, dans le cas du problème concat_v1, on peut définir la difficulté d’une instance $(A,B)$ comme étant le nombre d’élément de la liste $A$ et fixer le seuil $d_\text{triv}$ à 0. Ce choix peut paraitre arbitraire, mais il permet d’obtenir facilement les deux ingrédients nécessaires à une résolution récursive du problème :
- La concaténation de la liste vide
[]avec une liste $B$ est la liste $B$. - Soit une instance non triviale $([T|R],B)$. Si $Q$ est la solution de l’instance $(R,B)$, alors la solution de l’instance $(A,B)$ est $[T|Q]$.
Le deuxième ingrédient vous paraît indigeste ? En voici une illustration.

En ajoutant l’élément $T$ en tête de la concaténation de $R$ et $B$, on obtient la concaténation de $A$ et $B$.
Nous avons les ingrédients pour définir un prédicat concat permettant de résoudre notre problème.
Une première clause décrit le cas trivial correspondant à notre premier ingrédient : la concaténation d’une liste vide et d’une liste B est la liste B.
concat([],B,B).
Le deuxième ingrédient sera exploité par la clause récursive suivante :
concat([T|R],B,[T|Q]) :- concat(R,B,Q).
Littéralement :
Si
Qest la concaténation deRetBalors[T|Q]est la concaténation de[T|R]etB.
Ou encore, dans une interprétation plus constructive :
Pour concaténer
[T|R]etB, on ajouteTen tête de la concaténation deRetB.
Le bon fonctionnement du prédicat concat – et de tout prédicat défini récursivement – repose sur le principe de récurrence, très utilisé en mathématiques. Je ne le développerai pas ici, mais vous pouvez vous documenter sur le sujet. Si vous faites confiance à ce principe, alors vous pouvez concevoir des prédicats récursifs sans vous soucier de la manière dont Prolog évalue les buts utilisant ces prédicats.
Le prédicat concat permet aussi de résoudre le problème concat_v2, c’est à dire de vérifier si une liste connue est la concaténation de deux listes connues. Il permet également de résoudre d’autres problèmes, tels que :
- Soient deux listes $B$ et $C$. Trouver la liste $A$ telle que la concaténation de $A$ et $B$ est $C$.
- Soient deux listes $A$ et $C$. Trouver la liste $B$ telle que la concaténation de $A$ et $B$ est $C$.
- Soit une liste $C$. Trouver toutes les listes $A$ et $B$ telles que la concaténation de $A$ et $B$ est $C$.
Exercice de découverte C.x4
Si une liste $L$ est la concaténation d’une liste $P$ avec une liste quelconque (possiblement vide), on dit que $P$ est un préfixe de $L$. Par exemple, les préfixes de [1,2,3] sont les listes [], [1], [1,2], [1,2,3].
Donnez un but permettant de produire tous les préfixes de la liste [1,2,3,4] avec le prédicat concat.
concat(P,_,[1,2,3,4]).
On veux maintenant définir un prédicat pref dédié à la production des préfixes non vides d’une liste.
Par exemple, le but…
pref(P,[1,2,3,4]).
….doit produire le résultat :
P = [1]
P = [1, 2]
P = [1, 2, 3]
P = [1, 2, 3, 4]
Les deux ingrédients permettant de traiter ce problème récursivement sont les suivants :
- Une liste comportant un seul élément a pour seul préfixe elle-même.
- Soit une liste
[T|R]. Les préfixes de cette liste sont : 2.1 d’une part[T], 2.2 et d’autre part, si applicable, toutes les listes obtenues en ajoutantTau début des préfixes non vides deR.
Pour simplifier la définition du prédicat pref, on peut utiliser deux clauses, une non récursive et une récursive, ayant les rôles suivants :
- La clause non récursive produit tous les préfixes de taille 1, quelle que soit la taille de la liste d’entrée. Cette clause exploite donc l’ingrédient 1 et l’ingrédient 2.1.
- La clause récursive produit tous les préfixes de tailles supérieures à 1 en utilisant l’ingrédient 2.2.
Voici une illustration de ce que dit la clause non récursive.

Complétez cette définition du prédicat pref (la liste d’entrée occupe le deuxième slot, les préfixes produits remontent dans le premier slot) :
pref([T],[T|_]).
pref(..... , [T|R]) :- pref(..... , .....).
pref([T],[T|_]).
pref([T|P],[T|R]) :- pref(P,R).

La clause récursive peut se décrire de manière déclarative de la façon suivante :
Quel que soit l’élément
T, siPest un préfixe deR, alors[T|P]est un préfixe de[T|R].
Mais s’il est relativement facile de rédiger une telle description après avoir écrit la clause, il me semble plus difficile de rédiger une telle description comme étape préalable à l’écriture de la clause. C’est la raison pour laquelle je privilégie l’approche constructive lors de la conception de la définition d’un prédicats.
Toutefois, je ne saurais prétendre que cette approche est la meilleure pour tout le monde. C’est à vous de trouver votre propre voie.
C.dec4 : Un peu plus loin avec les listes
Je vous propose une étude de cas : résoudre le problème de la somme, c’est à dire rechercher s’il est possible de produire un entier $s$ appelé valeur cible en additionnant certains des éléments d’une liste $L$.
Par exemple, si $L$ est la liste $[3,5,11,13,17]$ et $s$ vaut 26, alors il n’y a aucune solution. Avec la même liste, si la valeur cible est 27 alors il y a une solution : 3+11+13= 27.
Pour résoudre ce problème, nous allons définir un prédicat somme tel que si L_in est une liste d’entiers positifs , X_in un entier positif ou nul, et S_out une variable non instanciée, alors le but…
somme(L_in, X_in, S_out).
…fait remonter dans S_out les listes d’éléments de L_in dont la somme est X_in.
Par exemple, l’évaluation du but…
somme([1,3,5,11,13,17],25,S).
…produira les solutions :
S = [1, 11, 13]
S = [3, 5, 17]
Pour résoudre le problème récursivement, nous allons considérer que la difficulté d’une instance est la taille de la liste d’entrée. Commençons par chercher nos deux ingrédients. Pour mémoire, le premier ingrédient doit permettre de construire ou de décrire les solutions des instances dont la difficulté est sous un certain seuil. Le deuxième argument doit nous permettre de construire ou de décrire les solutions d’une instance à partir de celles d’une ou plusieurs instances moins difficiles.
Pour le problème de la somme, le premier ingrédient est que si la liste d’entrée est vide (instances de difficulté 0, qu’on appellera instances triviales), la seule valeur réalisable avec une somme d’éléments de la liste d’entrée est 0. Il permet d’écrire la clause non récursive suivante :
somme([],0,[]). % Cas trivial
Notre deuxième ingrédient doit nous permettre de produire (ou décrire) les solutions d’une instance non triviales en exploitant des solutions d’instances basées sur les listes de valeurs plus petites. Je vous propose d’y réfléchir en faisant l’expérience de pensée suivante :
- Vous voulez résoudre une instance de difficulté 5.
- Vous disposez d’un moyen de résoudre des instances de difficulté 4.
Exercice de découverte C.x5
On considère l’instance suivante du problème de la somme.
- La liste d’entrée est [2,3,4,10,11].
- La valeur cible est 25.
On suppose qu’on dispose d’un prédicat somme_ capable de résoudre le problème de la somme, mais seulement avec des listes d’entrée d’au plus 4 éléments.
En utilisant le prédicat somme_, donnez deux buts permettant d’obtenir des informations à partir desquelles on peut immédiatement déterminer les solutions de l’instance du problème de la somme décrite plus haut. Déduisez-en les solutions.
On peut évaluer les deux buts suivants dans lesquels la liste d’entrée comporte tous les éléments de la liste initiale sauf le premier :
somme_([3,4,10,11],23,S).
somme_([3,4,10,11],25,S).
Le premier but tente d’obtenir 25 en utilisant la première valeur de la liste initiale, ce qui nécessite donc de réaliser 25-2, soit 23, avec la liste [3,4,10,11].
Le deuxième but tente d’obtenir 25 sans utiliser la première valeur de la liste initiale, ce qui nécessite de réaliser 25 avec la liste [3,4,10,11].
Le premier but échoue, donc il n’existe pas de solution utilisant la valeur 2.
Le deuxième but produit une seule solution : [4,10,11], qui est de fait l’unique solution de l’instance à résoudre.
En généralisant le principe utilisé dans l’exercice précédent, nous obtenons notre deuxième ingrédient, qui peut être exploité par les deux clauses récursives suivantes :
somme([T|R],S,[T|Q]) :- T=<S, S1 is S-T, somme(R,S1,Q).
somme([_|R],S,Q) :- somme(R,S,Q).
- La première clause récursive permet de rechercher les solutions utilisant le premier élément de la liste d’entrée, à condition que sa valeur ne soit pas plus grande que la valeur cible.
- La deuxième clause récursive permet de rechercher les solutions n’utilisant pas le premier élément de la liste d’entrée.
La définition complète du prédicat somme est la suivante :
somme([],0,[]).
somme([T|R],S,[T|Q]) :- T=<S, S1 is S-T, somme(R,S1,Q).
somme([_|R],S,Q) :- somme(R,S,Q).

Faisons un petit essai pour le fun. Comment obtenir 301 avec 14, 25, 32, 47, 59, 61, 78, 83, 96 ?
somme([14,25,32,47,59,61,78,83,96],301,S).
Solutions :
S = [14, 47, 61, 83, 96]
S = [32, 47, 61, 78, 83]