Prelucrarea listelor in Prolog

Prelucrarea listelor in Prolog

Structura de date lista este cea mai frecvent utilizata structura de date in programele Prolog. Acest capitol prezinta in detaliu lucrul cu liste in Prolog.

Predicate de prelucrare a listelor

Cele mai frecvente predicate utilizate in prelucrarea listelor sunt cel de apartenenta a unui element la o lista si concatenarea a doua liste. Aceste predicate sunt predefinite in SWI-Prolog: member(Element, Lista) si append(Lista1, Lista2, ListaRezultat).

In continuare, vom defini doua predicate cu efect similar cu cele doua predicate predefinite amintite mai sus.

Predicatul membru se defineste astfel:

% membru(Element, Lista)

membru(Elem, [Elem|_]).

membru(Elem, [_|Rest]) :- membru(Elem, Rest).

Pentru subcapitolul 2 vom folosi o versiune de membru putin modificata:

membru1(Elem, [Elem|_]) :- !.

membru1(Elem, [_|Rest]) :- membru1(Elem, Rest).

Operatorul cut impiedica resatisfacerea scopului, in conditiile in care elementul cautat apare de mai multe ori in lista.

Predicatul conc se defineste 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 cand nu cautam alte solutii

Yes

?- conc(L1, [c, d, e], [a, b, c, d, e]).

L1 = [a, b];

No

?- 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 observa ca, pentru cazul in care predicatul de concatenare are un singur argument neinstantiat, exista o singura solutie, iar pentru cazul in care primele doua argumente sunt neinstantiate (variabile), se obtin mai multe solutii, corespunzatoare tuturor variantelor de liste, care prin concatenare genereaza cea de a treia lista.

In continuare, se prezinta o serie de alte predicate utile in prelucrarea listelor.

Eliminarea unui obiect dintr‑o lista Sa scriem un predicat, care elimina un obiect dintr‑o lista. Astfel, elim(a, [a, b, c], L) va returna in L lista [b, c]. Implementarea in Prolog este:

% elim(+El,+Lista,-ListaRez)

elim(X, [X | Rest], Rest).

elim(X, [Y | Rest], [Y | Rest1]) :- elim(X, Rest, Rest1).

Conform acestei implementari, elim nu va elimina decat o aparitie a elementului cautat. Astfel, eliminarea lui a din lista [a,b,a,c], va genera doua solutii posibile:

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

L = [b, a, c]

L = [a, b, c]

No

Dar este posibila si intrebarea "Ce liste din care se elimina a dau ca rezultat lista [b, c]?":

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

L = [a, b, c]

L = [b, a, c]

L = [b, c, a]

No

Incluziunea listelor Fie un predicat, care este adevarat, daca o lista este sublista alteia.

De exemplu,

sublist([c, d, e], [a, b, c, d, e, f]) este adevarat, iar

sublist([b, c, e], [a, b, c, d, e, f]) este fals. Ne putem folosi de predicatul deja scris append. O lista S este sublista a listei L, daca:

Exista o descompunere a lui L in L1 si L2 si

Exista o descompunere a lui L2 in S si L

Implementare:

% sublist(+SubLista,+Lista)

sublist(S, L) :- append(L1, L2, L), append(S, L3, L2).

Aceasta implementare are un mic defect: afiseaza lista vida de mai multe ori. Incercati sa aflati de ce. O varianta care elimina 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 lista de elemente, care pot fi la randul lor liste, iar in Lista se construieste 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 executie este:

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

L = [1, 2, 3, 4, 5, 6, 7, 8, 9]

Yes

Predicate care utilizeaza liste

In acest subcapitol prezentam cateva predicate care utilizeaza liste.

Multimi. Multimile pot fi reprezentate in Prolog ca liste. Predicatul multime(L, M) transforma lista L in multimea 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 intersectiei a doua liste, prezentat in capitolul 4, se poate aplica si pentru obtinerea intersectiei a doua multimi. Prezentam in continuare, predicatul de determinare a reuniunii a doua multimi.

% 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 baza de date cu drumuri intre orase, 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 adevarat daca se poate ajunge de la orasul X la orasul Y, calculand si traseul T intre cele doua orase. Drumurile sunt bidirectionale (daca exista drum de la X la Y, atunci exista 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).

test.

[bucuresti, brasov, cheia, sinaia]

[sinaia, ploiesti, bucuresti]

[bucuresti, brasov, cheia, sinaia, ploiesti]

[ploiesti, bucuresti]

Nu exista traseu.

Yes

Descompunerea unui numar in factori primi. Predicatul descomp(N, Lista) primeste un numar intreg N si intoarce o lista a factorilor primi ai numarului N; de exemplu: descomp(12, [2, 2, 3]) este adevarat.

% 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) verifica daca o lista este palindrom. Un palindrom este o secventa care, daca este parcursa de la stanga la dreapta sau de la dreapta la stanga, este identica; 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 lista sortata Predicatul sortcresc verifica daca o lista de numere intregi este sortata crescator.

% 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

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

No

?- sortcresc([ ]).

Yes

Daca se considera ca lista vida nu este o lista sortata crescator atunci se poate elimina faptul:

sortcresc([ ]).

din definitia predicatului sortcresc, comportarea lui pentru liste diferite de lista vida ramanand aceeasi.

Exercitii propuse

EP1. Aflati care este defectul predicatului sublist.

EP2. Folosind predicatul elim, puneti intrebarea: "Ce elemente se pot elimina din [a, b, a, c] si ce lista rezulta in cazul fiecarei eliminari?"

EP Sa se defineasca si sa se exemplifice cu cate doua exemple in Prolog, urmatoarele predicate de prelucrare a listelor:

invers(Lista, ListaInversata) - inverseaza elementele unei liste. Sa se scrie doua variante ale predicatului de inversare a unei liste: o varianta in care lista inversata este calculata pe ramura de revenire din recursivitate si o varianta in care lista inversata este calculata pe ramura de avans in recursivitate.

reun(Lista1, Lista2, ListaRez) - produce ListaRez, care contine reuniunea elementelor din Lista1 si din Lista2. Pe baza predicatului multime din sectiunea 2, se va da o implementere alternativa a predicatului reun.

EP4. Sa se scrie predicatul Prolog substitutie(X, Y, L1, L2), unde L2 este rezultatul substituirii tuturor aparitiilor lui X din lista L1 cu Y, producand lista L2.

Ex: substitutie(a, x, [a, [b,a,] c], L2) va produce: L2 = [x, [b, x], c].

EP5. Sa se scrie predicatul imparte(L, L1, L2) care imparte lista L in doua subliste L1 si L2, care au un numar de elemente aproximativ egal, fara a calcula lungimea listei L.

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