37
ProLog Partie 3 : Listes Mathieu Vidal Cours disponible à https://matvidal.wordpress.com/teaching/ Université Grenoble Alpes Année 2015-2016 L2 - MIASHS Grenoble - France

Le langage Prolog - matvidal.files.wordpress.com · l Par unification, Prolog trouve la solution suivante : E= [sardine, pate, melon, avocat] l Nous savons donc affecter une liste

  • Upload
    lyduong

  • View
    219

  • Download
    0

Embed Size (px)

Citation preview

ProLog

Partie 3 : Listes

Mathieu Vidal

Cours disponible à https://matvidal.wordpress.com/teaching/

Université Grenoble Alpes

Année 2015-2016

L2 - MIASHS

Grenoble - France

Planl Présentation des Listesl Listes et Récursivitél Prédicats prédéfinis sur les listesl Accumulateurs

Partie 1-

Présentation des Listes

Les Listes

l A une suite, ordonnée ou non, on associe la liste de ses éléments.l suite e1, e2, …, eN est représentée en Prolog par la

liste [e1, e2, …, eN ]l Exemples :

l suite des variables X et Y est représentée par [X,Y]l suite fraises, tarte, glace par [fraises, tarte, glace]

l Liste vide : [ ]l Une liste peut contenir n fois le même élément :

[a,a]

Unification de liste

l Exemple de programme menu :entrees([sardine, pate, melon, avocat]).

viandes([poulet, roti, steack]).

poissons([merlan, colin, loup]).

desserts([gateau, fruit, glace]).

l Et si on pose la question : entrees(E).

l Par unification, Prolog trouve la solution suivante : E= [sardine, pate, melon, avocat]

l Nous savons donc affecter une liste à une variable.

Découpage Tête Queue

l La notation [X|Y] représente une liste dont la tête (le 1er élément) est X et la queue (le reste de la liste) est Y. l Cela constitue la base de l’utilisation des listes

dans les programmes Prolog. l | : symbole spécial décomposant la liste en Tête

et Queue : [Tête | Queue]l [a, b, c] ≡ [a | [b | [c | [ ] ] ] ]l La tête est un élément et la queue est une liste.

l Expl :?- [a,b] = [X,Y].l X = a, Y = [b].

Contenu d'une liste

l Une liste peut contenir des :l Constantes (atomes, nombres)

l Variables

l Termes complexes

l Listes

Listes et sous-listesl Utilisation du programme menu :

l Volonté de poursuivre le regroupement des données.l Liste unique qui regrouperait tous les mets du menu

§ L= [sardine, melon, … glace]

l Cette représentation n’est pas adéquate car il n’y a pas de distinction entre entrée, plat ou dessert.

l Il est donc nécessaire de découper la liste en sous-listes qui rassembleront les entrées, plats et desserts. La sous-liste des plats sera elle-même divisée en deux parties, les viandes et les poissons.

l Cela nous donne la structure :L = [ [sardines, pate, melon, celeri], [poulet, roti, steack], [merlan, colin, loup], [fraises, tarte, glace] ] L est de la forme : L = [L1, L2, L3, L4]Ou L = [E, V, P, D]

Exercice

l Dire si les expressions suivantes unifient et comment :l ?- [X|Y] = [jean, marie, leo, lea]. l ?- [X|Y] = [].l ?- [X|Y] = [a].l ?- [X|Y] = [[], dort(jean), [2], [], Z].l ?- [X,Y | W] = [[], dort(jean), [2], [], Z].

l ?- [_,X,_,Y | _] = [[], dort(jean), [2], [], Z].l ?- [_,_,_,[_|X] | _] = [1,2, dort(jean), [2,3], [], Z].

Partie 2-

Liste et Récursivité

Elément d'une liste (1)

l Nous avons besoin de pouvoir considérer les éléments d’une liste de façon individuelle, par exemple pour récupérer un élément particulier.l Supposons que l’on dispose du prédicat :

element_de(X, L) capable d’extraire un objet X d’une liste L.

Elément d'une liste (2)

l Nous définissons :menu(X, Y, Z) :- entree(X), plat(Y), dessert(Z).

plat(X) :- viande(X).

plat(X) :- poisson(X).

l Avec la déclaration des entrées comme liste, ce programme échouera. Il faut donc le modifier.

l Pour cela nous allons donner une définition du prédicat entree (le fait d'être une entrée) basée sur entrees (la liste des entrées).

Elément d'une liste (3)

l On utilise la propriété suivante : si X est une entrée, alors X est un élément quelconque de la liste des entrées. On peut donc écrire :

entree(X) :- entrees(E), element-de(X, E).

l Et de façon analogue :viande(X) :- viandes(V), element-de(X, V).

poisson(X) :- poissons(P), element-de(X, P).

dessert(X) :- desserts(D), element-de(X, D).

Accès aux éléments (1)l Il s’agit de rechercher les règles qui vont assurer le

fonctionnement du prédicat element-de(X, L) qui signifie que X est l’un des éléments de L.l On utilise la remarque selon laquelle toute liste peut

se décomposer simplement en une tête et une queue. Cela conduit à distinguer deux cas :l si X est la tête de L, X est élément de L.l si X est élément de la queue de L, X est élément de L.

l Ce qui se traduit directement en Prolog par :(R1) element-de(X, L) :- est-tete(X, L).(R2) element-de(X, L) :- element-de-la-queue(X,L).

l Note : R1 et R2 sont là en tant que repères et ne rentrent pas dans les règles.

Accès aux éléments (2)

l On sait que L peut toujours être représentée sous la forme [U|Y], ce qui nous donne :l Si X est en tête de [U|Y] alors X = U.l Si X est un dans la queue de [U|Y] alors X est

élément de Y.l (R1) element-de(X, [X|_]).

l (R2) element-de(X, [U|Y]) :- X\=U, element-de(X, Y).

l (R2) peut se reformuler en (R2'). Pourquoi ?

l (R2') element-de(X, [_|Y]) :- element-de(X, Y).

Accès aux éléments (3)

l On interprète ces deux règles de la façon suivante :l R1 : X est élément de toute liste qui commence par

X.l R2 : X est élément de toute liste dont la queue est Y,

si la liste ne commence pas par X.

l Il s’agit donc d’un appel récursif. La plupart des problèmes sur les listes ont des solutions mettant en jeu la récursivité.

Récursivité et Arrêt (1)

l On observe deux types de règles et deux types d'arrêt :l Une ou plusieurs règles provoquent la récursivité,

généralement sur des données assez simples, et assurent le déroulement de l’itération. Dans notre exemple, il s’agit de la règle R2.

l Une ou plusieurs règles stoppent la séquence d’appels récursifs. Dans notre exemple, c’est R1 qui s’en charge.

l Sauf impératif contraire, les règles d'arrêt sont placées en tête.

Récursivité et Arrêt (2)

l Il apparaît deux types d'arrêt :l Un arrêt explicite. Par exemple, dans R1, l'identité

entre l'élément cherché et la tête de la liste fournie, ce qu’exprime la notation X et [X|Y]

l Un arrêt implicite. En particulier par la rencontre d’un terme impossible à démontrer.

l Il existe cependant une forme d’erreur pour laquelle ces deux blocages se révèlent insuffisants, c’est la rencontre de listes infinies.

Exercice

Ecrire le prédicat somme/2 qui prend en premier argument une liste d'entiers et donne leur somme en second argument.

Indice : utiliser «S is E» qui évalue l'expression arithmétique E et unifie son résultat avec S.

Exemple d'utilisation:?- somme([5,4,1],S).

S = 10.

Solution à l'exercice

somme([], 0).

somme([T|Q], S) :- somme(Q, Sq), S is T + Sq.

Partie 3-

Prédicats prédéfinis

Quelques prédicats prédéfinis sur les listesl Dans la documentation SWI-Prolog :

- les paramètres d'entrée sont précédés d'un +- les paramètres de sortie sont précédés d'un -- les paramètres qui sont à la fois d'entrée et de sortie sont précédées d'un ?

Exemple : numlist(+Min, +Max, -List).Donne la liste des entiers entre Min et Max

?- numlist(2,8, L). L = [2, 3, 4, 5, 6, 7, 8]

Concaténation : appendl append est le prédicat prédéfini pour la concaténation de

listes : append(?List1, ?List2, ?List3).?- append([a,b,c],[d,e],L).

L = [a, b, c, d, e]l append est complètement symétrique et peut donc être

utilisé pour d’autres opérations :l Trouver tous les découpages d’une liste en 2 sous-listes:

append(L1,L2,[a,b,c,d]).L1 = [], L2 = [a, b, c, d] ;L1 = [a], L2 = [b, c, d] ;L1 = [a, b], L2 = [c, d] ;L1 = [a, b, c], L2 = [d] ;L1 = [a, b, c, d], L2 = []

Quelques prédicats prédéfinis sur les ensembles (listes sans doublons)

list_to_set(+List, -Set).transforme List en un ensemble Set (suppr

doublons)subset(+Subset, +Set).

Subset Set intersection(+Set1, +Set2, -Set3).

Set3 = Set1 Set2union(+Set1, +Set2, -Set3).

Set3 = Set1 Set2subtract(+Set, +Delete, -Rest).

Rest = Set - Deletemerge_set(+Set1, +Set2, -Set3).

Set3 = fusion triée de Set1 et Set2 (Set2 et Set3 sont des ensembles triés)sort(+List, -SetTrié).

transforme List en l'ensemble trié SetTrié

maplist : application d’un prédicat à tous les éléments d’une liste

Les prédicats maplist appliquent un prédicat sur tous les membres

d'une liste ou jusqu'à ce que le prédicat échoue.

maplist(+Pred,+List). Pred est d’arité 1?- maplist( integer, [15,8,5,6,9,4] ). Yes

maplist(+Pred, ?List1, ?List2). Pred est d’arité 2?- maplist(double, [3,4,6], L).L = [6, 8, 12] avec : double(X,D):- D is X*2.

maplist(+Pred, ?List1, ?List2, ?List3). Pred est d’arité 3maplist(plus, [0, 1, 2], [4, 8, 16], L). X = [4, 9, 18] avec : plus(?Int1, ?Int2, ?Int3) Int3 = Int2 + Int1

Liste des solutions d'un prédicat

l Les prédicats findall/3, bagof/3 et setof/3 permettent de faire la liste des solutions d'un prédicat.

l findall(+Motif, +But, -Liste).l Trouve toutes les solutions de But et en fait une Liste selon

le modèle Motif. Pas de solution : retourne []l bagof(+Motif, +But, -Liste).

l Trouve toutes les solutions de But de manière groupée. Pas de solution : retourne false.

● setof(+Motif, +But, -Liste).l Trouve toutes les solutions de But de manière groupée en

supprimant les doublons et en triant les résultats. Pas de solution : retourne false.

findall, bagof, setof : exemples (1)

l Soit le programme suivant :?- findall(C, foo(A,B,C), L).

L = [c, f, d, f, f, e, g]

?- bagof(C, foo(A,B,C), L).

A = a, B = b, L = [c, f, d, f] ;

A = b, B = c, L = [f, e] ;

A = c, B = c, L = [g]

?- setof(C, foo(A,B,C), L).

A = a, B = b, L = [c, d, f] ;

A = b, B = c, L = [e, f] ;

A = c, B = c, L = [g]

foo(a, b, c).foo(a, b, f).foo(a, b, d).foo(a, b, f).foo(b, c, f).foo(b, c, e).foo(c, c, g).

les variables A et B sont unifiées. On a 3 solutions: une pour chaque couple (A,B) possible.

L est un ensemble ordonné

findall, bagof, setof : exemples (2)?- bagof(C, A^foo(A,B,C), L).

B = b, L = [c, f, d, f] ;

B = c, L = [f, e, g] ;

?- setof(C, A^foo(A,B,C), L).

B = b, L = [c, d, f] ;

B = c, L = [e, f, g] ;

?- bagof(C, A^B^foo(A,B,C), L).

L = [c, f, d, f, f, e, g]

?- setof(C, A^B^foo(A,B,C), L).

L = [c, d, e, f, g]

foo(a, b, c).foo(a, b, f).foo(a, b, d).foo(a, b, f).foo(b, c, f).foo(b, c, e).foo(c, c, g).

A^ signifie “ne pas unifier A”

seule la variable B est unifiée, la variable A restant libre. On a 2 solutions: une par valeur de B différente.

les variables A et B ne sont pas unifiées. On n'a alors plus qu'une solution. (~ findall)

Exercice

l Ex1 : On possède une liste. Quelle question poser à Prolog pour qu'il affiche son dernier élément ? On utilisera le prédicat prédéfini append.

l Ex2 : Soit la base de connaissance présentée dans la diapositive précédent. Quel est le résultat retourné par la requête :?- findall(B,foo(A,B,C),L).

Solution des exercices

l Ex 1 :?- append(_,[X],[a,b,c,d]).X = d

l Ex 2 : L = [b,b,b,b,c,c,c]

Partie 4-

Accumulateurs

Prédicat Renverse

● Prédicat permettant de renverser une liste● Exemple : ?- renv([1,2,3],L).

L = [3,2,1] .● Définition :

renv([],[]).

renv([T|Q],L) :- renv(Q,Q1), append(Q1,[T],L).● Problème : très inefficace. On doit atteindre le

cas de base avant d'ajouter

Accumulateur

● Utilisation d'une variable intermédiaire : l'accumulateur

● Stocke le résultat intermédiaire● Permet d'effectuer la manipulation sans

attendre la récursion● Exécution en moins d'étapes et plus rapide

Renverse avec accumulateurl On obtient les règles suivantes :

renverser([], L, L).

renverser([X|Y], L, R) :- renverser(Y, [X|L], R).

l Au lancement L est vide : renverser([a,b,c],[],R).l L’élément qui apparaît en tête de la liste est retiré et placé

en tête de L.

l Interprétation de ces deux règles :l Renverser la liste vide, à partir de la liste auxiliaire L, donne

la liste résultat L : l'accumulateur est transféré au résultatl Renverser la liste [X|Y], à partir de la liste auxiliaire L,

donne la liste résultat R, si renverser la liste Y, à partir de l'accumulateur [X|L], donne la même liste R.

Renverser/2 avec accumulateur

l Si l’on souhaite disposer d’un prédicat renverser/2 qui ne mentionne que les listes donnée et résultat, on peut introduire le prédicat suivant :

renverser(L,R) :- renverser(L,[],R).renverser([], L, L).renverser([X|Y], L, R) :- renverser(Y, [X|L], R).

l Exécution :?- renverser([a,b,c], [], R).R = [c, b, a] Yes

?- renverser([a,b,c],R).R = [c, b, a] Yes

Exercice

Ecrire le prédicat impair/2 qui prend en premier argument une liste et renvoie la même liste mais ne contenant que les éléments impairs (1er élément, 3ème élément, 5ème élément, ...). Utiliser pour ceci le prédicat impair/3 avec accumulateur

Exemple d'utilisation:?- impair([5,4,1,6,8,4,9],R).

S = [5, 1, 8, 9].

Solution de l'Exercice

impair(L,R) :- impair(L,[],R).

impair([],L,L).

impair([_],L,L).

impair([T,_|Q],A1,R) :- append(A1,[T],A2), impair(Q,A2,R).