Pentru structuri fixe de date, putem considera termeni corespunzători - de exemplu, putem folosi persoană(ocupaţie(elev), nume('Popa'), prenume('Ion'), data_naşterii(1995, iunie, 1)) pentru a reprezenta persoane (printr-un număr fixat de "câmpuri"):
persoană(
ocupaţie(elev),
nume('Pop'), prenume('Ion'),
data_naştere(2001, iunie, 1)
).
persoană(
ocupaţie(profesor),
nume('Bar'), prenume('Jan'),
data_naştere(1960, mai, 10)).
Aceasta seamănă cu crearea unui tabel în MySQL (sau alt sistem de gestiune a bazelor de date) şi putem formula diverse interogări (analog SELECT-urilor uzitate în MySQL):
% Care "persoane" au ocupaţia elev. În MySQL am formula:
% SELECT nume,prenume FROM persoana WHERE ocupatie=elev;
% unde `persoana`, `ocupatie`, etc. desemnează tabelul MySQL şi câmpurile aferente
?- persoană(ocupaţie(elev), Nume, Prenume, _).
Nume = nume('Pop'),
Prenume = prenume('Ion').
% lista persoanelor şi ocupaţiilor
?- persoană(ocupaţie(Ocup), nume(Nume), prenume(Prenume), _),
writeln((Nume, Prenume: Ocup)), fail.
Pop,Ion:elev
Bar,Jan:profesor
false.
Dacă avem de lucrat cu structuri de date cu număr variabil de componente, putem folosi liste.
O listă este scrisă ca o secvenţă de elemente separate prin virgulă şi încadrată de paranteze pătrate: [1, 2, 3], sau [luni, marţi, joi], sau [zi('luni', 1), zi('marţi', 2), zi('joi', 4), zi(X, 3)]. Elementele listei pot fi atomi, sau termeni Prolog oarecare (inclusiv variabile), sau pot fi alte liste.
Primul element al unei liste nevide este numit head (capul listei); lista din spatele acestuia (lista rămasă după ce s-ar elimina head-ul ei) este numită tail ("restul" listei, suita sau escorta listei).
Şablonul [ H | T ] corespunde unei liste cu cel puţin un element, având capul H şi suita T (unde H şi T pot fi nişte liste). Această construcţie (cu operatorul |) permite specificarea valorilor prin potrivire, sau "egalare" (în loc de "asignare"); de exemplu:
?- assertz(mută([Head | Tail], [Tail | Head])). % adaugă mută/2 în baza de date true. % mută/2 "inversează" părţile unei liste ([H|T] trece în [T|H]; dar şi invers!) ?- mută([a, b, c], X). % [a, b, c] are Head = a şi Tail = [b, c] X = [[b, c]|a]. % rezultă o listă cu 2 elemente (Tail fiind tratat ca listă) ?- mută([[a, b] | c], X). % Head = [a, b], Tail = [c] (lista are 2 elemente) X = [c, a, b]. % elementele Head-ului au fost mutate la sfârşit ?- mută(X, [a, b, c]). % din care listă provine prin "mutare", lista [a,b,c]? X = [[b, c]|a]. % (argumentele lui mută/2 au roluri "input/output" simetrice)
De fapt şi listele sunt termeni compuşi (notaţia cu paranteze pătrate este doar o "scurtătură"):
?- functor([1,2,3], Functor, Arity). % determină functorul şi aritatea unui termen Functor = '.', % functorul rezervat pentru liste Arity = 2. % două argumente: "Head" şi "Tail"
O listă are ca functor punctul şi este o structură binară: ./2. De exemplu, [a, b] este echivalentul termenului .(a, .(b, [])); putem verifica folosind write_canonical (sau display):
?- write_canonical([a, b, c]). % produce reprezentarea internă a termenului .(a,.(b,.(c,[]))) % sau, scris cu "|": [a | [b | [c | []] ]] true.
Operatorul denumit "univ" şi notat =.. permite conversia între liste şi termeni complecşi:
?- X =.. [data_naştere, 2000, _, _], % "univ" transformă lista în termen complex persoană(_, nume(Nume), prenume(Prenume), X). % caută "potriviri" cu termenul rezultat X = data_naştere(2000, iunie, 1), % după "univ" şi "potrivire" Nume = 'Pop', Prenume = 'Ion' ; % pot exista şi alte potriviri (dacă s-au adăugat şi alte "persoană")
Iar pentru un exemplu de conversie inversă, de la termen la listă:
?- identitate(nume('Bar'), prenume('Goe'), cod(1234567890123)) =.. X.
X = [identitate, nume('Bar'), prenume('Goe'), cod(1234567890123)].
Functorul şi argumentele termenului "identitate" au devenit după =.., elementele unei liste.
Există submulţimi ale unei mulţimi de întregi, care să aibă ca sumă o valoare dată? (caz particular de problema rucsacului). În problemă de echilibru am tratat (inclusiv în Prolog) cazul când mulţimea dată este segmentul natural [n] - de sumă T(n) = n(n+1)/2 - şi suma de atins este jumătate din T(n) sau din T(n)+1 (submulţimile căutate sunt "s-partiţii" ale lui [n]).
Imaginea obişnuită a problemei este aceea a unui rucsac care trebuie umplut cu nişte obiecte; acestea corespund numerelor date, iar capacitatea rucsacului este suma de atins.
Avem de descris relaţia dintre lista obiectelor externe rucsacului, lista obiectelor deja introduse în rucsac şi capacitatea rămasă de ocupat în interiorul rucsacului:
rucsac(Obiecte_externe, Capacitate_liberă, Obiecte_interne).
Iniţial "capacitatea liberă" este suma de atins, iar "obiecte interne" este lista vidă; când "capacitate liberă" a ajuns zero, rucsacul s-a umplut şi "obiecte interne" reprezintă o soluţie (numere având ca sumă valoarea dată iniţial).
Un "obiect" {X} se va putea transfera din exterior în interior, dacă numărul X respectiv nu depăşeşte "capacitatea liberă" existentă la momentul respectiv şi în acest caz, noua stare a problemei este:
X ≤ Capacitate_liberă şi
rucsac(Obiecte_externe - {X}, Capacitate_liberă - X, Obiecte_interne + {X}).
Furnizarea unui obiect {X} care să fie eventual transferat în rucsac nu ţine de rucsac, ci ţine mai degrabă de organizarea internă a listei obiectelor disponibile (această listă ar putea fi ordonată de la bun început după un criteriu prestabilit, în aşa fel încât obiectul cel mai convenabil de adăugat în rucsac la un moment dat să fie cel aflat în vârful listei obiectelor disponibile la acel moment).
Prin urmare, putem considera că {X} este "head"-ul listei Obiecte_externe şi putem realiza operaţia descrisă mai sus implicând liste (operând implicit pe "head"-urile lor):
X ≤ Capacitate_liberă, % dacă X încape în rucsac Capacitate_încă_liberă is Capacitate_liberă - X, % cât spaţiu rămâne după includere rucsac([X | Alte_Obiecte_externe], /* separă headul X */ Capacitate_încă_liberă, /* rămas neocupat în rucsac */ [X | Obiecte_interne] /* adaugă X "în vârful" rucsacului */ ).
Dar se poate ca obiectul din capul listei să nu încapă în rucsac (nu îndeplineşte prima dintre clauzele de mai sus); în acest caz, trebuie investigată coada listei - cu alte cuvinte, trebuie ignorat capul listei şi trebuie reluată problema angajând numai restul listei de obiecte externe rucsacului, ajungând deci la următoarea regulă recursivă:
rucsac([_|Alte_obiecte], Capacitate_liberă, Obiecte_interne) :-
rucsac(Alte_obiecte, Capacitate_liberă, Obiecte_interne).
Dar ignorarea capului listei şi reluarea problemei pentru restul listei, va conduce la un anumit moment la situaţia în care lista Alte_obiecte vizată mai sus, devine vidă; în acest caz nu mai avem obiecte de adăugat în rucsac şi am găsit o soluţie numai dacă "Capacitate_liberă" a devenit zero:
rucsac([], 0, []). % rucsacul s-a umplut (şi avem o soluţie a problemei)
Reunind descrierile de mai sus (dar "standardizând" termenii) obţinem următorul program Prolog:
rucksack([Next|Others], Target, [Next|Rest]):- % încarcă Next (din capul listei) Next =< Target, % dacă încape Remainder is Target - Next, % cât rămâne de acoperit rucksack(Others, Remainder, Rest). % repetă, pentru restul obiectelor rucksack([_|Others], Target, Load):- % ignoră capul listei (nu încape) rucksack(Others, Target, Load). % continuă asupra celorlalte obiecte rucksack([], 0, []). % rucsacul s-a umplut (s-a obţinut o soluţie)
Termenii folosiţi în comentarii, "repetă" şi "continuă" (asupra restului obiectelor) vizează mecanismul de backtracking al interpretorului de Prolog; un exemplu de invocare:
?- rucksack([9, 10, 11, 12, 25, 50, 15, 80], 100, R).
R = [9, 11, 80] ; % 9 + 11 + 80 = 100
R = [10, 25, 50, 15] ;
false.
În problemă de echilibru, "rucsacul" avea capacitatea T(n)/2 sau (T(n)+1)/2 - în funcţie de valoarea n mod 4, unde T(n)=n(n+1)/2 - şi trebuia "umplut" cu valori 1..n; pentru a aborda acum acest caz, putem adăuga programului de mai sus:
halfTrig(N, Suma) :- % vezi problemă de echilibru R is N mod 4, ( R =\= 0, R =\= 3 -> Suma is (N * (N + 1) +2) / 4 % (T(n)+1)/2 dacă n mod 4 este 1 sau 2 ; Suma is N * (N + 1) / 4 % T(n)/2 dacă n mod 4 este 0 sau 3 ). esparts(N) :- halfTrig(N, S), % S = T(n)/2 sau (T(n)+1)/2 numlist(1, N, L1n), % rezultă lista L1n = [1, 2, ..., N] % rucksack(L1n, S, _). % pentru a folosi 'count' (numărul de soluţii) rucksack(L1n, S, X), % dacă vrem soluţiile (nu numărul lor) writeln(X), % !. % dacă vrem numai prima soluţie fail. % dacă vrem toate soluţiile
O interogare ca ?- esparts(10). va lista soluţiile, pentru n = 10. Dacă ne interesează numai numărul de soluţii, putem decomenta linia a treia din predicatul "esparts" de mai sus (comentând restul liniilor) şi putem folosi predicatul count din Partea (I) - "Numărarea soluţiilor, în Prolog".
Interesant este de a compara durata de execuţie: prima soluţie pentru n = 1000, se obţinuse în problemă de echilibru (II) în mai puţin de 6 secunde; cu programul de mai sus (după ce activăm "cut"-ul !. şi comentăm ultima linie) avem:
?- time(esparts(1000)).
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,
. . . . . .
,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,795,999,1000]
% 504,203,499 inferences, 122.365 CPU in 122.439 seconds (100% CPU, 4120485 Lips)
Timpul rezultat este de 20 de ori mai mare; în programul de aici - care este mai general şi într-adevăr, mai elegant - se parcurg (cu revenire) toate elementele listei (spre deosebire de programul similar ca scop din problemă de echilibru (II), unde nu se angaja lista valorilor, ci foloseam "between(Minim, N, Numar_de_inclus)" pentru a genera restrictiv şi într-o anumită ordine, valori acceptabile).
Să se achite o anumită sumă, folosind - eventual, într-un număr minimal - monede şi bancnote de valori şi cantităţi date.
De exemplu, să se plătească suma de 1.42 dolari dispunând de 6 bancnote de 1 dolar, 8 monede de 25 cenţi, 10 monede de 10 cenţi, un nickel (5 cenţi) şi 5 penny (un cent).
Vom evita aritmetica în "virgulă mobilă" (în care numere ca 0.1 nu pot fi reprezentate exact), exprimând valorile monedelor într-o aceeaşi unitate (un dolar = 100 cenţi).
Putem vedea aceasta şi ca un caz particular de "problema rucsacului", invocând predicatul anterior:
?- rucksack([100, 25,25,25,25, 10,10,10,10, 5, 1,1,1,1,1], 142, Change). Change = [100, 25, 10, 5, 1, 1] ; Change = [100, 25, 10, 5, 1, 1] ; Change = [100, 25, 10, 5, 1, 1]
Soluţia [100,25,10,5,1,1] va fi calculată şi afişată de… 160 de ori (4 monede de 25 ORI 4 monede de 10 ORI 10 posibilităţi de a lua doi de 1 din cei cinci). Putem evita înregistrarea şi afişarea duplicatelor (dar aceasta sunt totuşi efectiv calculate) folosind meta-predicatul setof:
?- setof( Change,
rucksack([100,25,25,25,25,10,10,10,10,5,1,1,1,1,1], 142, Change),
ListChange ),
member(X, ListChange), writeln(X), fail.
[25,25,25,25,10,10,10,10,1,1]
[100,10,10,10,10,1,1]
[100,25,10,5,1,1]
false.
Deosebirea faţă de "rucksack"-ul tratat mai sus constă în faptul că acum lista iniţială ar conţine valori care se pot repeta de un anumit număr de ori; în loc de "Remainder is Target - Next" ar trebui acum "Remainder is Target - Nr * Next", cu Nr între 0 şi numărul monedelor de valoare Next.
Să declarăm piesele (ca listă de elemente [Număr, Valoare_monedă]) şi suma de schimbat:
pieces([[6, 100], [8, 25], [10, 10], [1, 5], [5, 1]]). to_change(142).
Obs. Alegerea bună era [Valoare, Număr]! Între altele, se va dovedi important să ordonăm piesele descrescător după Valoare, ceea ce - în cazul reprezentării prin [Valoare, Număr] - se obţine foarte simplu, adăugând: pieces(X, Y) :- pieces(X), sort(X, Z), reverse(Z, Y). (Y va fi lista pieselor, dar ordonată descrescător după valoare).
Pentru a schimba suma în piesele indicate putem formula (asemănător cu "rucksack"):
change([], [], 0). % avem soluţie dacă suma rămasă de schimbat este zero change([[Nr_, Value]|Pieces], [[Nr, Value]|ExPieces], Target):- between(0, Nr_, Nr), % Nr posibil de piese de tip Value Rest is Target - Nr * Value, % suma care mai rămâne de schimbat Rest >= 0, change(Pieces, ExPieces, Rest). % ExPieces acoperă Rest cu Pieces
Putem verifica "change" în mod expeditiv, cu date oarecare furnizate direct:
?- change([[4, 10], [3, 50], [2, 100], [5, 1]], Xchg, 130).
Xchg = [[3, 10], [0, 50], [1, 100], [0, 1]] ; % 3*10 + 1*100 = 130
Xchg = [[3, 10], [2, 50], [0, 100], [0, 1]] ;
false.
sau ceva mai complex, folosind datele "pieces", "to_change" din program:
?- pieces(Pieces), to_change(Sum),
| change(Pieces, ExchPieces, Sum),
| writeln(ExchPieces), fail.
[[0,100],[2,25],[9,10],[0,5],[2,1]] % 2*25 + 9*10 + 2*1 = 142
[[0,100],[3,25],[6,10],[1,5],[2,1]]
. . . . .
Dar este mai convenabil să adăugăm în program un predicat corespunzător:
exchange :- pieces(Pieces), to_change(Sum), change(Pieces, ExchPieces, Sum), scrie(ExchPieces), fail. scrie(ListPieces) :- findall([N, P], (member([N, P], ListPieces), N > 0), As), writeln(As).
oferindu-ne o "scurtătură" pentru interogarea anterioară şi mai mult, posibilitatea de a modifica ulterior maniera de afişare (rescriind procedura "scrie" de mai sus):
?- exchange.
[[2,25],[9,10],[2,1]] % nu mai afişează valori ca [0, 100]
[[3,25],[6,10],[1,5],[2,1]]
[[4,25],[4,10],[2,1]]
. . . . .
Putem prefera următoarea reformulare, în care găsim "deodată" lista tuturor soluţiilor (invocând "change" în "findall") şi adăugăm un antet conţinând datele problemei, iar pentru fiecare soluţie precizăm numărul de monede folosite pentru schimbul respectiv:
exchange1 :- pieces(Pieces), to_change(Target), DP =.. [disponibil, Pieces], SS =.. [suma_de_schimbat, Target], write(DP), tab(4), writeln(SS), nl, findall(ExchPieces, (change(Pieces, ExchPieces, Target)), AllSol), member(Sol, AllSol), findall([N, P], (member([N, P], Sol), N > 0), As), findall(N, member([N, _], As), C1), sumlist(C1, S), X =.. [schimb, As], Y =.. [nr_piese, S], write(X), put_char('\t'), writeln(Y), fail.
Operatorul "univ" =.. ne-a permis să construim termenii expliciţi "disponibil", "schimb", etc. Redăm rezultatul invocării (dar aliniind manual coloana "nr_piese"):
?- exchange1. disponibil([[6,100],[8,25],[10,10],[1,5],[5,1]]) suma_de_schimbat(142) schimb([[2,25],[9,10],[2,1]]) nr_piese(13) schimb([[3,25],[6,10],[1,5],[2,1]]) nr_piese(12) schimb([[4,25],[4,10],[2,1]]) nr_piese(10) schimb([[5,25],[1,10],[1,5],[2,1]]) nr_piese(9) schimb([[1,100],[4,10],[2,1]]) nr_piese(7) schimb([[1,100],[1,25],[1,10],[1,5],[2,1]]) nr_piese(6) false.
Soluţiile au fost obţinute (şi afişate ca atare, fără a implica "sort") în ordinea descrescătoare a valorii "nr_piese" corespunzătoare - ceea ce se explică prin faptul că piesele iniţiale au fost indicate în lista "pieces" în ordinea descrescătoare a valorilor monedelor; se poate verifica (folosind de exemplu, time, sau profile şi eventual, angajând ca date o listă mai lungă de piese) faptul că numărul de inferenţe va fi mai mare în cazul când piesele sunt date iniţial într-o ordine oarecare.
Obs. Datele folosite aici sunt preluate din Finite Domain Constraint Programming in Oz - tutorial (we can pay $1.42 with 1 one dollar bill, 1 quarter, 1 dime, 1 nickel, and 2 pennies. This payment uses the minimal number of bills and coins - soluţia cu nr_piese(6), mai sus).
Programul de mai sus face doar aluzie la "monede" - el acoperind de fapt orice problemă de descompunere a unui număr; de exemplu, redefinind în program:
pieces([[1, 9], [1, 8], [2, 3], [3, 2], [1, 1]]). to_change(15).
vom obţine descompunerile numărului 15, constituite din cel mult un termen 9, cel mult un 8, cel mult doi de 3, cel mult trei de 2 şi cel mult un termen 1:
?- exchange. [[1,8],[3,2],[1,1]] % 8 + 2 + 2 + 2 + 1 = 15 [[1,8],[1,3],[2,2]] [[1,8],[2,3],[1,1]] [[1,9],[3,2]] % 9 + 2 + 2 + 2 = 15 [[1,9],[1,3],[1,2],[1,1]] [[1,9],[2,3]] false.
Evident că aplicând programul de mai sus pe cazul general al descompunerii unui număr (fără legătură cu "monede"), termenii "schimb", "nr_piese" (introduşi artificial, prin operatorul "univ") îşi pierd sensul; pe de altă parte, când lista "pieces" este mai lungă - programul devine insuficient în privinţa eficienţei, încât el (deşi acoperă cazul general) este chiar inadecvat pentru cazul "general".
Să încercăm o reformulare a programului de mai sus, încât să exprimăm cu un caracter declarativ mai pronunţat, problema monedelor propriu-zise. Monedele au valori prestabilite şi avem numai câteva tipuri de monede (spre deosebire de termenii descompunerii unui număr, care pot fi oricât de mulţi); de exemplu, dolarul american are exact cinci subdiviziuni monetare - vezi USA coins.
În mod firesc, un stoc disponibil de monede este constituit implicit în ordinea descrescătoare a valorii; am putea să-l descriem astfel:
stocks([Dollar, Half, Quarter, Dime, Nickel, Penny], Stock) :- % stock(Denumire, Valoare, Cantitate) ordonat descrescător după Valoare AllPcs = [ stock(dollar, 100, Dollar), stock(half, 50, Half), stock(quarter, 25, Quarter), stock(dime, 10, Dime), stock(nickel, 5, Nickel), stock(penny, 1, Penny) ], % reţine numai piesele pentru care Cantitate este nenul findall(Nz, ( member(stock(D,V,N), AllPcs), N > 0, Nz = stock(D,V,N) ), Stock).
De exemplu:
?- stocks([6, 0, 8, 10, 1, 5], Stock),
| member(stock(Name, _, Quantity), Stock),
| write(Quantity), put_char(' '), write(Name), tab(2),
| fail.
6 dollar 8 quarter 10 dime 1 nickel 5 penny % stocul de monede
false.
În rest, nu avem decât modificări minore, faţă de programul de mai sus (şi nu este necesar să mai folosim "univ", pentru a introduce alţi termeni):
change_([], [], 0). change_( [stock(Name, Value, Nr_) |Pieces], [stock(Name, Value, Nr) |ExPieces], Target ) :- between(0, Nr_, Nr), Rest is Target - Nr * Value, Rest >= 0, change_(Pieces, ExPieces, Rest). exchange_(ListAllPieces, Sum) :- % ?- exchange_([6,0,8,10,1,5], 142). stocks(ListAllPieces, Pieces), change_(Pieces, ExchPieces, Sum), scrie_(ExchPieces), fail. scrie_([]) :- nl. scrie_([stock(Name, _, Nr) | _]) :- Nr > 0, maplist(write, [Nr, ' ', Name, ' ', ' ']). scrie_([_|Tail]) :- scrie_(Tail).
De exemplu, obţinem modalităţile de a schimba 1.42$ pe baza stocului de mai sus:
?- exchange_([6, 0, 8, 10, 1, 5], 142). 2 quarter 9 dime 2 penny 3 quarter 6 dime 1 nickel 2 penny 4 quarter 4 dime 2 penny 5 quarter 1 dime 1 nickel 2 penny 1 dollar 4 dime 2 penny 1 dollar 1 quarter 1 dime 1 nickel 2 penny false.
maplist a aplicat predicatul "write" fiecărui termen din lista indicată; însă o soluţie de afişare mai bună se obţinea direct, cu writef('%3r %8l', [Nr, Name]). (Nr va fi afişat pe 3 coloane, aliniat la dreapta; apoi urmează un spaţiu şi Name - pe 8 coloane, aliniat la stânga).
vezi Cărţile mele (de programare)