Inspiré de :

• http://www.coli.uni-saarland.de/~kris/learn-prolog-now (pdf),
• de travaux pratiques de Michel Bour.

Ce TP a pour objectif :

• de présenter la notion de liste en Prolog,
• de présenter quelques parcours récursifs sur les listes.

Structure de liste

Introduction aux listes

On définit une liste en mettant des termes entre crochets, et en les séparant par des virgules. En voici des exemples :

• [mia, vincent, jules, yolanda]
• [mia, robber(honey_bunny), X, 2, mia]
• []
• [mia, [vincent, jules], [butch, girlfriend(butch)]]

Une liste contient des termes : constantes, variables, termes complexes qui peuvent être mélangés. En particulier, une liste peut elle-même contenir d'autres listes

Signalons pour finir que la liste vide (de longueur 0) est représentée par [].

Tête et queue

Une liste non vide est divisée en deux parties :

La tête

Le premier élément de la liste

La queue

La liste privée de la tête.

Par exemple,

• dans [mia, vincent, jules, yolanda], la tête est mia quand la queue est [vincent, jules, yolanda].
• dans [dead(zed)], la tête est dead(zed) et la queue est [].

Prédicat "|" de décomposition de liste

Le prédicat Prolog "|" (pipe) décompose une liste entre sa tête et sa queue : si on pose la requête

  ?- [X|Y] = [mia, vincent, jules, yolanda].

Alors :

• la variable X est unifiée à mia,
• la variable Y est unifiée à [vincent, jules, yolanda].

Travaux pratiques

Listes identiques

Quelles sont les réponses de Prolog aux requêtes suivantes ?

  1. [a,b,c,d] = [a,[b,c,d]].
  2. [a,b,c,d] = [a|[b,c,d]].
  3. [a,b,c,d] = [a,b,[c,d]].
  4. [a,b,c,d] = [a,b|[c,d]].
  5. [a,b,c,d] = [a,b,c,[d]].
  6. [a,b,c,d] = [a,b,c|[d]].
  7. [a,b,c,d] = [a,b,c,d,[]].
  8. [a,b,c,d] = [a,b,c,d|[]].
  9. [] = _.
 10. [] = [_].
 11. [] = [_|[]].

Correction de syntaxe

Dire lesquelles des listes suivantes sont syntaxiquement correctes. Le cas échéant, donner la taille de la liste.

  1. [1|[2,3,4]]
  2. [1,2,3|[]]
  3. [1|2,3,4]
  4. [1|[2|[3|[4]]]]
  5. [1,2,3,4|[]]
  6. [[]|[]]
  7. [[1,2]|4]

Exercice sur "|".

Quel résultat donnerait la requête

  ?- [X|Y] = [].

Et la requête :

  ?- [X|Y] = [[], dead(zed), [2, [b, chopper]], [], Z].

Même question pour

  ?- [X,Y | W] = [[], dead(zed), [2, [b, chopper]], [], Z].

Idem avec

  ?- [_,X,_,Y|_] = [[], dead(zed), [2, [b, chopper]], [], Z].

Appartenance d'un élément à une liste

On montre dans ce qui suit comment vérifier qu'un élément appartient à une liste donné, par récursivité.

Première définition

On souhaite définir le prédicat element(X,Y), qui sera vrai si l'élément X appartient à la liste Y.

Pour se faire, on constate qu'un élément appartient à une liste :

• S'il est égal à la tête de la liste, ce qui conduit à la clause

element(X,[X|T]).

• S'il appartient à la queue de la liste, ce qui donne la clause

element(X,[H|T]) :- element(X,T).

D'où l'ensemble de clauses définissant le prédicat element(X,Y) :

  element(X, [X|T]).
  element(X, [H|T]) :- element(X,T).

Exemples d'application

Face à la requête

  ?- element(yolanda,[yolanda,vincent,jules]).

Prolog va appliquer la première règle pour unifier avec succès

• X à yolanda,
• T à [trudy,vincent,jules].

Par contre, face à la requête

  ?- element(vincent,[yolanda,vincent,jules]).

Prolog ne peut pas appliquer la première règle : X ne peut s'unifier simultanément à vincent et à yolanda.

Pour exploiter la seconde règle, Prolog unifie :

• X à vincent,
• H à yoland,
• T à [vincent,jules].

Il doit alors déduire element(vincent,[vincent,jules]), ce qui s'obtient immédiatement avec la règle 1

Enfin, face à la requête :

  ?- element(vincent,[yolanda,jules]).

Prolog ne peut pas appliquer la première règle : X ne peut s'unifier simultanément X à vincent et à yolanda.

Pour exploiter la seconde, il unifie :

• X à vincent,
• H à yoland,
• T à [jules].

Il doit alors déduire element(vincent,[jules])

• Il ne peut pas appliquer la premier règle (impossible d'unifier simultanément X à vincent et à jules).
• Pour exploiter la seconde il unifie :
  • X à vincent,
  • H à jules,
  • T à [].

Il doit alors déduire element(vincent,[]). Or le prédicat de séparation "|" ne peut pas s'appliquer sur la liste vide.

Bref, Prolog échoue.

Définition minimale du predicat element

On peut faire mieux. Dans la première règle :

  element(X,[X|T]).

Nommer la queue par T est inutile : on ne s'en sert pas dans la partie droite.

Dans ce cas on peut remplacer T par une variable muette _, ce qui donne :

  element(X,[X|_]).

De même, dans la seconde règle, nommer la tête par H est inutile :

  element(X,[H|T]) :- element(X,T).

On peut là encore remplacer H par une variable muette _, ce qui donne :

  element(X,[_|T]) :- element(X,T).

Travaux Pratiques

Algorithmes de traitement des listes I

Écrire les règles nécessaire à la définition de :

hors_de(x,l)

Qui s'efface si x n'est pas élément de la liste l, et ne s'efface pas dans le cas contraire.

tous_differents(l)

Qui vérifie qu'un même élément ne figure pas plus d'une fois dans la liste l.

retirer(x,l,m)

Qui retire la première occurrence de l'élément x de la liste l pour donner la liste m, et qui échoue lorsque x n'est pas élément de l.

retirer(x,l,m)

Qui retire cette fois-ci toutes les occurrences de l'élément x de la liste l pour donner la liste m (et qui échoue lorsque x n'est pas élément de l).

inserer(n,x,l,m)

Qui insère l'élément x en n-ième position dans la liste l, pour obtenir la liste m.

Algorithmes de traitement des listes II

Faire de même avec :

supprimer_occurrences(l,m)

Qui lie à mune liste qui comporte les mêmes éléments que ceux de la liste l, mais dans laquelle les éventuelles occurrences multiples de ces éléments sont supprimées. Le but ne doit jamais échouer.

est_debut_de(m,l)

Qui vérifie si la liste m figure au début de la liste l. Que se passe-t-il si m est libre lors du lancement du but est_debut(m,l) ?

contenu_dans(m,l), contenue_meme_ordre(m,l), sous_liste(m,l)

Qui vérifient que tous les éléments de la liste m sont dans la liste l, dans les cas suivants (respectivement) : dans un ordre quelconque, dans le même ordre, dans le même ordre et consécutivement.

renverser(x,y)

Qui écrit dans la liste y la liste x en commençant par la fin.

fusionner(u,v,l)

Qui prend alternativement un élément de la liste u et un élément de la liste v' pour construire la liste l''.

intersection(u,v,l), reunion(u,v,m)

Qui font ce à quoi on s'attend. On supposera que les listes u et v ne comportent pas d'occurrences multiples d'éléments.

permutation(l,m)

Où m doit être lié à une liste qui comporte les mêmes éléments que la liste liée à 'l, écrits dans un ordre quelconque. À titre d'indication, voici les déclarations de description de l'algorithme qui pourraient être utilisées :

• La seule permutation de la liste vide est la liste vide.
• Une permutation d'une liste est obtenue en retirant un élément quelconque à cette liste, et en le rajoutat en tête d'une permutation quelconque des éléments restants.

ordonner(l,m)

l est liée à une liste d'éléments, tous de même nature, qui peuvent être comparés par une règle inférieur(x,y) qui réussit où échoue selon que x est ou non considéré comme strictement inférieur à y. m sera liée à la liste des éléments de l rangés dans l'ordre croissant.

Arbre sur element

Construire les arbres de décision pour les trois requêtes suivantes :

 ?- element(a,[c,b,a,y]).
 ?- element(x,[a,b,c]).
 ?- element(X,[a,b,c]).

Listes similaires

Définir le prédicat a_similaire_b qui prend deux listes en argument et qui est vrai

• si la première liste ne contient que des a et
• si la première liste ne contient que des b et
• si les listes on le même nombre d'éléments et faut sinon.

Combinaison de listes

Définir le prédicat combine qui prend trois listes en argument et qui est vrai si la troisième liste est égale à la fusion des deux première en alternant les éléments des deux premières tant qu'il y en a.

On a par exemple les déductions suivantes :

 ?- combine ([a,b,c],[1,2,3],X).
 X = [a,1,b,2,c,3];
 fail

 ?- combine ([a,b,c,d],[1,2],X).
 X = [a,1,b,2,c,d];
 fail

 ?- combine ([a,b],[1,2,3,4],X).
 X = [a,1,b,2,3,4];
 fail