Prolog - numerály a seznamy

Dnes si zkusíme napsat trochu složitější programy v Prologu, na kterých si můžeme vyzkoušet různé složitější věci, například si ukázat obousměrnost výpočtů. Poslouží nám k tomu Peanova aritmetika. V té máme jedinou konstantu 0, a jedinou funkci S(x), která vrací následníka x. Dají se v ní potom nadefinovat numerály (čísla) tak, že numerál n je n-krát aplikovaná operace S na 0.

Napišme napřed proceduru pro součet dvou numerálů.

% soucet(X,Y,Z)
% implementuje scitani numeralu, Z = X + Y
% prvni klauzule: 0+Y=Y
% druha klauzule: s(X)+Y=s(X+Y)
soucet(0,Y,Y).
soucet(s(X), Y, s(Z1)):-soucet(X,Y,Z1).

Pohrajte si s touto procedurou. Co se stane, když dáte na různá místa proměnnou místo numerálu? Co třeba dělá soucet(X, s(0), s(s(0)))? A co soucet(X,Y,s(s(s(0))))?

Napište predikát, který vytvoří dvojnásobek zadaného numerálu, a predikát, který rozhodne jestli daný numerál reprezentuje sudé číslo.

dvakrat(X,Y):-soucet(X,X,Y).
sude(X):-soucet(Z,Z,X).

Zkuste napsat další predikáty pro práci s numerály – součin a mocninu. Napište predikát, který rozhodne, jestli zadaný term je číslo.

% soucin(X,Y,Z) -- spocita XY a vrati vysledek v Z
soucin(_,0,0).
soucin(0,_,0).
soucin(X, s(Y), Z2):-soucin(X,Y,Z1),soucet(Z1,X,Z2).

Umí předcházející procedura soucin/3, rozkládat čísla? Co se stane, když zavoláte soucin(X,Y,s(s(s(s(s(s(0))))))). Proč? Upravte soucin/3 tak, aby v tomhle případě fungoval.

% lt(X,Y) -- vrati true, kdyz X < Y
lt(X,s(X)).
lt(X,s(Y)):-lt(X,Y).

% cislo(X) -- rozhoduje, zda X je cislo.
cislo(s(X)):-cislo(X).
cislo(0).

soucin1(_, 0, 0).
soucin1(0, _, 0).
soucin1(s(X), Y, Z):-soucet(A, Y, Z), soucin1(X, Y, A).

Jak byste v prologu reprezentovali datovou strukturu? Co třeba struktura pro datum?

Prolog umí pracovat také se seznamy, ale na rozdíl od jiných jazyků neumí přistupovat rychle na dané místo v seznamu. Přístup trvá lineárně dlouho.

Seznamy se píšou do hranatých závorek, jejich prvky se oddělují čárkou např. [1,2,3] je seznam čísel 1, 2 a 3; [1,2,[3,4]] je seznam, který obsahuje čísla 1,2 a seznam [3,4]. Prázdný seznam se zapíše jako []. Seznam se dá rozdělit na první prvek a zbytek pomocí [X|Xs], X potom obsahuje první prvek seznamu a Xs zbytek. Podobně je možné získat i první dva prvky seznamu a zbytek jako [X1, X2 | Xs]. Kratší než dvouprvkový seznam se s tímto termem neunifikuje.

Užitečnou procedurou pro práci se seznamy je prvek(X,S), která říká, jestli X je prvek seznamu S. Ve většině verzí tento predikát najdete jako member/2.

% prvek(?X, +S)
prvek(X,[X|_]).
prvek(X,[_|S]):-prvek(X,S).

Procedura se podívá, jestli je první prvek seznamu unifikovatelný s X, pokud ano, uspěje. Druhá řádka potom řeší situaci, kdy X není unifikovatelné s prvním prvkem seznamu, v takovém případě se procedura volá rekurzivně na zbytek seznamu.

Můžeme napsat i proceduru, která připojí prvek na začátek seznamu. Je to hodně jednoduché, stačí výsledný seznam unifikovat se seznamem, který má na prvním místě X a zbytek je S.

%pridejz(+X, +S, -Z). Pridava X na zacatek seznamu S a vysledek vraci v Z
pridejz(X, S, [X|S]).

Jak je to s přidáním prvku v seznamu na konec? Jak by taková procedura vypadala? A jaká bude její složitost? Je triviální přidat prvek na konec prázdného seznamu, stačí vytvořit jednoprvkový seznam s tímto prvkem. Pro přidání na konec delšího seznamu vezmeme jeho první prvek, zkopírujeme ho do výsledného seznamu a zavoláme proceduru rekurzivně.

% pridejk(+X, +S, -Z). Pridava X na konec seznamu S a vysledek vraci v Z.
pridejk(X,[],[X]).
pridejk(X,[Y|Ys],[Y|Z]):-pridejk(X,Ys,Z).

Všimněte si, že na začátek seznamu umíme přidávat v konstantním čase, kdežto na konec seznamu v čase lineárním v délce seznamu.

U obou předchozích predikátů jste si mohli všimnout znaků +/- v komentáři. Tyto znaky se používají pro rozlišení vstupních a výstupních proměnných – '+' označuje vstupní proměnnou, '-' výstupní. Při volání se potom očekává, že vstupní proměnné mají konkrétní hodnotu a výstupní jsou volné. Můžete se setkat i se znakem '?', ten znamená, že proměnná může být vstupní i výstupní. Toto je důležité při čtení a psaní dokumentace - pokud zavoláte predikát jinak, než je popsáno, může se zacyklit, nebo vracet nesprávné výsledky. (Celý tento systém notace je mnohem složitější, můžete se podívat do dokumentace, nám bude stačit zjednodušená verze popsaná výše.)

Zkusme si nyní napsat otočení seznamu pozpátku.

%otoc(+S,-Z). Otoci seznam S a vrati vysledek v Z
otoc([],[]). % otoceni prazdeho senzamu je prazdny seznam
otoc([X|Xs],Y):-otoc(Xs,Z),pridejk(X,Z,Y). % kdyz chces otocit [H|T] otoc T a pripoj za to H

Takhle napsané otočení seznamu je neefektivní, trvá kvadraticky dlouhou dobu ($n$-krát se volá pridejk na seznamy délky $1 \dots n$). Otočení ale i v Prologu lze napsat v lineárním čase, stačí využít jednoduchou techniku akumulátoru. Akumulátor je proměnná, do které si postupně ukládáme mezivýsledky a (typicky) v posledním kroku rekurze ji překopírujeme do výsledku.

S pomocí akumulátoru můžeme napsat proceduru otoc2/2, která seznam otočí v lineárním čase. Použije k tomu pomocnou proceduru otoc/3, která navíc používá akumulátor. Ten je na začátku prázdný.

%otoc2(+S,-Z). Otoci seznam S a vrati vysledek v Z.
otoc2(S,Z):-otoc2(S,[],Z).

%otoc2(+S, @A, -Z). Otoci seznam S a vrati vysledek v Z, pouziva A jako akumulator.
otoc2([], A, A). % Seznam uz je prazdny, prekopiruj akumulator 
otoc2([X|Xs], A, Z):-otoc2(Xs, [X|A], Z). 	% Prvni prvek z [X|Xs] pripoj na zacatek
                                            % akumulatoru a rekurzivne se zavolej.

Co se děje v tomto případě? Místo, abychom přidávali prvky na konec výsledného seznamu, přidáváme je na začátek akumulátoru. Když se vstupní seznam vyprázdní, zkopírujeme akumulátor do výsledku. Jak tedy probíhá výpočet pro dotaz otoc2([1,2,3,4], Z)? Napřed se zavolá pomocná procedura otoc2([1,2,3,4],[],Z) a potom postupně otoc2([2,3,4],[1],Z), otoc2([3,4],[2,1],Z), otoc2([4],[3,2,1],Z) a otoc2([], [4,3,2,1], Z). V tuto chvíli se zavolá první klauzule procedury otoc2/3 a Z se unifikuje s akumulátorem [4,3,2,1]. Potom už se program jen vrátí s unifikací Z = [4,3,2,1]. Všimněte si, že v tomto případě program běžel v době, která je lineární v délce seznamu, a že jsme toho dosáhli tím, že jsme přidávání na konec seznamu nahradili přidáváním na začátek akumulátoru, který jsme nakonec překopírovali.

Promyslete si další operace pro práci se seznamy: sudy, lichy (říkají, jestli má seznam sudou nebo lichou délku), prefix a sufix (vrací postupně prefixy, nebo sufixy seznamu) atd.

sudy([]).
sudy([_,_|S]):-sudy(S).

lichy([_|S]):-sudy(S).

prefix([],_).
prefix([X|Xs], [X|Ys]):-prefix(Xs,Ys).

sufix(X,Y):-otoc2(Y,Y1),prefix(X1,Y1),otoc2(X1,X).