Seznamy, řez
Reprezentace seznamu
Seznam: [a, b, c], prázdný seznam []
Hlava (libovolný objekt), tělo (seznam): . (Hlava, Telo)
3 všechny strukturované objekty stromy - i seznamy
3 funktordva argumenty
M .(a,  .(b,  .(c, []))) = [a, b, c]
3 notace: [ Hlava | Telo ] = [a | Tel o]
Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ]
M Lze psát i: [a,b|Telo]
M před "|" je libovolný počet prvků seznamu , za "|" je seznam zbývajících prvků 3 [a.b.c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] 3 pozor: [ [a,b]  I  [c] ] ^ [ a,b |  [c] ]
M Seznam jako neúplná datová struktura: [a,b,c|T]
3 Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S]
Hana Rudová, Logické programování I, 25. března 201 3 2 Seznamy, řez
Cvičení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).     % (2)
:- append([l,2],[3,4],A).
I (2)
I A=[1|B] :- append([2],[3,4],B).
I (2)
I B=[2|C]   => A=[1,2|C] :- append([],[3,4],C)■ I (D
I C=[3,4]    => A=[l,2,3,4], yes
Hana Rudová, Logické programování I, 25. března 201 3
3
Seznamy, řez
Cvičení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).     % (2)
:- append([l,2],[3,4],A).
I (2)
I A=[1|B] :- append([2],[3,4],B).
I (2)
| B=[2|C]    => A=[1,2|C] :- append([],[3,4],C)■ I (D
| C=[3,4]   => A=[l,2,3,4], yes
Předchůdce a následník prvku X v seznamu S
hledej(S,X,Pred,Po) :- append( _S1,  [ Pred,X,Po I _S2 ], S)
Hana Rudová, Logické programování I, 25. března 201 3
3
Seznamy, řez
Seznamy a append
append( [] , S, S ) .
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).
Napište následující predikáty pomocí append/3:
M prefixC SI, S2 ) :-DÚ: suffix(Sl,S2)
Hana Rudová, Logické programování I, 25. března 201 3
4
Seznamy, řez
Seznamy a append
appendC [], S, S ).
appendC [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).
Napište následující predikáty pomocí append/3:
M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2)
Hana Rudová, Logické programování I, 25. března 201 3
4
Seznamy, řez
Seznamy a append
append( [], S, S ) .
appendC [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).
Napište následující predikáty pomocí append/3:
M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2)
last( X, S ) :-
append([3,2],  [6],  [3,2,6]). X=6, S=[3,2,6]
Hana Rudová, Logické programování I, 25. března 201 3
4
Seznamy, řez
Seznamy a append
append( [] , S, S ) .
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).
Napište následující predikáty pomocí append/3:
M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2)
M last( X, S ) :- append( _S1,  [X], S).
append([3,2],  [6],  [3,2,6]). X=6, S=[3,2,6]
Hana Rudová, Logické programování I, 25. března 201 3
4
Seznamy, řez
Seznamy a append
append( [] , S, S ) .
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).
Napište následující predikáty pomocí append/3:
M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2)
M last( X, S ) :- append( _S1,  [X], S).
append([3,2],  [6],  [3,2,6]). X=6, S=[3,2,6]
M memberC X, 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)
Hana Rudová, Logické programování I, 25. března 201 3
4
Seznamy, řez
Seznamy a append
append( [] , S, S ) .
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).
Napište následující predikáty pomocí append/3:
M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2)
M last( X, S ) :- append( _S1,  [X], S).
append([3,2],  [6],  [3,2,6]). X=6, S=[3,2,6]
M member( X, S ) :- append( 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)
Hana Rudová, Logické programování I, 25. března 201 3
4
Seznamy, řez
Seznamy a append
append( [] , S, S ) .
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).
Napište následující predikáty pomocí append/3:
M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2)
M last( X, S ) :- append( _S1,  [X], S).
append([3,2],  [6],  [3,2,6]). X=6, S=[3,2,6]
M member( X, S ) :- append( 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)
% sublist(+S,+ASB) sublist(S,ASB) :-
Hana Rudová, Logické programování I, 25. března 201 3
4
Seznamy, řez
Seznamy a append
append( [] , S, S ) .
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).
Napište následující predikáty pomocí append/3:
<M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2)
M last( X, S ) :- append( _S1,  [X], S).
append([3,2],  [6],  [3,2,6]). X=6, S=[3,2,6]
memberC X, S ) :- append( 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)
% sublist(+S,+ASB)
sublist(S,ASB)  :- append( AS, B, ASB ),
append( A, S, AS ).
POZOR na efektivitu, bez append lze často napsat efektivněji
Hana Rudová, Logické programování I, 25. března 2013 4 Seznamy, řez
Optimalizace posledního volání
M Last Call Optimization (LCO)
Implementační technika snižující nároky na paměť
M Mnoho vnořených rekurzivních volání je náročné na paměť
M 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:
M procedura musí mít pouze jedno rekurzivní volání: v posledním cíli poslední klauzule
M cíle předcházející tomuto rekurzivnímu volání musí být deterministické
M p( ...):-.. . % žádné rekurzivní voláni v těle klauzule
p( ...):- ... % žádné rekurzivní voláni v těle klauzule
p(...) :- !, p( ... ). % řez zajišťuje determinismus
M Tento typ rekurze lze převést na iteraci
Hana Rudová, Logické programování I, 25. března 201 3
5
Seznamy, řez
LCO a akumulátor
M Reformulace rekurzivní procedury, aby umožnila LCO M Výpočet délky seznamu length( Seznam, Délka ) lengthC [] , 0 ).
length( [ H | T ], Délka ) :- length( T, Del kaO ), Délka is 1 + DelkaO.
Hana Rudová, Logické programování I, 25. března 201 3 6 Seznamy, řez
LCO a akumulátor
M Reformulace rekurzivní procedury, aby umožnila LCO M Výpočet délky seznamu length( Seznam, Délka ) lengthC [] , 0 ).
length( [ H | T ], Délka ) :- length( T, Del kaO ), Délka is 1 + DelkaO.
M Upravená procedura, tak aby umožnila LCO:
% length( Seznam, ZapocitanaDelka, CelkovaDelka ):
% CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam''
Hana Rudová, Logické programování I, 25. března 201 3
6
Seznamy, řez
LCO a akumulátor
M Reformulace rekurzivní procedury, aby umožnila LCO M Výpočet délky seznamu length( Seznam, Délka ) lengthC [] , 0 ).
length( [ H | T ], Délka ) :- length( T, Del kaO ), Délka is 1 + DelkaO.
M Upravená procedura, tak aby umožnila LCO:
% length( Seznam, ZapocitanaDelka, CelkovaDelka ):
length( Seznam, Délka ) :- length( Seznam, 0, Délka ). % pomocný predikát
length ( [H | T ] , A, Délka ) :- AO is A + 1, length ( T, AO, Del ka ).
M Přídavný argument se nazývá akumulátor
CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam
length( [] , Délka, Délka ).
Hana Rudová, Logické programování I, 25. března 201 3
6
Seznamy, řez
Akumulátor a sum_l i st(S, Sum)
?- sum_list( [2,3,4], Sum ). s akumulátorem:
sum_list( S, Sum ) :-   sum_list( S, 0, Sum ).
sum_list( [], Sum, Sum ).
sum_list( [H|T], A, Sum )  :- Al i s A + H,
sum_list( T, Al, Sum).
Hana Rudová, Logické programování I, 25. března 201 3
7
Seznamy, řez
Výpočet faktoriálu f act(N, F)
s akumulátorem:
Hana Rudová, Logické programování I, 25. března 201 3
8
Seznamy, řez
Výpočet faktoriálu fact (N, F)
s akumulátorem:
fact( N, F )  :- fact (N, 1, F ).
fact( 1, F, F )  :- ! . fact( N, A, F )  :-   N > 1,
Al is N * A,
Nl is N - 1,
fact( Nl, Al, F ).
Hana Rudová, Logické programování I, 25. března 201 3
8
Seznamy, řez
r(X):-wri te(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pl). p(X):-a(X),b(X),!,
c(X) ,d(X) ,write(p2) . p(X) : -wri te(p3) .
a(X):-write(al). a(X):-write(a2).
b(X):- X > O, write(bl). b(X):- X < O, write(b2).
c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2)
d(X):- abs(X) < 10, write(dl). d(X):- write(d2).
Prozkoumejte trasy výpočtu a navracení např. pomocí následujících dotazů (vždy si 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)
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
■wri te(rl) . ■p(X),write(r2). ■wri te(r3) .
■wri te(pl) . ■a(X),b(X), ! , c(X),d(X),write(p2). ■wri te(p3) .
■wri te(al) . ■wri te(a2) .
■ X > O, write(bl) .
■ X < O, write(b2).
■ X mod 2 =:= 0, write(cl)
■ X mod 3 =:= 0, write(c2)
■ abs(X) < 10, write(dl).
■ wri te(d2).
Prozkoumejte trasy výpočtu a navracení např. pomocí následujících dotazů (vždy si 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)
řez v predikátu p/1 neovlivní alternativy predikátu r/1
dokud nebyl proveden řez, alternativy predikátu a/l se uplatňují, př. neúspěch b/l v dotazu (3)
při neúspěchu cíle za řezem se výpočet navrací až k volající proceduře r/1, viz (1)
alternativy vzniklé po provedení řezu se zachovávají - další možnosti predikátu c/1 viz (2) a (4)
Hana Rudová, Logické programování I, 25. března 201 3
Seznamy, řez
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pl). p(X):-a(X),b(X),!,
c(X) ,d(X) ,write(p2) . p(X):-write(p3).
a(X):-write(al). a(X):-write(a2).
b(X):- X > 0, write(bl). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(cl). c(X):- X mod 3 =:= 0, write(c2).
d(X):- abs(X) < 10, write(dl). d(X):- write(d2).
r(X):-wri te(rl). r(X):-p(X),write(r2). r(X):-wri te(r3).
p(X):-write(pl). p(X):-a(X),b(X),!,
c(X) ,d(X) ,write(p2) . p(X):-write(p3).
a(X):-write(al). a(X):-write(a2).
b(X):- X > 0, write(bl). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2)
d(X):- abs(X) < 10, write(dl). d(X):- write(d2).
I ?- X=l,r(X). r(X):-write(rl). rl
r(X):-p(X),write(r2) . X = 1 ? ;
r(X):-wri te(r3).
p(X):-write(pl). p(X):-a(X),b(X),!,
c(X) ,d(X) ,write(p2) . p(X):-write(p3).
a(X):-write(al). a(X):-write(a2).
b(X):- X > 0, write(bl). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(cl). c(X):- X mod 3 =:= 0, write(c2).
d(X):- abs(X) < 10, write(dl). d(X):- write(d2).
r(X):-wri te(rl). r(X):-p(X),write(r2). r(X):-wri te(r3).
p(X):-write(pl). p(X):-a(X),b(X),!,
c(X) ,d(X) ,write(p2) . p(X):-write(p3).
a(X):-write(al). a(X):-write(a2).
b(X):- X > 0, write(bl). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(cl). c(X):- X mod 3 =:= 0, write(c2).
d(X):- abs(X) < 10, write(dl). d(X):- write(d2).
I ?- X=l,r(X). rl
X = 1 ? ; plr2
X = 1 ? ;
I ?- X=l,r(X) r(X):-write(rl). rl
r(X):-p(X),write(r2) . X = 1 ? ;
r(X):-write(r3). plr2
p(X):-write(pl). p(X):-a(X),b(X),!,
c(X) ,d(X) ,write(p2) . p(X):-write(p3).
a(X):-write(al). a(X):-write(a2).
b(X):- X > 0, write(bl). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2)
d(X):- abs(X) < 10, write(dl). d(X):- write(d2).
X = 1 ? ; alblr3 X = 1 ? ;
I ?- X=l,r(X) r(X):-write(rl). rl
r(X):-p(X),write(r2) . X = 1 ? ;
r(X):-write(r3). plr2
p(X):-write(pl). p(X):-a(X),b(X),!,
c(X) ,d(X) ,write(p2) . p(X):-write(p3).
a(X):-write(al). a(X):-write(a2).
b(X):- X > 0, write(bl). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2)
d(X):- abs(X) < 10, write(dl). d(X):- write(d2).
X = 1 ? ; alblr3 X = 1 ? ; no
I ?- X=l,r(X) r(X):-write(rl). rl
r(X):-p(X),write(r2) . X = 1 ? ;
r(X):-write(r3). plr2
p(X):-write(pl). p(X):-a(X),b(X),!,
c(X) ,d(X) ,write(p2) p(X):-write(p3).
X = 1 ? ; alblr3 X = 1 ? ; no
a(X):-write(al). , ?_ x=0>r(x)
a(X):-write(a2).
b(X):- X > 0, write(bl). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(cl). c(X):- X mod 3 =:= 0, write(c2).
d(X):- abs(X) < 10, write(dl). d(X):- write(d2).
I ?- X=l,r(X) r(X):-write(rl). rl
r(X):-p(X),write(r2) . X = 1 ? ;
r(X):-write(r3). plr2
p(X):-write(pl). p(X):-a(X),b(X),!,
c(X) ,d(X) ,write(p2) p(X):-write(p3).
X = 1 ? ; alblr3 X = 1 ? ; no
a(X):-write(al). , ?_ x=0>r(x)
a(X):-write(a2). ^
b(X):- X > 0, write(bl). X = 0 ? ;
b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(cl). c(X):- X mod 3 =:= 0, write(c2).
d(X):- abs(X) < 10, write(dl). d(X):- write(d2).
I ?- X=l,r(X).
r(X)	:-wri te(rl).	rl
r(X)	:-p(X), wri te(r2).	X = 1 ? ;
r(X)	:-write(r3).	plr2
P(X)	:-write(pl).	X = 1 ? ;
P(X)	:-a(X),b(X),!,	alblr3
	c(X),d(X),write(p2).	X = 1 ? ;
P(X)	:-write(p3).	no
a(X)	:-write(al).	1 ?- X=0,r(X).
a(X)	:-write(a2).	rl
b(X)	: - X > 0, write(bl) .	X = 0 ? ;
b(X)	:- X < 0, write(b2).	plr2
		X = 0 ? ;
c(X)	:- X mod 2 =:= 0, write(cl).	
c(X)	:- X mod 3 =:= 0, write(c2).	
d(X)	:- abs(X) < 10, write(dl).	
d(X)	: - wri te(d2) .	
I ?- X=l,r(X).
r(X)	:-wri te(rl).	rl
r(X)	:-p(X), wri te(r2).	X = 1 ? ;
r(X)	:-write(r3).	plr2
P(X)	:-write(pl).	X = 1 ? ;
P(X)	:-a(X),b(X),!,	alblr3
	c(X),d(X),write(p2).	X = 1 ? ;
P(X)	:-write(p3).	no
a(X)	:-write(al).	1 ?- X=0,r(X).
a(X)	:-write(a2).	rl
b(X)	: - X > 0, write(bl) .	X = 0 ? ;
b(X)	:- X < 0, write(b2) .	plr2
		X = 0 ? ;
c(X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2
c(X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;
d(X)	:- abs(X) < 10, write(dl).	
d(X)	: - wri te(d2) .	
I ?- X=l,r(X).
r(X)	:-wri te(rl).	rl
r(X)	:-p(X), wri te(r2).	X = 1 ? ;
r(X)	:-write(r3).	plr2
P(X)	:-write(pl).	X = 1 ? ;
P(X)	:-a(X),b(X),!,	alblr3
	c(X),d(X),write(p2).	X = 1 ? ;
P(X)	:-write(p3).	no
a(X)	:-write(al).	1 ?- X=0,r(X).
a(X)	:-write(a2).	rl
b(X)	: - X > 0, write(bl) .	X = 0 ? ;
b(X)	:- X < 0, write(b2).	plr2
		X = 0 ? ;
c(X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2
c(X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;
d(X)	:- abs(X) < 10, write(dl).	r3
d(X)	: - wri te(d2) .	X = 0 ? ;
I ?- X=l,r(X).
r(X)	:-wri te(rl).	rl
r(X)	:-p(X), wri te(r2).	X = 1 ? ;
r(X)	:-write(r3).	plr2
P(X)	:-write(pl).	X = 1 ? ;
P(X)	:-a(X),b(X),!,	alblr3
	c(X),d(X),write(p2).	X = 1 ? ;
P(X)	:-write(p3).	no
a(X)	:-write(al).	1 ?- X=0,r(X).
a(X)	:-write(a2).	rl
b(X)	: - X > 0, write(bl) .	X = 0 ? ;
b(X)	:- X < 0, write(b2).	plr2
		X = 0 ? ;
c(X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2
c(X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;
d(X)	:- abs(X) < 10, write(dl).	r3
d(X)	: - wri te(d2) .	X = 0 ? ;
		no
?- X=l,r(X)
r (X)	:-wri te(rl).	rl
r (X)	:-p(X), wri te(r2).	X = 1 ? ;
r (X)	:-write(r3).	plr2
P (X)	:-write(pl).	X = 1 ? ;
P (X)	:-a(X),b(X),!,	alblr3
	c(X),d(X),write(p2).	X = 1 ? ;
P (X)	:-write(p3).	no
a (X)	:-write(al).	1 ?- X=0,r(X).
a (X)	:-write(a2).	rl
b (X)	: - X > 0, write(bl) .	X = 0 ? ;
b (X)	:- X < 0, write(b2).	plr2
		X = 0 ? ;
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;
d (X)	:- abs(X) < 10, write(dl).	r3
d (X)	: - wri te(d2) .	X = 0 ? ;
?- X=3,r(X)
no
?- X=l,r(X)
r (X)	:-wri te(rl).	rl
r (X)	:-p(X), wri te(r2).	X = 1 ? ;
r (X)	:-write(r3).	plr2
P (X)	:-write(pl).	X = 1 ? ;
P (X)	:-a(X),b(X),!,	alblr3
	c(X),d(X),write(p2).	X = 1 ? ;
P (X)	:-write(p3).	no
a (X)	:-write(al).	1 ?- X=0,r(X).
a (X)	:-write(a2).	rl
b (X)	: - X > 0, write(bl) .	X = 0 ? ;
b (X)	:- X < 0, write(b2).	plr2
		X = 0 ? ;
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;
d (X)	:- abs(X) < 10, write(dl).	r3
d (X)	: - wri te(d2) .	X = 0 ? ;
		no
I ?- X=3,r(X) rl
X = 3 ? ;
?- X=l,r(X)
r (X)	:-wri te(rl).	rl
r (X)	:-p(X), wri te(r2).	X = 1 ? ;
r (X)	:-write(r3).	plr2
P (X)	:-write(pl).	X = 1 ? ;
P (X)	:-a(X),b(X),!,	alblr3
	c(X),d(X),write(p2).	X = 1 ? ;
P (X)	:-write(p3).	no
a (X)	:-write(al).	1 ?- X=0,r(X).
a (X)	:-write(a2).	rl
b (X)	: - X > 0, write(bl) .	X = 0 ? ;
b (X)	:- X < 0, write(b2) .	plr2
		X = 0 ? ;
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;
d (X)	:- abs(X) < 10, write(dl).	r3
d (X)	: - wri te(d2) .	X = 0 ? ;
I ?- X=3,r(X) rl
X = 3 ? ; plr2
X = 3 ? ;
no
?- X=l,r(X)
r (X)	:-wri te(rl).	rl
r (X)	:-p(X), wri te(r2).	X = 1 ? ;
r (X)	:-write(r3).	plr2
P (X)	:-write(pl).	X = 1 ? ;
P (X)	:-a(X),b(X),!,	alblr3
	c(X),d(X),write(p2).	X = 1 ? ;
P (X)	:-write(p3).	no
a (X)	:-write(al).	1 ?- X=0,r(X).
a (X)	:-write(a2).	rl
b (X)	: - X > 0, write(bl) .	X = 0 ? ;
b (X)	:- X < 0, write(b2) .	plr2
		X = 0 ? ;
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;
d (X)	:- abs(X) < 10, write(dl).	r3
d (X)	: - wri te(d2) .	X = 0 ? ;
		no
I ?- X=3,r(X) rl
X = 3 ? ; plr2
X = 3 ? ; alblc2dlp2r2 X = 3 ? ;
?- X=l,r(X)
r (X)	:-wri te(rl).	rl
r (X)	:-p(X), wri te(r2).	X = 1 ? ;
r (X)	:-write(r3).	plr2
P (X)	:-write(pl).	X = 1 ? ;
P (X)	:-a(X),b(X),!,	alblr3
	c(X),d(X),write(p2).	X = 1 ? ;
P (X)	:-write(p3).	no
a (X)	:-write(al).	1 ?- X=0,r(X).
a (X)	:-write(a2).	rl
b (X)	: - X > 0, write(bl) .	X = 0 ? ;
b (X)	:- X < 0, write(b2).	plr2
		X = 0 ? ;
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;
d (X)	:- abs(X) < 10, write(dl).	r3
d (X)	: - wri te(d2) .	X = 0 ? ;
		no
I ?- X=3,r(X) rl
X = 3 ? ; plr2
X = 3 ? ; alblc2dlp2r2 X = 3 ? ; d2p2r2 X = 3 ? ;
		1 ?- X=l,r(X).	
r (X)	:-wri te(rl).	rl	
r (X)	:-p(X), wri te(r2).	X = 1 ? ;	
r (X)	:-write(r3).	plr2	
			1 ?- X=3,r(X
P (X)	:-write(pl).	X = 1 ? ;	rl
P (X)	:-a(X),b(X),!,	alblr3	X = 3 ? ;
	c(X),d(X),write(p2).	X = 1 ? ;	7 plr2
P (X)	:-write(p3).	no	X = 3 ? ;
a (X)	:-write(al).	1 ?- X=0,r(X).	alblc2dlp2r2
a (X)	:-write(a2).	rl	X = 3 ? ;
			d2p2r2
b (X)	: - X > 0, write(bl) .	X = 0 ? ;	X = 3 ? ;
b (X)	:- X < 0, write(b2).	plr2	r3
		X = 0 ? ;	
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2	X = 3 ? ;
			
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;	
			
d (X)	:- abs(X) < 10, write(dl).	r3	
d (X)	: - wri te(d2) .	X = 0 ? ;	
		no	
		1 ?- X=l,r(X).	
r (X)	:-wri te(rl).	rl	
r (X)	:-p(X), wri te(r2).	X = 1 ? ;	
r (X)	:-write(r3).	plr2	
			1 ?- X=3,r(X
P (X)	:-write(pl).	X = 1 ? ;	rl
P (X)	:-a(X),b(X),!,	alblr3	X = 3 ? ;
	c(X),d(X),write(p2).	X = 1 ? ;	7 plr2
P (X)	:-write(p3).	no	X = 3 ? ;
a (X)	:-write(al).	1 ?- X=0,r(X).	alblc2dlp2r2
a (X)	:-write(a2).	rl	X = 3 ? ;
			d2p2r2
b (X)	: - X > 0, write(bl) .	X = 0 ? ;	X = 3 ? ;
b (X)	:- X < 0, write(b2) .	plr2	r3
		X = 0 ? ;	
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2	X = 3 ? ;
			
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;	no
			
d (X)	:- abs(X) < 10, write(dl).	r3	
d (X)	: - wri te(d2) .	X = 0 ? ;	
		no	
		1 ?- X=l,r(X).	
r (X)	:-wri te(rl).	rl	
r (X)	:-p(X), wri te(r2).	X = 1 ? ;	
r (X)	:-write(r3).	plr2	
			1 ?- X=3,r(X
P (X)	:-write(pl).	X = 1 ? ;	rl
P (X)	:-a(X),b(X),!,	alblr3	X = 3 ? ;
	c(X),d(X),write(p2).	X = 1 ? ;	7 plr2
P (X)	:-write(p3).	no	X = 3 ? ;
a (X)	:-write(al).	1 ?- X=0,r(X).	alblc2dlp2r2
a (X)	:-write(a2).	rl	X = 3 ? ;
			d2p2r2
b (X)	: - X > 0, write(bl) .	X = 0 ? ;	X = 3 ? ;
b (X)	:- X < 0, write(b2) .	plr2	r3
		X = 0 ? ;	
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2	X = 3 ? ;
			
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;	no
			
d (X)	:- abs(X) < 10, write(dl).	r3	
d (X)	: - wri te(d2) .	X = 0 ? ;	
		no	
I ?- X= -6, r(X).
I ?- X=l,r(X).
r(X)	:-wri te(rl).	rl
r(X)	:-p(X), wri te(r2).	X = 1 ? ;
r(X)	:-write(r3).	plr2
P(X)	:-write(pl).	X = 1 ? ;
P(X)	:-a(X),b(X),!,	alblr3
	c(X),d(X),write(p2).	X = 1 ? ;
P(X)	:-write(p3).	no
a(X)	:-write(al).	1 ?- X=0,r(X).
a(X)	:-write(a2).	rl
b(X)	: - X > 0, write(bl) .	X = 0 ? ;
b(X)	:- X < 0, write(b2).	plr2
		X = 0 ? ;
c(X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2
c(X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;
d(X)	:- abs(X) < 10, write(dl).	r3
d(X)	: - wri te(d2) .	X = 0 ? ;
		no
I ?- X= -6, r(X). rl
I ?- X=3,r(X).   X = -6 ? ; rl
X = 3 ? ; plr2
X = 3 ? ;
alblc2dlp2r2
X = 3 ? ;
d2p2r2
X = 3 ? ;
r3
X = 3 ? ; no
		1 ?- X=l,r(X).	
r (X)	:-wri te(rl).	rl	
r (X)	:-p(X), wri te(r2).	X = 1 ? ;	
r (X)	:-write(r3).	plr2	
			1 ?- X=3,r(X
P (X)	:-write(pl).	X = 1 ? ;	rl
P (X)	:-a(X),b(X),!,	alblr3	X = 3 ? ;
	c(X),d(X),write(p2).	X = 1 ? ;	7 plr2
P (X)	:-write(p3).	no	X = 3 ? ;
a (X)	:-write(al).	1 ?- X=0,r(X).	alblc2dlp2r2
a (X)	:-write(a2).	rl	X = 3 ? ;
			d2p2r2
b (X)	: - X > 0, write(bl) .	X = 0 ? ;	X = 3 ? ;
b (X)	:- X < 0, write(b2).	plr2	r3
		X = 0 ? ;	
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2	X = 3 ? ;
			
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;	no
			
d (X)	:- abs(X) < 10, write(dl).	r3	
d (X)	: - wri te(d2) .	X = 0 ? ;	
		no	
I ?- X= -6, r(X). rl
X = -6 ? ; plr2
X = -6 ? ;
		1 ?- X=l,r(X).	
r (X)	:-wri te(rl).	rl	
r (X)	:-p(X), wri te(r2).	X = 1 ? ;	
r (X)	:-write(r3).	plr2	
			1 ?- X=3,r(X
P (X)	:-write(pl).	X = 1 ? ;	rl
P (X)	:-a(X),b(X),!,	alblr3	X = 3 ? ;
	c(X),d(X),write(p2).	X = 1 ? ;	7 plr2
P (X)	:-write(p3).	no	X = 3 ? ;
a (X)	:-write(al).	1 ?- X=0,r(X).	alblc2dlp2r2
a (X)	:-write(a2).	rl	X = 3 ? ;
			d2p2r2
b (X)	: - X > 0, write(bl) .	X = 0 ? ;	X = 3 ? ;
b (X)	:- X < 0, write(b2) .	plr2	r3
		X = 0 ? ;	
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2	X = 3 ? ;
			
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;	no
			
d (X)	:- abs(X) < 10, write(dl).	r3	
d (X)	: - wri te(d2) .	X = 0 ? ;	
		no	
I ?- X= -6, r(X). rl
X = -6 ? ; plr2
X = -6 ? ; alb2cldlp2r2 X = -6 ? ;
		1 ?- X=l,r(X).	
r (X)	:-wri te(rl).	rl	
r (X)	:-p(X), wri te(r2).	X = 1 ? ;	
r (X)	:-write(r3).	plr2	
			1 ?- X=3,r(X).
P (X)	:-write(pl).	X = 1 ? ;	rl
P (X)	:-a(X),b(X),!,	alblr3	X = 3 ? ;
	c(X),d(X),write(p2).	X = 1 ? ;	7 plr2
P (X)	:-write(p3).	no	X = 3 ? ;
a (X)	:-write(al).	1 ?- X=0,r(X).	alblc2dlp2r2
a (X)	:-write(a2).	rl	X = 3 ? ;
			d2p2r2
b (X)	: - X > 0, write(bl) .	X = 0 ? ;	X = 3 ? ;
b (X)	:- X < 0, write(b2).	plr2	r3
		X = 0 ? ;	
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2	X = 3 ? ;
			
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;	no
			
d (X)	:- abs(X) < 10, write(dl).	r3	
d (X)	: - wri te(d2) .	X = 0 ? ;	
		no	
?- X= -6, r(X) rl
X = -6 ? ; plr2
X = -6 ? ;
alb2cldlp2r2
X = -6 ? ;
d2p2r2
X = -6 ? ;
r (X r (X r (X
P (X P (X
■write(rl) . ■p(X), wri te(r2). ■write(r3) .
■write(pl) . -a(X),b(X),!, c(X),d(X),write(p2)
I ?- X=l,r(X) rl
X = 1 ? ; plr2
X = 1 ? ; alblr3 X = 1 ? ;
I ?- X=3,r(X). rl
X = 3 ? ; plr2
?- X= -6, r(X) rl
X = -6 ? ; plr2
X = -6 ? ; alb2cldlp2r2
P (X)	:-write(p3).	no	X = 3 ? ;	X = -6 ?
a (X)	:-write(al).	1 ?- X=0,r(X).	alblc2dlp2r2	d2p2r2
a (X)	:-write(a2).	rl	X = 3 ? ;	X = -6 ?
			d2p2r2	c2dlp2r2
b (X)	: - X > 0, write(bl) .	X = 0 ? ;	X = 3 ? ;	X = -6 ?
b (X)	:- X < 0, write(b2) .	plr2	r3	
		X = 0 ? ;		
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2	X = 3 ? ;	
				
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;	no	
				
d (X)	:- abs(X) < 10, write(dl).	r3		
d (X)	: - wri te(d2) .	X = 0 ? ; no		
r (X r (X r (X
P (X P (X
-write(rl) . ■p(X),wri te(r2). ■write(r3) .
■write(pl) . -a(X),b(X),!, c(X),d(X),write(p2)
I ?- X=l,r(X) rl
X = 1 ? ; plr2
X = 1 ? ; alblr3 X = 1 ? ;
I ?- X=3,r(X). rl
X = 3 ? ; plr2
?- X= -6, r(X) rl
X = -6 ? ; plr2
X = -6 ? ; alb2cldlp2r2
P (X)	:-write(p3).	no	X = 3 ? ;	X = -6 ? ;
a (X)	:-write(al).	1 ?- X=0,r(X).	alblc2dlp2r2	d2p2r2
a (X)	:-write(a2).	rl	X = 3 ? ;	X = -6 ? ;
			d2p2r2	c2dlp2r2
b (X)	: - X > 0, write(bl) .	X = 0 ? ;	X = 3 ? ;	X = -6 ? ;
b (X)	:- X < 0, write(b2).	plr2	r3	d2p2r2
		X = 0 ? ;		
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2	X = 3 ? ;	X = -6 ? ;
				
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;	no	
				
d (X)	:- abs(X) < 10, write(dl).	r3		
d (X)	: - wri te(d2) .	X = 0 ? ; no		
r (X r (X r (X
P (X P (X
■write(rl) . ■p(X), wri te(r2). ■write(r3) .
■write(pl) . -a(X),b(X),!, c(X),d(X),write(p2)
I ?- X=l,r(X) rl
X = 1 ? ; plr2
X = 1 ? ; alblr3 X = 1 ? ;
I ?- X=3,r(X). rl
X = 3 ? ; plr2
?- X= -6, r(X) rl
X = -6 ? ; plr2
X = -6 ? ; alb2cldlp2r2
P (X)	:-write(p3).	no	X = 3 ? ;	X = -6 ? ;
a (X)	:-write(al).	1 ?- X=0,r(X).	alblc2dlp2r2	d2p2r2
a (X)	:-write(a2).	rl	X = 3 ? ;	X = -6 ? ;
			d2p2r2	c2dlp2r2
b (X)	: - X > 0, write(bl) .	X = 0 ? ;	X = 3 ? ;	X = -6 ? ;
b (X)	:- X < 0, write(b2).	plr2	r3	d2p2r2
		X = 0 ? ;		
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2	X = 3 ? ;	X = -6 ? ;
				r3
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;	no	
				
				X = -6 ? ;
d (X)	:- abs(X) < 10, write(dl).	r3		
d (X)	: - wri te(d2) .	X = 0 ? ;		
		no		
		| ?- X=l,r(X).			
r (X)	:-wri te(rl).	rl			
r (X)	:-p(X), wri te(r2).			1 ?- X= -	-6, r(X)
		X = 1 ? ;		i     ■        * % rl	
r (X)	:-write(r3).	plr2			
			| ?- X=3,r(X).	X = -6 ?	
P (X)	:-write(pl).	X = 1 ? ;	rl	plr2	
P (X)	:-a(X),b(X),!,	alblr3	X = 3 ? ;	X = -6 ?	«
	c(X),d(X),write(p2).	X = 1 ? ;	plr2	alb2cldlp2r2	
P (X)	:-write(p3).	no	X = 3 ? ;	X = -6 ?	j
a (X)	:-write(al).	| ?- X=0,r(X).	alblc2dlp2r2	d2p2r2	
a (X)	:-write(a2).	rl	X = 3 ? ;	X = -6 ?	j
			d2p2r2	c2dlp2r2	
b (X)	: - X > 0, write(bl) .	X = 0 ? ;	X = 3 ? ;	X = -6 ?	j
b (X)	:- X < 0, write(b2) .	plr2	r3	d2p2r2	
		X = 0 ? ;			
c (X)	:- X mod 2 =:= 0, write(cl).	ala2p3r2	X = 3 ? ;	X = -6 ?	j
				r3	
c (X)	:- X mod 3 =:= 0, write(c2).	X = 0 ? ;	no		
				X = -6 ?	
d (X)	:- abs(X) < 10, write(dl).	r3		no	
d (X)	: - wri te(d2) .	X = 0 ? ; no			
Hana Rudová, Logické programování I, 25. března 201 3
10
Seznamy, řez
Řez: maximum
Je tato definice predikátu max/3 korektní?
max(X,Y,X):-X>=Y,!. max(X,Y,Y).
Hana Rudová, Logické programování I, 25. března 201 3
Seznamy, řez
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.
Hana Rudová, Logické programování I, 25. března 201 3
Seznamy, řez
Řez: 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,Z):-X>=Y,!,Z=X.
max(X,Y,Y):-Y>X. max(X,Y,Y).
Problém byl v definici, v první klauzuli se tvrdilo: X=Z a X>=Y => true
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, 25. března 201 3
Seznamy, řez
Ř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] )■
meml(H,[H|_]).
meml(H,[_|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).
Hana Rudová, Logické programování I, 25. března 201 3
12
Seznamy, řez
Ř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] )■
meml(H,[H|_]).
meml(H,[_|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).
M 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)
Hana Rudová, Logické programování I, 25. března 201 3
12
Seznamy, řez
Ř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] )■
meml(H,[H|_]).
meml(H,[_|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).
M 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é
Hana Rudová, Logické programování I, 25. března 201 3
12
Seznamy, řez
Rez: 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] )■
meml(H,[H|_]).
meml(H,[_|T]) :- meml(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)
3 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)
Dokážete napsat variantu, která hledá jenom identické prvky a přitom najde všechny výskyty?
mem2(H,[H|_]) mem2(H,[_|T])
mem2(H,T).
mem3(H,[K|_])  :- H==K.
mem3(H,[K|T])  :- H\==K, mem3(H,T).
Hana Rudová, Logické programování I, 25. března 201 3
12
Seznamy, řez
Rez: 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] )■
meml(H,[H|_]).
meml(H,[_|T]) :- meml(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)
M 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)
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).
mem2(H,[H|_]) mem2(H,[_|T])
mem2(H,T).
mem3(H,[K|_])  :- H==K.
mem3(H,[K|T]) :- H\==K, mem3(H,T).
Hana Rudová, Logické programování I, 25. března 201 3
12
Seznamy, řez
Řez: delete
deleteC X,  [X|S], S ).
deleteC X,  [Y|S],  [Y|S1] ) :- delete(X,S,SI).
Napište predikát delete(X,S,Sl), který odstraní všechny výskyty X (pokud se X v S nevyskytuje, tak predikát uspěje).
Hana Rudová, Logické programování I, 25. března 201 3
13
Seznamy, řez
Rez: delete
deleteC X,  [X|S], S ).
deleteC X,  [Y|S],  [Y|S1] ) :- delete(X,S,SI).
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, [] , [] ).
deleteC X,  [X|S], SI ) :- !, delete(X,S,SI).
deleteC X,  [Y|S],  [Y|S1] ) :- delete(X,S,SI).
Hana Rudová, Logické programování I, 25. března 201 3
Seznamy, řez
Seznamy: 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
Hana Rudová, Logické programování I, 25. března 201 3
14
Seznamy, řez