Analyse et Programmation Déclarative / Prolog

Mise en œuvre des listes

Exemples de descriptions

Usage des méta caractères : [ , ] et |

[paul, jacques, pierre, michel, edouard]

[1.5, -2.75, 4.0]

[12, -11, [4, 75, 40]]

[cœur, X, pique, trèfle]

[]

[Y | Z]

Exemples de mise en œuvre (1)

Extraction de la tête et/ou de la queue

?- [a,b,c,d,e]=[T|Q].

T = a

Q = [b, c, d, e]

Exemples de mise en œuvre (2)

Cas d’une queue vide

?- [a]=[T|Q].

T = a

Q = []

Exemples de mise en œuvre (3)

Vérification de la tête

?- [a,b,c,d,e]=[a|Q].

Q = [b, c, d, e]

Exemples de mise en œuvre (4)

Vérification de la queue

?- [a,b,c,d,e]=[T|[b,c,d,e]].

T = a

Exemples de mise en œuvre (5)

Extraction/contrôle d’un élément

?- [a,b,c,d,e]=[a,b,c,X,e].

X = d

Exemples de mise en œuvre (6)

La liste vide n’a ni tête ni queue !

?- []=[T|Q].

false

Exemples de mise en œuvre (7)

Une liste ne contenant que la liste vide

?- [[]]=[Tete|Queue].

Tete = []

Queue = []

Exemples de mise en œuvre (8)

Cas d’une sous liste

?- [0,[a,b,c]]=[Tete|Queue].

Tete = 0

Queue = [[a, b, c]]

Exemples de mise en œuvre (9)

Unification d’une sous liste

?- [0,[a,b,c]]=[Tete|[SousListe|Fin]].

Tete = 0

SousListe = [a, b, c]

Fin = []

Yes

Exemples de règles (1)

Appartenance à une liste (member)

appartient(X,[X|_]).

appartient (X,[_|Q]) :- appartient(X,Q).

Appartenance à une liste

Etre ou ne pas être dans une liste

?- appartient (a,[q,d,a,f,d]).

true

?- appartient(a,[q,d,f,d]).

false

?- appartient (a,[q,d,[a,f,d]]).

false

Exemples de règles (2)

Cardinal d’une liste (length)

cardinal([], 0).

cardinal ([_|Q], N) :- cardinal(Q, P), N is P+1.

Cardinal d’une liste

?- cardinal ([q,d,a,f,d], N).

N=5

Yes

?- cardinal ([], 0).

true

?- cardinal ([q,d,[a,f,d]], N).

N= 3

?- cardinal (L, N).

Exemples de règles (3)

Somme des éléments d’une liste

somme([], 0).

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

Somme des éléments d’une liste

?- somme ([4,12,-5,1,1], S).

S=13

?- somme ([4, -4], 1).

false

?- somme ([4,[5, 6]], S).

ERROR

Exemples de règles (4)

Inverser l’ordre des éléments (reverse)

renverser([], []).

renverser ([T|Q], R) :- renverser(Q, X),

append(X, [T], R).

Renverser une liste

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

R=[c, b, a]

?- renverser ([4, -4], [-4, 4]).

true

?- renverser ([a,b,c,d], [d, X, b, a]).

X=c