Seminar 3 – Liste eterogene în Prolog

- O listă eterogenă este o listă în care elementele sunt de tipuri diferite: numere, simboluri, sau

alte liste. De exemplu: [1, a, 2, [3,2,5], t, 1, [7,2,q], 6]. În exemplele noastre vom presupune că

sublistele dintr-o listă eterogenă nu conțin alte subliste.

- Vom lucra cu liste eterogene similar cu modul de a lucra cu liste omogene, folosind [H|T] pentru

a împărți lista în primul element și restul listei. Diferența este că va trebui să verificăm tipul

primului element, folosind una dintre următoatele funcțiile predefinite din Prolog:

o is_list(H) – returnează true dacă H este listă

o number(H) – returnează true dacă H este număr

o atom(H) – returnează true dacă H este simbol

- În general pentru a cred o listă, folosim expresia [H|T], și am discutat că H ar trebui să fie un

element și T ar trebui să fie o listă. Ce se întâmplă dacă avem alte tipuri pentru H și T?

T = 3 T = [4,5,6]

H = 2 [2|3] [2,4,5,6]

H = [1,2,3] [[1,2,3]|3] [[1,2,3],4,5,6]

1. Se dă o listă eterogenă, formată din numere și liste de numere. Să se șteargă numerele impare din sublistele care au aspect de munte (o listă are aspect de munte dacă e formată dintr-o secvență de numere crescătoare urmată de o secvență de numere descrescătoare). De exemplu: [1,2,[1,2,3,2], 6,[1,2],[1,4,5,6,7,1],8,2,[4,3,1],11,5,[6,7,6],8] => [1,2,[2,2], 6, [1,2], [4,6], 8, 2,

[4,3,1], 11,5,[6,6],8]

- Vom avea nevoie de 3 funcții:

o Una pentru a verifica dacă o listă are aspect de munte

o Una pentru a șterge numerele impare dintr-o listă

o Una pentru a procesa lista inițială, eterogenă.

- Cum verificăm dacă o listă are aspect de munte? - O variantă este să luăm un parametru extra, care să aibă valoarea 0 pentru partea crescătoare și

valoarea 1 pentru partea descrescătoare.

-

- Din moment ce am introdus un parametru extra avem nevoie și o încă o funcție, pentru a inițializa valoarea parametrului f cu valoarea 0. Valoarea 0 înseamnă că suntem pe partea crescătoare a listei. Dar ce se întâmplă dacă lista are doar partea descrescătoare? Vom intra direct în cazul care schimbă valoarea lui f în 1 și funcția va returna true, deși lista nu are aspect de munte. Pentru a evita această problemă, funcția principală va verifică dacă lista începe cu o pereche de numbere în ordinea crescătoare.

- Obs: Deoarece munte e doar una dintre funcțiile de care avem nevoie pentru a rezolva această problemă, nu e necesar să scriem o funcție separată pentru a verifica primele 2 elemente și a inițializa f. Acestea vor fi făcute în funcția principală (cea care prelucrează lista eterogenă și care apelează predicatul munte). % munte(L:list, F:integer) % model de flux: (i,i) % L – lista pe care o verificăm % F – parametru care arată dacă suntem pe partea crescătoare (0) sau descrescătoare (1) a listei munte([_], 1). munte([H1,H2|T], 0):- H1 < H2, munte([H2|T], 0). munte([H1,H2|T], 0):- H1 >= H2, munte([H2|T], 1). munte([H1,H2|T], 1):- H1 > H2, munte([H2|T], 1).

- Funcția următoare va elimina numerele impare dintr-o listă

%elimina(L:list, LR: list)

%L – lista din care stergem elemente

%LR – lista rezultat

%model de flux (i, o), (i, i)

elimina([], []).

elimina([H|T], [H|LR]):-

H mod 2 =:= 0,

elimina(T, LR).

elimina([H|T], LR):-

H mod 2 =:= 1,

elimina(T, LR).

- Și funcția care prelucreaza lista inițială

%procesare(L: list, LR: list)

%L – lista initiala, o lista eterogena

%LR – lista rezultat

%model de flux (i, o), (i, i)

procesare([], []).

procesare([H|T], [HRez|LR]):-

is_list(H),

H = [A, B|T],

A < B,

munte(H, 0),!,

elimina(H, HRez),

procesare(T, LR).

procesare([H|T], [H|LR]):-

procesare(T, LR).

2. Să considerăm următoarele predicate

%predicat pentru numere impare

%impar(i), impar(o)

impar(1).

impar(3).

impar(5).

impar(7).

impar(9).

%par (o)

par(X):- impar(N1), impar(N2), X is N1 + N2, X < 9.

par(X):- impar(N1), X is N1 * 2, X > 9.

- Ce va returna apelul par(X)?

o 2, 4, 6, 8, 4, 6, 8, 6, 8, 8, 10, 14, 18

- Ce se întâmplă dacă modificăm prima clauză de la par în modul următor:

o par(X):- !, impar(N1), impar(N2), X is N1 + N2, X < 9.

o 2, 4, 6, 8, 4, 6, 8, 6, 8, 8,

- Ce se întâmplă dacă modificăm prima clauză de la par în modul următor:

o par(X):- impar(N1), !, impar(N2), X is N1 + N2, X < 9.

o 2, 4, 6, 8

- Ce se întâmplă dacă modificăm prima clauză de la par în modul următor:

o par(X):- impar(N1), impar(N2),!, X is N1 + N2, X < 9.

o 2

3. Să considerăm predicatul următor:

p(E, L, [E|L]).

p(E, [H|T], [H|L1]):-

p(E, T, L1).

- Ce face predicatul?

- Fără a specifica un model de flux, nu putem interpreta predicatul, nu avem de unde să știm ce

face.

De fapt, acest predicat face lucruri diferite în funcție de modelul de flux

i, i, o – primește un element și o listă si inserează elementul pe toate

pozițțiile din listă

o p(11, [1,2,3], R).

R = [11, 1, 2, 3]

R = [1, 11, 2, 3]

R = [1, 2, 11, 3]

R = [1, 2, 3, 11]

i, o, i - primește un element și o listă și șterge o apariție a elementului

din listă

o p(11, R, [1,2, 11, 3, 4, 11, 5, 6, 11])

R = [1, 2, 3, 4, 11, 5, 6, 11]

R = [1, 2, 11, 3, 4, 5, 6, 11]

R = [1, 2, 11, 3, 4, 11, 5, 6]

o, i, i – primește 2 liste și returnează care element ar trebui inserat in

prima ca să ajungem la a 2-a (dacă e posibil așa ceva)

o p(X, [1,2,6], [1, 2, 5, 6])

X = 5

o, o, i – primește o listă și returnează pe rând elementele listei și lista

fără elementul returnat

o p(X, R, [1,2,3,4])

X = 1, R = [2,3,4]

X = 2, R = [1,3,4]

X = 3, R = [1,2,4]

X = 4, R = [1,2,3]