Václav Končický

Zatím jsme se naučili přidávat prvky na začátek a konec seznamu. Nyní je zkusme odstraňovat. Nejprve si pořídíme predikát smaz(?P, ?L, ?NL), který ze seznamu L, který obsahuje alespoň jeden prvek P, vytvoří seznam NL smazáním tohoto prvku.

smaz(P, [P|L], L).
smaz(P, [X|L], [X|NL]) :- smaz(P, L, NL).

Tento predikát je nederministický a existuje jeho standardní verze select/3.

?- smaz(a, [a, b, a, c, a], NL).
NL = [b, a, c, a] ;
NL = [a, b, c, a] ;
NL = [a, b, a, c] ;
false.

?- smaz(c, [a, b], NL).
false.

?- smaz(c, L, [a, b]).
L = [c, a, b] ;
L = [a, c, b] ;
L = [a, b, c] ;
false.

V případě, že L obsahuje P vícekrát, ve výsledném NL postupně bude chybět každý výskyt jednou, a to zleva doprava. Jestliže však L neobsahuje P, predikát selže. Predikát smaz lze taktéž použít i na vkládání P na libovolnou pozici v seznamu NL.

Cvičení: Naprogramujte predikát nahrad(?P, ?NP, ?L, ?NL) splnitelný, jestliže L obsahuje P a seznam NL má stejné prvky L, až jeden prvek NP nahrazující prvek P. Predikát tedy nahradí právě jeden výskyt prvku P za NP.

Co kdybychom ale chtěli mít predikát, který si poradí i se seznamy, které mazaný prvek neobsahují? Zkusme si takový predikát napsat. Ten bude vypadat stejně, akorát přidáme ještě druhý základní případ, když dojdeme na prázdný seznam.

smazMozna(_, [], []).
smazMozna(P, [P|L], L).
smazMozna(P, [X|L], [X|NL]) :- smazMozna(P, L, NL).

Cvičení: Naprogramujte predikat smazVice(?P, ?L, ?NL) splnitelný, jestliže NL je seznam vzniklý z L vypuštěním libovolné podmnožiny výskytu prvků P.

Zkusme na tento predikát spustit dotazy.

?- smazMozna(c, [a, b], NL).
NL = [a, b].

?- smazMozna(b, [a, b], NL).
NL = [a] ;
NL = [a, b].

Jak vidíme, smazMozna si nyní poradí i s takovými L, jenž neobsahují P. Na druhou stranu ale nyní budeme vždy dostávat i řešení, kde L = NL, přestože P se v L nachází. Zde narážíme na limity našeho deklarativního přístupu. Z jeho pohledu je takové chování správně. Nadeklarovali jsme přeci, že nesmazat prvek je přípustné.

Co kdybychom ale chtěli, aby tento případ nenastal?

Řezy

Prolog podporuje konstrukce, které mění deklarativní význam predikátů. Jeden z nich je řez, reprezentován predikátem !/0. Jestliže Prolog při vyhodnocování predikátu narazí na řez, zafixuje všechny předchozí nedeterministické volby a pokračuje dál. Jinými slovy jakmile Prolog přejde přes řez, nemůže se přes něj vrátit backtrackingem.

Řez se chová "nedeklarativně"; doteď (skoro) nezáleželo na pořadí predikátů, měnila se nám pouze efektivita. S řezem se ale při prohození pořadí pravidel začne i měnit význam predikátu. Ukažme si to na malém příkladu.

plati(a).
plati(b) :- !.
plati(c).

Jak se budou chovat dotazy pro tento predikát?

?- plati(c).
true.

?- X = c, plati(X).
true.

?- plati(X), X = c.
false.

?- plati(X).
X = a ;
X = b.

Na první dva dotazy Prolog odpoví pravdou, jelikož varianta plati(b) selže před tím, než se vyhodnocování dostane k řezu. Naopak, u zbylých dvou dotazů se Prologu podaří splnit druhou variantu a Prolog projde přes řez. V tuto chvíli už Prolog nesmí vyzkoušet třetí možnost, takže třetí dotaz selže a čtvrtý dotaz nevrátí X = c.

Řez ale můžeme použít k tomu, abychom zvýšili efektivitu vyhodnocení predikátů, většinou za cenu jeho obousměrnosti. 

% max(+X, +Y, -M) :- M = max(X, Y).
max(X, Y, X) :- geq(X, Y), !.
max(X, Y, Y) :- lt(X, Y).

% max2(+X, +Y, -M) :- M = max(X, Y).
max2(X, Y, Z) :- geq(X, Y), !, Z = X.
max2(X, Y, Y).

Normálně by u dotazu na max Prolog vyhodnocoval obě varianty, a tedy by vyhodnotil geq i lt. Díky řezu Prolog pro X ≥ Y už nebude zkoušet, zda X < Y (které selže), čímž se vyhne nutnosti vyhodnotit lt a program bude rychlejší. Pokud se ale dotážeme na max(s(0), Y, s(0)), dostaneme pouze jedno řešení, přestože existují dvě.

Všimněme si však, že po odstranění řezu z predikátu max/3 nezměníme odpovědi, tedy alespoň pro námi určený druh parametrů. Naopak, řez u predikátu max2/3 je nepostrádatelný, bez něj začneme dostávat nesprávná řešení.

Řezy, které mění pouze efektivitu vyhodnocování pro námi určený kontext, se nazývají zelené. Řezy měnící množinu řešení nazvěme červené. Červeným řezům je lepší se vyhýbat, pokud to jde.

Procedurální podmínka

U predikátu max2 jsme použili ekvivalent procedurální podmínky. Její nevýhoda je však, že se podmínka vyhodnotí kvůli řezu kladně nejvýše jednou. Tudíž nelze mít v podmínce nedeterminismus. Tento typ podmínky má dokonce syntaktickou zkratku.

% Podmínka přes řez
predikat(X) :- if(X), !, then(X).
predikat(X) :- else(X).
% Stejná podmínka užitím speciální syntaxe
predikat(X) :- if(X) -> then(X) ; else(X).

Negace

Další nedeklarativní predikát, který máme v Prologu k dispozici, je negace \+. Negace je splněna právě, když negovaný predikát není splnitelný -- jeho vyhodnocení vrátí pouze false.

Negaci si můžeme sami naprogramovat pomocí řezu, jde o jednoduchou procedurální podmínku:

negace(Predikat) :- Predikat, !, fail.
negace(Predikat).
% Alternativně přes syntaxi podmínky
negace(Predikat) :- Predikat -> fail ; true.

Tato negace není pravá negace ve smyslu logiky, není totiž úplná. Pokud se predikát podaří jakkoliv splnit, vrátí false. Jinak vrátí true. Jakmile ale je negace splněna, Prolog už nemá důvod zkoušet v negaci další varianty, může tedy přeskočit některá řešení.

Speciální případ negace, který se velmi často užívá, je neunifikovatelnost X \= Y, která je ekvivalentní \+ X = Y.

Vraťme se k odstraňování prvků se seznamu. Nyní, umíme používat (červený) řez a negaci, můžeme napsat predikát mazající vždy pouze první výskyt prvku. 

smazPrvni(P, [P|L], L) :- !.
smazPrvni(P, [X|L], [X|NL]) :- smazPrvni(P, L, NL).

Samozřejmě, tento predikát můžeme rovněž napsat bez přímého užití řezu pomocí neunifikovatelnosti:

smazPrvni2(P, [P|L], L).
smazPrvni2(P, [X|L], [X|NL]) :- P \= X, smazPrvni2(P, L, NL).

Vyzkoušejme, jak se tyto predikáty chovají.

?- smazPrvni(a, [a, b, a, c, a], NL).
NL = [b, a, c, a].

?- smazPrvni2(a, [a, b, a, c, a], NL).
NL = [b, a, c, a] ;
false.

?- smazPrvni(a, [a, b, c], NL),
|    smazPrvni(a, [b, a, c], NL),
|    smazPrvni(a, [b, c, a], NL).
NL = [b, c].

?- smazPrvni(a, L, [b, c]).
L = [a, b, c].

?- smazPrvni2(a, L, [b, c]).
L = [a, b, c] ;
L = [b, a, c] ;
L = [b, c, a].

?- smazPrvni(P, [a, b, c], NL).
P = a,
NL = [b, c].

?- smazPrvni(P, [a, b, c], [a, c]).
P = b.

?- smazPrvni2(P, [a, b, c], [a, c]).
false.

Vidíme, že tyto predikáty nyní opravdu odstraňují jen první P v L. Bohužel ale ztracíme obousměrnost predikátů. Zatímco jsme našli tři možnosti L pro P = a a NL = [b, c], zavoláním predikátu s takto dosazenými proměnnými získáme jen jednu možnost. Stejně tak, pro P volné dostaneme jen možnost P = a. Tudíž, máme pouze predikát smazPrvni(+P, +L, -NL).

Predikát implementovaný přes negaci si taky nevede nijak dobře. Pro volné P nám predikát nenajde žádné řešení. Podmínka X \= P selže, protože v daný čas vyhodnocení lze P na X unifikovat. Narozdíl od řezu jsme však pro volné L dostali více řešení.

Cvičení: Naprogramujte predikát smazMoznaPrvni(+P, +L, -NL) splnitelný, jestliže NL vznikne z L odstraněním prvního výskytu P. Pokud se P v L nevyskytuje, NL = L.

Cvičení: Naprogramujte predikát smazVsechny(+P, +L, -NL) splnitelný, jestliže NL vznikne z L vypuštěním všech výskytů P.

Zdroj s predikáty

Práce s čísly v Prologu

Dříve jsme si zkusili napsat Robinsonovu aritmetiku na přirozených číslech. Prolog však má k dispozici vlastní aritmetiku. Tato aritmetika nefunguje zdaleka tak dobře, je velmi omezená. Neumí například fungovat oboustranně.

Základní operátor pro aritmetiku je is. Ten provede to, že vyhodnotí pravou stranu a její výsledek zunifikuje s levou stranou. K tomuto účelu nejde použít obyčejnou unifikaci, protože ta nevyhodnocuje operátory.

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

?- X is 1 + 2.
X = 3.

?- 3 is 1 + X.
ERROR: Arguments are not sufficiently instantiated

Pokud v době vyhodnocení operátoru is není pravá strana dosazená, Prolog si bude stěžovat, nevrátí ani žádnou odpověď.

Prolog nabízí relační a funkční predikáty a operátory pro práci s čísly, jejichž použití vyžaduje, aby obě strany byly dosazené:

Další aritmetické funkce lze najít na manuálu SWI-Prologu. Aritmetická rovnost a unifikace se liší v tom, že rovnost opravdu kontroluje číselnou rovnost:

?- 1 + 4 = 2 + 3.
false.

?- 1 + 4 =:= 2 + 3.
true.

?- 1 + X =:= 2 + 3.
ERROR: Arguments are not sufficiently instantiated

?- X is 2 + 3 - 1.
X = 4.

S aritmetikou nyní zvládneme napsat predikát zjišťující délku seznamu. Prázdný seznam má jistě délku 0 a přidání prvku na začátek seznamu jej prodlouží. Protože však musíme při vyhodnocování aritmetiky mít již konkrétní hodnotu k dispozici, musíme přičíst délku až po návratu z rekurze.

% delka(?L, ?N) :- Seznam L má N prvků.
delka([], 0).
delka([_|L], N) :- delka(L, N1), N is N1 + 1.

Nám by se však líbílo mít predikát, který se rekurzí až na konci vyhodnocování. Takovou rekurzi nazýváme koncovou. Její výhoda je, že pokud nemáme žádný nedeterminismus a rekurzíme se koncově, Prolog může tuto rekurzi zoptimalizovat na iteraci, takže nepotřebuje zásobník. Predikát delka naprogramovaný koncovou rekurzí získáme chytrým použitím akumulátoru.

delka_acc(L, N) :- delka_acc(L, 0, N).
% delka_acc(?L, @A, ?N) :- L má délku N, zkrácením seznamu zvýší A o 1.
delka_acc([], N, N).
delka_acc([_|L], A, N) :- A1 is A + 1, delka_acc(L, A1, N).

Obě verze predikátu delka jsou ekvivalentní v množině řešení, akumlátorová verze je efektivnější. Vyzkoušejme nyní naše predikáty, jak se budou chovat, když zvolíme různé proměnné jako volné.

?- delka([a, b, c], N).
N = 3.

?- delka_acc([a, b, c], N).
N = 3.

?- delka(L, N).
L = [],
N = 0 ;
L = [_2146],
N = 1 .

?- delka(L, 3).
L = [_2116, _2122, _2128] ;
% Zacyklení...

Všimněme si, že predikát stále funguje i pro volné N. V prvním případě totiž díky základnímu případu vždy budeme mít N1 dosazené, v druhém příkladě inicializujeme A na 0.

Pro volné L a vázané N se však po vracení seznamu správné délky predikát zacyklí, jelikož necháme základní příklad selhat a N1 + 1 pak bude vždy větší, než N.

Cvičení: Naprogramujte predikat seznam_delky(+N, -L) vracející seznam L volných proměnných délky N. Zkuste to bez řezu.

Standardní knihovna Prologu obsahuje predikát length/2, který umí všechny případy volnosti proměnných.

Cvičení: Naprogramujte predikát pozice(+L, ?N, ?P) splnitelný, jestliže se v seznamu L na N-té pozici nachází prvek P. Hlava L je na pozici 0.

Predikát pozice/3 lze najít v standardní knihovně Prologu jako nth0/3. Navíc, existuje i predikát nth1/3, který počítá od 1.

Cvičení: Naprogramujte predikát nezaporna(+L) splnitelný, jestliže všechny prvky L jsou nezáporná čísla.

Cvičení: Naprogramujte predikát max_seznam(+L, -M) splnitelný, jestliže L obsahuje pouze čísla a M je jejich maximum.