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
.
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é:
=:=
(rovnost),=\=
(nerovnost),<
(menší),=<
(menší nebo rovno),>
(větší),>=
(větší nebo rovno),+
(sčítání),-
(odčítání),*
(násobení),/
(dělení),//
(celočíselné dělení),mod
arem
pro zbytek (liší se v záporných číslech),max/2
,min/2
pro minimum a maximum
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.