Seznamy a append
appendC [], S, S ).
appendC [X|S1], S2,  [X|S3] ) :- appendC SI, S2, S3).
Napište následující predikáty pomocí append/3
Seznamy, řez
lastC X, S ) :- appendC _S1,  [X], S). append([3,2] , [6],  [3,2,6]). X=6, S=[3,2,6]
' prefix( SI, S2 ) :- appendC SI, _S3, S2). DÚ: suffix(Sl,S2)
■ memberC X, S ) :- appendC SI,  [X|S2], S ).
append([3,4,l],  [2,6],  [3,4,1,2,6]).      X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S)
1 % sublistC+S,+ASB)
sublistCS.ASB)  :- appendC AS, B, ASB ), appendC A, S, AS ).
POZOR na efektivitu, bez append lze často napsat efektivněji
Hana Rudová, Logické programování I, 17. března 2009 2 Seznamy, řez
Seznamy a delete
deleteC X,  [X|S], S ).
deleteC X,  [Y|S],  [Y|S1] ) :- deleteCX,S,S1).
Napište predikát delete(X, S, SI), který odstraní všechny výskyty X (pokud se X v S nevyskytuje, tak predikát uspěje).
deleteC _X,  [] ,  [] ) .
deleteCX,  [X|S], SI) :- !, deleteCX,S,SI) . deleteCX,  [Y|S],  [Y|S1] ) :- deleteCX,S,SI).
Optimalizace posledního volání
■ Last Call Optimization (LCO)
■ Implementační technika snižující nároky na paměť
■ Mnoho vnořených rekurzivních volání je náročné na paměť
■ Použití LCO umožňuje vnořenou rekurzi s konstantními pamětovými nároky
■ Typický příklad, kdy je možné použití LCO:
■ procedura musí mít pouze jedno rekurzivní volání: v posledním cíli poslední klauzule
■ cíle předcházející tomuto rekurzivnímu volání musí být deterministické
■ pC ...):- ... % žádné rekurzivní voláni v těle klauzule pC ...):- ... % žádné rekurzivní voláni v těle klauzule
pC-..) :- !, pC ■■■ )■ % řez zajišťuje determinismus
■ Tento typ rekurze lze převést na iteraci
Hana Rudová, Logické programování I, 17. března 2009 3 Seznamy, řez Hana Rudová, Logické programování I, 17. března 2009
LCO a akumulátor
Akumulátor a sum_l i st (S, Sum)
Reformulace rekurzivní procedury, aby umožnila LCO Výpočet délky seznamu length( Seznam, Délka ) lengthC [] , 0 ) .
lengthC [ H | T ], Délka ) :- lengthC T, DelkaO ), Délka is 1 + DelkaO. Upravená procedura, tak aby umožnila LCO:
% lengthC Seznam, ZapocitanaDelka, CelkovaDelka ):
% CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam''
lengthC Seznam, Délka ) :- lengthC Seznam, 0, Délka ). % pomocný predikát
lengthC [] , Délka, Délka ). % celková délka = započítaná délka
lengthC [ H I T ], A, Délka ) :- A0 is A + 1, lengthC T, A0, Délka ).
Přídavný argument se nazývá akumulátor
Hana Rudová, Logické programování I, 17. března 2009
Výpočet faktoriálu fact(N, F)
s akumulátorem:
factC N, F ) :- fact C N, 1, F ). factC 1, F,  F )  :- !.
factC N, A,  F )
N > 1,
Al i s N * A, Nl i s N - 1, factC Nl, Al,  F ).
Hana Rudová, Logické programování I, 17. března 2009
?- sum_listC [2,3,4], Sum ).
bez akumulátoru: sum_listC [] , 0 ) .
sum_list( [H|T], Sum ) :- sum_list( T, SumT ),
Sum is H + SumT.
s akumulátorem:
sum_list( S, Sum ) :-   sum_list( S, 0, Sum ).
sum_list( [], Sum, Sum ).
sum_list( [H|T], A, Sum )  :- Al is A + H,
sum_list( T, Al, Sum).
Hana Rudová, Logické programování I, 17. března 2009
r(X) r(X) r(X)
P(X) P(X)
P(X)
a(X) a(X)
b(X) b(X)
c(X) c(X)
d(X) d(X)
-writeCrl). -p(X),write(r2) . -write(r3).
-write(pl). -a(X),b(X), ! , c(X),d(X),write(p2) . -write(p3).
-write(al). -write(a2).
- X > 0, write(bl).
- X < 0, write(b2).
X mod 2 X mod 3
0, write(cl). 0, write(c2).
abs(X) < 10, write(dl). write(d2).
Prozkoumejte trasy výpočtu a navracet např. pomocí následujících dotazů (vždy : středníkem vyžádejte navracení):
(1) X=l,r(X). (3) X=0,r(X).
(2) X=3,r(X). (4) X= -6,r(X).
Hana Rudová, Logické programování I, 17. března 2009
řez v predikátu p/1 neovlivní alternativ predikátu r/1
dokud nebyl proveden řez, alternativ predikátu a/l se uplatňují, př. neúspěc b/l v dotazu (3)
při neúspěchu cíle za řezem se výpočí navrací až k volající proceduře r/1, viz (1
alternativy vzniklé po provedení řezu s zachovávají - další možnosti predikát c/1 viz (2) a (4)
Seznamy, řez
-write(rl) . -p(X),write(r2). -write(r3) .
-write(pl) . -a(X),b(X),!, c(X) ,d(X) ,wn'te(p2) . -write(p3) .
-write(al) . -write(a2).
- X > 0, write(bl).
- X < 0, write(b2).
X mod 2 X mod 3
write(cl) . write(c2).
abs(X) < 10, wn'te(dl). write(d2).
I ?- X=l,r(X). rl
X = 1 ? ; plr2
X = 1 ? ; alblr3 X = 1 ? ; no
I ?- X=0,r(X). rl
X = 0 ? ; plr2
X = 0 ? ; ala2p3r2 X = 0 ? ; r3
X = 0 ? ; no
I ?- X=3,r(X). rl
X = 3 ? ; plr2
X = 3 ? ;
alblc2dlp2r2
X = 3 ? ;
d2p2r2
X = 3 ? ;
r3
X = 3 ? ; no
X=
6, rC
I ? rl
X = -6 ? ; plr2
X = -6 ? ;
alb2cldlp2r2
X = -6 ? ;
d2p2r2
X = -6 ? ;
c2dlp2r2
X = -6 ? ;
d2p2r2
X = -6 ? ;
r3
X = -6 ? ; no
Rez: maximum
Je tato definice predikátu max/3 korektní?
max(X,Y,X):-X>=Y,!. max(X,Y,Y).
Není, následující dotaz uspěje: ?- max(2 ,1,1).
Uveďte dvě možnosti opravy, se zachováním použití řezu a bez.
max(X,Y,X):-X>=Y. max(X,Y,Y):-Y>X.
max(X,Y,Z):-X>=Y,!,Z=X. max(X,Y,Y).
Problém byl v definici, v první verzi se tvrdilo: X=Z a X>=Y => Z=X
správná definice je: X>=Y => Z=X
Při použití řezu je třeba striktně oddělit vstupní podmínky od výstupních unifikací a výpočtu.
Hana Rudová, Logické programování I, 17. března 2009
Hana Rudová, Logické programování I, 17. března 2009
Řez: member
Jakýje rozdíl mezi následujícími definicemi predikátů member/2. Ve kterých odpovědích se budou lišit? Vyzkoušejte např. pomocí member( X, [1,2,3] ).
memlCH,[H|_]).
memlCH,[_|T]) :- meml(H,T).
mem2(H, [H|_]) :- !. mem3(H, [K|_]) :-H==K.
mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T).
■ meml/2 vyhledá všechny výskyty, při porovnávání hledaného prvku s prvky seznamu může dojít k vázání proměnných (může sloužit ke generování všech prvků seznamu)
■ mem2/2 najde jenom první výskyt, taky váže proměnné
■ mem3/2 najde jenom první výskyt, proměnné neváže (hledá pouze identické prvky)
Seznamy: i intersection (A, B,C)
DÚ: Napište predikát pro výpočet průniku dvou seznamů. Nápověda: využijte predikát member/2
DÚ: Napište predikát pro výpočtu rozdílu dvou seznamů. Nápověda: využijte predikát member/2
Dokážete napsat variantu, která hledá jenom identické prvky
a přitom najde všechny výskyty?        mem4(H,[K|_]) :- H==K.   mem4(H,[K|T]) :- mem4(H,T).
Hana Rudová, Logické programování 1,17. března 2009 11 Seznamy, řez
Hana Rudová, Logické programování I, 17. března 2009
12
Seznamy, řez