Capitolul 3

Prelucrarea listelor n Prolog Structura de date list este cea mai frecvent utilizat structur de date n programele Prolog. Acest capitol prezint n detaliu lucrul cu liste n Prolog.

3.1 Predicate de prelucrare a listelor Cele mai frecvente predicate utilizate n prelucrarea listelor sunt cel de apartenen a unui element la o list i concatenarea a dou liste. Aceste predicate sunt predefinite in SWI-Prolog: member(Element, Lista) si append(Lista1, Lista2, ListaRezultat).

n continuare, vom defini dou predicate cu efect similar cu cele dou predicate predefinite amintite mai sus.

Predicatul membru se definete astfel: % membru(Element, Lista) membru(Elem, [Elem|_]). membru(Elem, [_|Rest]) :- membru(Elem, Rest). Pentru subcapitolul 3.2 vom folosi o versiune de membru puin modificat: membru1(Elem, [Elem|_]) :- !. membru1(Elem, [_|Rest]) :- membru1(Elem, Rest). Operatorul cut mpiedic resatisfacerea scopului, n condiiile n care elementul cutat apare de mai multe ori in list.

Predicatul conc se definete astfel: % conc(Lista1, Lista2, ListaRezultat) conc([], L2, L2). conc([Prim1|Rest1], Lista2, [Prim1|Rest3]) :- conc(Rest1, Lista2, Rest3). ?- conc([a, b], [c, d, e], L3). L3 = [a, b, c, d, e]; No ?- conc([a, b], [c, d, e], L3). L3 = [a, b, c, d, e] % Enter cnd nu cutm alte soluii Yes ?- conc(L1, [c, d, e], [a, b, c, d, e]). L1 = [a, b]; No

48 CAPITOLUL 3

?- conc([a, b], L2, [a, b, c, d, e]). L2 = [c, d, e]; No

?- conc(L1, L2, [a, b]). L1 = [ ], L2 = [a, b];

L1 = [a], L2 = [b];

L1 = [a, b], L2 = [ ]; No

Se observ c, pentru cazul n care predicatul de concatenare are un singur argument neinstaniat, exist o singur soluie, iar pentru cazul n care primele dou argumente sunt neinstaniate (variabile), se obin mai multe soluii, corespunztoare tuturor variantelor de liste, care prin concatenare genereaz cea de a treia list.

n continuare, se prezint o serie de alte predicate utile n prelucrarea listelor. Eliminarea unui obiect dintr-o list. S scriem un predicat, care elimin

un obiect dintr-o list. Astfel, elim(a, [a, b, c], L) va returna n L lista [b, c]. Implementarea n Prolog este:

% elim(+El,+Lista,-ListaRez) elim(X, [X | Rest], Rest). elim(X, [Y | Rest], [Y | Rest1]) :- elim(X, Rest, Rest1).

Conform acestei implementri, elim nu va elimina dect o apariie a elementului cutat. Astfel, eliminarea lui a din lista [a,b,a,c], va genera dou soluii posibile:

?- elim(a, [a, b, a, c], L). L = [b, a, c]; L = [a, b, c]; No

Dar este posibil i ntrebarea Ce liste din care se elimina a dau ca rezultat lista [b, c]?:

?- elim(a, L, [b, c]).

PRELUCRAREA LISTELOR N PROLOG 49

L = [a, b, c]; L = [b, a, c]; L = [b, c, a]; No

Incluziunea listelor. Fie un predicat, care este adevrat, dac o list este sublista alteia.

De exemplu,

sublist([c, d, e], [a, b, c, d, e, f]) este adevrat, iar sublist([b, c, e], [a, b, c, d, e, f]) este fals. Ne putem folosi de predicatul

deja scris append. O list S este sublist a listei L, dac: 1) Exist o descompunere a lui L n L1 i L2 i 2) Exist o descompunere a lui L2 n S si L3.

Implementare:

% sublist(+SubLista,+Lista) sublist(S, L) :- append(L1, L2, L), append(S, L3, L2). Aceast implementare are un mic defect: afieaz lista vid de mai multe ori. ncercai s aflai de ce. O variant care elimin acest defect este subset: subset([], _). subset([X | Rest], L) :- member(X, L), subset(Rest, L). In plus, pentru subset nu conteaza ordinea elementelor din L.

Liniarizarea listelor. Vom scrie predicatul liniar(ListaListe, Lista), unde ListaListe este o list de elemente, care pot fi la rndul lor liste, iar n Lista se construiete liniarizarea listei ListaListe:

% liniar(+Lista,ListaLiniarizata) liniar([] , []). liniar([[ ] | Rest], Rez) :- liniar(Rest, Rez). liniar([X | Rest], [X | Rez]) :- X \= [], X \= [ _ | _ ], liniar(Rest, Rez). liniar([[X | Rest] | RestList], Rez) :- liniar([X, Rest | RestList], Rez). Un exemplu de execuie este:

?- liniar([1, 2, [3, 4], [5, [6, 7], [[8], 9]]], L). L = [1, 2, 3, 4, 5, 6, 7, 8, 9] Yes

50 CAPITOLUL 3

3.2 Predicate care utilizeaz liste n acest subcapitol prezentm cteva predicate care utilizeaz liste.

Mulimi. Mulimile pot fi reprezentate n Prolog ca liste. Predicatul multime(L, M) transform lista L n mulimea M. multime([], []). multime([X | Rest], Rez) :- membru1(X, Rest), multime(Rest, Rez). multime([X | Rest], [X | Rez]) :- not(membru1(X, Rest)), multime(Rest, Rez).

Predicatul de definire a interseciei a dou liste, prezentat n capitolul 4, se poate aplica i pentru obinerea interseciei a dou mulimi. Prezentm n continuare, predicatul de determinare a reuniunii a dou mulimi.

% reun(+L1,+L2,-L) reun([],L,L). reun([X | Rest], L, Rez) :-membru1(X,L), reun(Rest,L,Rez). reun([X | Rest], L, [X | Rez]) :-not(membru1(X,L)), reun(Rest,L,Rez).

Problema drumurilor. Fie o baz de date cu drumuri ntre orae, de forma drum(oras1, oras2): drum(bucuresti, ploiesti). drum(bucuresti, cheia). drum(cheia, brasov). drum(brasov, bucuresti). drum(cheia, sinaia). drum(ploiesti, sinaia). drum(ploiesti, brasov).

Predicatul traseu(X, Y, T) este adevrat dac se poate ajunge de la oraul X la oraul Y, calculnd i traseul T ntre cele dou orae. Drumurile sunt bidirecionale (dac exista drum de la X la Y, atunci exist drum de la Y la X). membru2(X, [Y | T]) :- X == Y, ! ; membru2(X, T). traseu(Y, X) :- traseu(X, Y, [X]). traseu(Y, Y, Traseu) :- write(Traseu), nl. traseu(X, Y, Traseu) :- (drum(X, Z) ; drum(Z, X)), not(membru2(Z, Traseu)), traseu(Z, Y, [Z | Traseu]). traseu( _ , _ , _ ) :- write('Nu exista traseu.'), nl. test :- traseu(bucuresti, sinaia), traseu(sinaia, bucuresti), traseu(bucuresti, ploiesti), traseu(ploiesti, bucuresti), traseu(cheia, craiova).

PRELUCRAREA LISTELOR N PROLOG 51

?- test. [bucuresti, brasov, cheia, sinaia] [sinaia, ploiesti, bucuresti] [bucuresti, brasov, cheia, sinaia, ploiesti] [ploiesti, bucuresti] Nu exista traseu. Yes

Descompunerea unui numr n factori primi. Predicatul descomp(N, Lista) primete un numr ntreg N i ntoarce o list a factorilor primi ai numrului N; de exemplu: descomp(12, [2, 2, 3]) este adevrat. % descomp(+N,-L) descomp(N, L) :- factp(N, L, 2). factp(1, [ ], _ ). factp(N, [Divizor | Lista], Divizor) :- N > 1, 0 is N mod Divizor, N1 is N // Divizor, factp(N1, Lista, Divizor). factp(N,Lista,Divizor) :- N > 1, not(0 is N mod Divizor), D1 is Divizor + 1, factp(N, Lista, D1).

Verificare palindrom. Predicatul palindrom(Lista) verific dac o list este palindrom. Un palindrom este o secven care, dac este parcurs de la stnga la dreapta sau de la dreapta la stnga, este identic; de exemplu: [a, b, c, b, a] sau [a, b, c, c, b, a]. % Idee: o lista este palindrom daca este egala cu inversa ei. palindrom(L) :- reverse(L, [], L). reverse([], Acc, Acc). reverse([X | Rest], Acc, L) :- reverse(Rest, [X | Acc], L).

Verificare list sortat. Predicatul sortcresc verific dac o list de numere ntregi este sortat cresctor.

% sortcresc(Lista) sortcresc([ ]). % lista vida se considera sortata sortcresc([ _ ]). % lista cu un singur element este sortata sortcresc([X, Y | Rest]) :- X =< Y, sortcresc([Y | Rest]).

?- sortcresc([1, 2, 3, 4]). Yes

52 CAPITOLUL 3

?- sortcresc([1, 3, 5, 4]). No ?- sortcresc([ ]). Yes

Dac se consider c lista vid nu este o list sortat cresctor atunci se poate elimina faptul:

sortcresc([ ]).

din definiia predicatului sortcresc, comportarea lui pentru liste diferite de lista vid rmnnd aceeai.

3.3 Exerciii propuse EP1. Aflai care este defectul predicatului sublist.

EP2. Folosind predicatul elim, punei ntrebarea: Ce elemente se pot elimina din [a, b, a, c] i ce list rezult n cazul fiecrei eliminri? EP3. S se defineasc i s se exemplifice cu cte dou exemple n Prolog, urmtoarele predicate de prelucrare a listelor:

1) invers(Lista, ListaInversata) - inverseaz elementele unei liste. S se scrie dou variante ale predicatului de inversare a unei liste: o variant n care lista inversat este calculat pe ramura de revenire din recursivitate i o variant n care lista inversat este calculat pe ramura de avans n recursivitate.

2) reun(Lista1, Lista2, ListaRez) - produce ListaRez, care conine reuniunea elementelor din Lista1 i din Lista2. Pe baza predicatului mulime din seciunea 3.2, se va da o implementere alternativ a predicatului reun.

EP4. S se scrie predicatul Prolog substitutie(X, Y, L1, L2), unde L2 este rezultatul substituirii tuturor apariiilor lui X din lista L1 cu Y, producnd lista L2.

Ex: substitutie(a, x, [a, [b,a,] c], L2) va produce: L2 = [x, [b, x], c]. EP5. S se scrie predicatul imparte(L, L1, L2) care mparte lista L n dou subliste L1 i L2, care au un numr de elemente aproximativ egal, fr a calcula lungimea listei L.

Ex: imparte([a, b, c, d, e], L1, L2) va produce: L2 = [a, b, c] i L3 = [d, e].