Prolog - seznamy a aritmetika

Minule jsme se věnovali seznamům, dnes v tom budeme ještě pokračovat, přidáme ale i aritmetiku.

Začněme jednoduchým příkladem na odebrání prvku ze seznamu.

% vymaz(+X, +X, -V) :- vymaze vyskyt prvku X ze seznamu S
%                      a vrati vysledny seznam jako V
vymaz(X,[X|Xs],Xs).
vymaz(X,[Z|Xs],[Z|Y]):-vymaz(X,Xs,Y).

Občas se hodí, aby procedura uspěla i v případě, že seznam daný prvek neobsahuje

% vymaz1(X,Odkud,CoZbude) :- totez co vymaz
%                            jen uspeje i kdyz X neni prvkem seznamu Odkud.
vymaz1(_,[],[]).
vymaz1(X,[X|T],T):-!.
vymaz1(X,[H|T],[H|T1]) :- vymaz1(X,T,T1).

Všimněte si, že pokud nenapíšete ! na konec první klauzule, Prolog vrací i seznamy, ve kterých jsou odebrané jiné výskyty než ten první a nakonec vrátí i původní seznam. ! je operátor řezu a říká Prologu, že zvolená rozhodnutí má považovat za konečná. Zakazuje mu backtrackovat v daném místě - ořezává všechny větve výpočtu kromě té první, proto ten název “operátor řezu”.

Zkusme si ještě napsat proceduru, která vrátí prostřední prvek ze seznamu. Jak ji napíšete, když nevíte dopředu, jak je seznam dlouhý?

prostredni(S,X):- prostredni(S,S,X). 
prostredni([_],[X|_],X). 
prostredni([_,_],[X|_],X). 
prostredni([_,_|T1],[_|T2],X):- prostredni(T1,T2,X).

Jak procedura funguje? Všimněte si, že v prvním seznamu se jde vždy po dvou a ve druhém po jednom kroku. Když se tedy první seznam vyprázdni (má max 2 prvky), na začátku toho druhého je přesně prostřední prvek.

Nakonec napišme ještě proceduru, která spočítá průnik dvou seznamů (ta je těžší a potřebujete na ni operátor řezu).

prunik([],_,[]).
prunik(_,[],[]).
prunik([X|Xs], Y, [X|Z]):-member(X,Y), prunik(Xs,Y,Z), !.
prunik([_|Xs], Y, Z):-prunik(Xs,Y,Z). 

Úkol: Zvládli byste napsat sjednocení? Zkuste si to.

Podívejme se nyní na aritmetiku v Prologu a na počítání. Počítáni v Prologu má svá úskalí a liší se od počítání v jazycích, na jaké jste zvyklí. Část těchto problémů plyne z toho, že v Prologu neexistuje operator přiřazení, = dělá unifikaci. Místo = se v aritmetických výpočtech v Prologu používá operátor is.

Rozdíl mezi = a is je vidět na následujících dotazech a odpovědích Prologu.

? X = 1+2
X = 1+2.

? X is 1+2
X = 3.

V Prologu také existují obvyklé relační operátory: rovná se se zapíše jako =:=, nerovná se jako =\=, menší než a větší než jako < a >, případně menší nebo rovno a větší nebo rovno jako =< a >=. Dávejte si pozor na to, že některé z těchto operátorů se zapisují jinak, než jste asi zvyklí.

U všech relačních operátorů je potřeba, aby obě strany výrazu už měly přiřazenu konkrétní hodnotu. U operátoru is stačí, když je přiřazena konkrétní hodnota termům na pravé straně (pokud je přiřazena konkrétní hodnota i termům na levé straně, operátor uspěje, pokud se obě hodnoty rovnají, jinak selže).

S pomocí aritmetiky můžeme napsat několik jednoduchých procedur. Nejjednodušší z nich je výpočet délky seznamu

% delka(+S,-L) :- do L dosadi delku seznamu S
delka([], 0).
delka([_|T], N):-delka(T,N1),N is N1 + 1.

Všimněte si, že výpočet N a rekurzivní volání nejde prohodit, protože jinak N1 ještě nemá přiřazenou žádnou hodnotu.

Můžeme také napsat jednoduchou proceduru pro výpočet druhé mocniny zadaného čísla.

% nadruhou(+X, -Y) :- prirazuje do Y druhou mocninu X
nadruhou(X,Y):-Y is X*X.

Zajímavější ale je napsat proceduru, která spočítá libovolnou mocninu libovolného čísla.

% mocnina(+Z,+M,-V) :- pocita Z^M a vysledek ulozi do V
mocnina(_,M,_):-M<0,fail.
mocnina(_,0,1).
mocnina(Z,1,Z).
mocnina(Z,2,V):-nadruhou(Z,V).
mocnina(Z,M,V):-M>2, M1 is M - 1, mocnina(Z,M1,V1), V is V1*Z.

Za použití aritmetiky se dají napsat i další procedury pro práci se seznamy, například nalezení minima v seznamu. Všimněte si tady i použití akumulátoru.

% minseznam(+S, -M) :- najde minimum v seznamu S a ulozi ho do M
minseznam([H|T], M) :- minseznam(T, H, M).
minseznam([], A, A).
minseznam([H|T], A, M):-A=<H,minseznam(T,A,M).
minseznam([H|T], A, M):-H<A,minseznam(T,H,M).

Můžeme napsat i přístup k N-tému prvku v seznamu. Dejte si ale pozor, přístup trvá lineárně dlouho.

% nty(+N, +S, +X) :- do X ulozi N-ty prvek seznamu S
nty(1, [H|_], H).
nty(N, [_|T], X):-N1 is N-1,nty(N1,T,X).