Seznamy, řez
Reprezentace seznamu
M Seznam: [a,   b,   c], prázdný seznam []
-• Hlava (libovolný objekt), tělo (seznam): .(Hlava,  Telo)
3 všechny strukturované objekty stromy - i seznamy
M funktor".", dva argumenty
3   .(a,   .(b,   .(c,   [])))  =  [a,   b,   c]
-• 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 "I "je seznam zbývajících prvků *  [a,b,c]  =  [a|[b,c]]  =  [a,b|[c]]  =  [a,b,c|[]] M pozor: [   [a,b]   |   [c]   ]   +   [  a,b   |   [c]   ]
-• 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, 23. března 2010                      2                                                                                                 Seznamy, řez
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:
M   prefixC  SI,   S2  )   :-DÚ:   suffix(Sl,S2)
Hana Rudová, Logické programování I, 23. března 2010
3
Seznamy, řez
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:
M  prefixC SI,   S2  )   :- append( SI,  _S3,   S2). DÚ:   suffix(Sl,S2)
Hana Rudová, Logické programování I, 23. března 2010
3
Seznamy, řez
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:
M  prefixC SI,   S2  )   :- append( SI,  _S3,   S2). DÚ:   suffix(Sl,S2)
M  lastC X,   S )   :-
append([3,2],   [6],   [3,2,6]).                X=6,   S=[3,2,6]
Hana Rudová, Logické programování I, 23. března 2010
3
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:
M  prefixC 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, 23. března 2010
3
Seznamy, řez
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:
M  prefixC SI,   S2  )   :- appendC SI,  _S3,   S2). DÚ:   suffix(Sl,S2)
M  last( X,   S )   :- appendC _S1,   [X],   S).
append([3,2],   [6],   [3,2,6]).                X=6,   S=[3,2,6]
M  member( X,   S )   :-
append([3,4,l],   [2,6],   [3,4,1,2,6]).         X=2,   S=[3,4,l,2,6]
DÚ:   adjacent(X,Y,S)
Hana Rudová, Logické programování I, 23. března 2010
3
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:
M  prefixC SI,   S2  )   :- appendC SI,  _S3,   S2). DÚ:   suffix(Sl,S2)
M  last( X,   S )   :- appendC _S1,   [X],   S).
append([3,2],   [6],   [3,2,6]).                X=6,   S=[3,2,6]
M  member( X, S ) :- appendC SI, [X|S2], S ).
appendC[3,4,l], [2,6], [3,4,1,2,6]).   X=2, S=[3,4,l,2,6] DÚ: adjacentCX,Y,S)
Hana Rudová, Logické programování I, 23. března 2010
3
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:
M  prefixC SI,   S2  )   :- appendC SI,  _S3,   S2). DÚ:   suffix(Sl,S2)
M  last( X,   S )   :- appendC _S1,   [X],   S).
append([3,2],   [6],   [3,2,6]).                X=6,   S=[3,2,6]
M  member( X,   S )   :-  appendC SI,   [X|S2],   S ).
appendC[3,4,l],   [2,6],   [3,4,1,2,6]).         X=2,   S=[3,4,l,2,6]
DÚ:   adjacentCX,Y,S)
B  % sublistC+S,+ASB) sublistCS,ASB)   :-
Hana Rudová, Logické programování I, 23. března 2010
3
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:
M  prefixC SI,   S2  )   :- appendC SI,  _S3,   S2). DÚ:   suffix(Sl,S2)
M  last( X,   S )   :- appendC _S1,   [X],   S).
append([3,2],   [6],   [3,2,6]).                X=6,   S=[3,2,6]
M  member( X, S ) :- appendC SI, [X|S2], S ).
appendC[3,4,l], [2,6], [3,4,1,2,6]).   X=2, S=[3,4,l,2,6] DÚ: adjacentCX,Y,S)
B  % 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, 23. března 2010                      3                                                                                                 Seznamy, řez
Optimalizace posledního volání
-• Last Call Optimization (LCO)
M 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ěť
-• Použití LCO umožňuje vnořenou rekurzi s konstantními pametový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é
3 p(   ...):-   ...                            % žádné  rekurzivní   voláni   v těle  klauzule
p(   ...):-   ...                            % žádné  rekurzivní   voláni  v těle  klauzule
p(...)   :-   ...,   !,   p(   ...   ).  % řez zajišťuje determinismus
-• Tento typ rekurze lze převést na iteraci
Hana Rudová, Logické programování I, 23. března 2010                      4                                                                                                 Seznamy, řez
LCO a akumulátor
-• 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.
Hana Rudová, Logické programování I, 23. března 2010
5
Seznamy, řez
LCO a akumulátor
-• 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''
Hana Rudová, Logické programování I, 23. března 2010                      5                                                                                                 Seznamy, řez
LCO a akumulátor
-• 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   |   T ] ,  A,   Délka )   :- A0 is A + 1,   lengthC T,  A0,   Délka ).
M Přídavný argument se nazývá akumulátor
Hana Rudová, Logické programování I, 23. března 2010
5
Seznamy, řez
Akumulátor a sum
?-  sum_list(   [2,3,4],   Sum ). bez akumulátoru:
Hana Rudová, Logické programování I, 23. března 2010                      6
list(S,Sum)
Seznamy, řez
Akumulátor a sum_list(S,Sum)
?-  sum_list(   [2,3,4],   Sum ).
bez akumulátoru: sum_list(   [] ,   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, 23. března 2010
6
Výpočet faktoriálu f act (N, F)
s akumulátorem:
Hana Rudová, Logické programování I, 23. března 2010                      7                                                                                                 Seznamy, řez
Výpočet faktoriálu f act (N, F)
s akumulátorem: factC N,   F )   :-  fact  (N,   1,   F ).
factC  1,   F,   F )   :-   !. factC  N,   A,   F )   :-     N > 1,
Al is  N  * A,
Nl is  N  -  1,
factC  Nl,   Al,   F ).
Hana Rudová, Logické programování I, 23. března 2010
7
■write(rl) . -p(X),write(r2). -write(r3) .
■write(pi) . -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 =:= 0,  write(cl)
■  X mod  3 =:= 0,  write(c2)
■   abs(X)  < 10,  write(dl).
■  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).            (2)  X=3,r(X).
(3)  X=0,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
-write(rl) . -p(X),write(r2) -write(r3) .
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).             (2)  X=3,r(X).
(3)  X=0,r(X).             (4)  X= -6,r(X)
-write(pi) . -a(X),b(X),!,
c(X) ,d(X) ,write(p2).           M vez v predikátu p/l  neovlivní alternativy
-write(p3).                                   predikátu r/l
-wnte(a;.                             ^ dokud   nebyl   proveden  řez,  alternativy
-write(a2).                                                                                             ..     „        ,     „
predikátu a/l se uplatňuji, pr. neúspech
-  X > 0, write(bl).                    b/1 v dotazu (3)
-  X < 0,  write(b2).
-• při neúspěchu cíle za řezem se výpočet
-  X mod  2 =:= 0,  write(cl).                    ,   - .       .   .. ,              ,   -      /n      .    /ns
navrací az k volající procedure r/1, viz (1)
-  X mod  3 =:= 0,  write(c2).
3 alternativy vzniklé po provedení řezu se
-   abs(X)  < 10,  write(dl).
, , N                                   zachovávají - další možnosti  predikátu
-  wnte(d2) .
c/1 viz (2) a (4)
Hana Rudová, Logické programování I, 23. března 2010                      8                                                                                                 Seznamy, řez
-write(rl). -p(X),write(r2). -write(r3).
-write(pi) . -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 =:= 0, write(cl).
- X mod 3 =:= 0, write(c2).
- abs(X) < 10, write(dl).
- write(d2) .
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
- X=l,r(X).
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
rl X
X=l,r(X). 1 7 ■
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
| ?- 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(pi). 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 ? ;
-writeCrl) . -pCX),writeCr2). -writeCr3).
-writeCpi) ■ -aCX),bCX),!,
cCX),dCX),writeCp2). -writeCp3).
-writeCal). -writeCa2).
- X > O, writeCbl).
- X < O, writeCb2).
- X mod 2 =:= O, write Cel)
- X mod 3 =:= 0, writeCc2)
- absCX) < 10, write(dl).
- writeCd2) .
rCX).
					| ?- X=l,rCX)
rCX)	-writeCrl) .				rl
rCX)	-pCX),writeCr2).				X = 1 ? ;
rCX)	-writeCr3).				plr2
PCX)	-writeCpi) ■				X = 1 ? ;
PCX)	-aCX),bCX),!,				alblr3
	cCX),dCX),write	Cp2)	i		X = 1 ? ;
PCX)	-writeCp3).				no
aCX)	-writeCal).				| ?- X=0,rCX)
aCX)	-writeCa2).				
bCX)	- X > 0, writeCbl) .				
bCX)	- X < 0, writeCb2) .				
cCX)	- X mod 2 =:= 0,	wri	te(c	1).	
cCX)	- X mod 3 =:= 0,	wri	te(c	2).	
dCX)	- absCX) < 10, write(dl)			■	
dCX)	- write(d2) .				
I   ?- X=l,r(X) -write(rl).                                    rl
-p(X),write(r2).                         X = 1 ?   ;
-write(r3).                                   plr2
■write(pi) . -a(X),b(X),!, c(X),d(X),write(p2) ■write(p3) .
X = 1 ?   ; alblr3 X = 1 ?   ; no
-write(al).                                    ,   ?_ x=0jr(x)
■write(a2).                                    rl
■  X > 0,  writeCbl).                   X = 0 ?   ;
■  X < 0,  write(b2).
■  X mod 2 =:= 0,  write(cl).
■  X mod  3 =:= 0,  write(c2).
■   abs(X)  < 10,  write(dl).
■  write(d2) .
	I ?- X=l,r(X)
write(rl) .	rl
p(X),write(r2).	X = 1 ? ;
write(r3) .	plr2
write (pi) .	X = 1 ? ;
a(X),b(X),!,	alblr3
c(X),d(X),write(p2).	X = 1 ? ;
write(p3) .	no
write(al) .	I ?- X=0,r(X)
write(a2).	rl
X > 0, writeCbl).	X = 0 ? ;
X < 0, write(b2).	plr2
	X = 0 ? ;
X mod 2 =:= 0,  write(cl). X mod  3 =:= 0,  write(c2).
abs(X)  < 10,  write(dl). write(d2) .
I ?- X=l,r(X) -write(rl).                                  rl
-p(X),write(r2).                        X = 1 ? ;
-write(r3).                                  plr2
■write(pi) . -a(X),b(X),!, c(X),d(X),write(p2) ■write(p3) .
X = 1 ? ; alblr3 X = 1 ? ; no
-write(al).                                  , ?_ x=0jr(x)
-write(a2).                                  rl
■ X > 0, writeCbl).                  X = 0 ? ;
■ X < 0, write(b2).                  Plr2
X mod 2 =:= 0, write(cl) X mod 3 =:= 0, write(c2)
abs(X) < 10, write(dl). write(d2) .
X = 0 ? ala2p3r2 X = 0 ?
				I ?- X=l,r(X)
write(rl) .				rl
p(X),write(r2).				X = 1 ? ;
write(r3) .				plr2
write (pi) .				X = 1 ? ;
a(X),b(X),!,				alblr3
c(X),d(X),write	(p2)	i		X = 1 ? ;
write(p3) .				no
write(al) .				I ?- X=0,r(X)
write(a2).				rl
X > 0, writeCbl).				X = 0 ? ;
X < 0, write(b2).				plr2
				X = 0 ? ;
X mod 2 =:= 0, X mod 3 =:= 0,	wri wri	te(c te(c	1). 2).	ala2p3r2 X = 0 ? ;
abs(X) < 10, write(dl)			■	r3
write(d2) .				X = 0 ? ;
I   ?- X=l,r(X) -write(rl).                                    rl
-p(X),write(r2).                         X = 1 ?   ;
-write(r3).                                   plr2
■write(pi) . -a(X),b(X),!, c(X),d(X),write(p2) ■write(p3) .
X = 1 ?   ; alblr3 X = 1 ?   ; no
-write(al).                                    ,   ?_ x=0jr(x)
■write(a2).                                    rl
■  X > 0,  writeCbl).                   X = 0 ?
■  X < 0,  write(b2).                    Plr2
X = 0 ? ala2p3r2 X = 0 ?
abs(X)  < 10,  write(dl).        r3 write(d2).                                 X = 0 ?
no
X mod 2 =:= 0,  write(cl) X mod  3 =:= 0,  write(c2)
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
| ?- X=l,r(X)
rl
X = 1 ? ;
plr2
X = 1 ? ;
alblr3
X = 1 ? ;
no
?- X=3,r(X)
?- X=0,r(X) rl
X = 0 ? plr2 X = 0 ? ala2p3r2 X = 0 ? r3 X = 0 ?
no
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
| ?- X=l,r(X)
rl
X = 1 ? ;
plr2
X = 1 ? ;
alblr3
X = 1 ? ;
no
| ?- X=3,r(X)
rl
X = 3 ? ;
?- X=0,r(X) rl
X = 0 ? plr2 X = 0 ? ala2p3r2 X = 0 ? r3 X = 0 ?
no
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
| ?- X=l,r(X)
rl
X = 1 ? ;
plr2
X = 1 ? ;
alblr3
X = 1 ? ;
no
| ?- X=3,r(X)
rl
X = 3 ? ;
plr2
X = 3 ? ;
?- X=0,r(X) rl
X = 0 ? plr2 X = 0 ? ala2p3r2 X = 0 ? r3 X = 0 ?
no
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
| ?- X=l,r(X).
rl
X = 1 ? ;
plr2
X = 1 ? ;
alblr3
X = 1 ? ;
no
| ?- X=0,r(X).
rl
X = 0 ? ;
plr2
X = 0 ? ;
ala2p3r2
X = 0 ? ;
r3
X = 0 ? ;
no
| ?- X=3,r(X).
rl
X = 3 ? ;
plr2
X = 3 ? ;
alblc2dlp2r2
X = 3 ? ;
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
| ?- X=l,r(X).
rl
X = 1 ? ;
plr2
X = 1 ? ;
alblr3
X = 1 ? ;
no
| ?- X=0,r(X).
rl
X = 0 ? ;
plr2
X = 0 ? ;
ala2p3r2
X = 0 ? ;
r3
X = 0 ? ;
no
| ?- X=3,r(X).
rl
X = 3 ? ;
plr2
X = 3 ? ;
alblc2dlp2r2
X = 3 ? ;
d2p2r2
X = 3 ? ;
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
| ?- X=l,r(X).
rl
X = 1 ? ;
plr2
X = 1 ? ;
alblr3
X = 1 ? ;
no
| ?- X=0,r(X).
rl
X = 0 ? ;
plr2
X = 0 ? ;
ala2p3r2
X = 0 ? ;
r3
X = 0 ? ;
no
| ?- X=3,r(X).
rl
X = 3 ? ;
plr2
X = 3 ? ;
alblc2dlp2r2
X = 3 ? ;
d2p2r2
X = 3 ? ;
r3
X = 3 ? ;
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
| ?- X=l,r(X).
rl
X = 1 ? ;
plr2
X = 1 ? ;
alblr3
X = 1 ? ;
no
| ?- X=0,r(X).
rl
X = 0 ? ;
plr2
X = 0 ? ;
ala2p3r2
X = 0 ? ;
r3
X = 0 ? ;
no
| ?- X=3,r(X).
rl
X = 3 ? ;
plr2
X = 3 ? ;
alblc2dlp2r2
X = 3 ? ;
d2p2r2
X = 3 ? ;
r3
X = 3 ? ;
no
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
| ?- X=l,r(X).
rl
| ?- X= -6, r(X). X = 1 ? ;
plr2
| ?- X=3,r(X). X = 1 ? ;
rl alblr3
X = 3 ? ; X = 1 ? ;
plr2 no
X = 3 ? ;
alblc2dlp2r2 | ?- X=0,r(X).
X = 3 ? ; rl
d2p2r2 X = 0 ? ;
X = 3 ? ; plr2
r3 X = 0 ? ;
X = 3 ? ; ala2p3r2
no X = 0 ? ;
r3
X = 0 ? ;
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
| ?- X=l,r(X).
rl
| ?- X= -6, r(X). X = 1 ? ;
rl plr2
| ?- X=3,r(X). X = -6 ? ; X = 1 ? ;
rl alblr3
X = 3 ? ; X = 1 ? ;
plr2 no
X = 3 ? ;
alblc2dlp2r2 | ?- X=0,r(X).
X = 3 ? ; rl
d2p2r2 X = 0 ? ;
X = 3 ? ; plr2
r3 X = 0 ? ;
X = 3 ? ; ala2p3r2
no X = 0 ? ;
r3
X = 0 ? ;
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
| ?- X=l,r(X)
rl
X = 1 ? ;
plr2
X = 1 ? ;
alblr3
X = 1 ? ;
no
?- X=0,r(X) rl
X = 0 ? plr2 X = 0 ? ala2p3r2 X = 0 ? r3 X = 0 ?
| ?- X=3,r(X).
rl
X = 3 ? ;
plr2
X = 3 ? ;
alblc2dlp2r2
X = 3 ? ;
d2p2r2
X = 3 ? ;
r3
X = 3 ? ;
no
| ?- X= -6, r(X)
rl
X = -6 ? ;
plr2
X = -6 ? ;
no
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
1 ?- x=i,	r (X).		
rl			| ?- X= -6, r(X)
X = 1 ? ;			rl
plr2			
		| ?- X=3,r(X).	X = -6 ? ;
X = 1 ? ;			
		rl	plr2
alblr3			
		X = 3 ? ;	X = -6 ? ;
X = 1 ? ;			
		plr2	alb2cldlp2r2
no			
		X = 3 ? ;	X = -6 ? ;
		alblc2dlp2r2	
1 ?- x=o,	r (X).	X = 3 ? ;	
rl		d2p2r2	
X = 0 ? ;		X = 3 ? ;	
plr2		r3	
X = 0 ? ;		X = 3 ? ;	
ala2p3r2		no	
X = 0 ? ;			
r3			
X = 0 ? ;			
no
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
1 ?- x=i,	r (X).		
rl			| ?- X= -6, r(X)
X = 1 ? ;			rl
plr2			
		| ?- X=3,r(X).	X = -6 ? ;
X = 1 ? ;			
		rl	plr2
alblr3			
		X = 3 ? ;	X = -6 ? ;
X = 1 ? ;			
		plr2	alb2cldlp2r2
no			
		X = 3 ? ;	X = -6 ? ;
		alblc2dlp2r2	d2p2r2
1 ?- x=o,	r (X).		
		X = 3 ? ;	X = -6 ? ;
rl		d2p2r2	
X = 0 ? ;		X = 3 ? ;	
plr2		r3	
X = 0 ? ;		X = 3 ? ;	
ala2p3r2		no	
X = 0 ? ;			
r3			
X = 0 ? ;			
no
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
1 ?- x=i,	r (X).			
rl				| ?- X= -6, r(X)
X = 1 ? ;				rl
plr2				
		1 ?- X=3,r	(X).	X = -6 ? ;
X = 1 ? ;		rl		plr2
alblr3		X = 3 ? ;		X = -6 ? ;
X = 1 ? ;		plr2		alb2cldlp2r2
no		X = 3 ? ;		X = -6 ? ;
		alblc2dlp2	r2	d2p2r2
1 ?- x=o,	r (X).	X = 3 ? ;		X = -6 ? ;
rl		d2p2r2		c2dlp2r2
X = 0 ? ;		X = 3 ? ;		X = -6 ? ;
plr2		r3		
X = 0 ? ;		X = 3 ? ;		
ala2p3r2		no		
X = 0 ? ;				
r3				
X = 0 ? ;				
no
r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3).
p(X):-write(pi). 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 > 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).
1 ?- x=i,	r (X).			
rl				| ?- X= -6, r(X)
X = 1 ? ;				rl
plr2				
		1 ?- X=3,r	(X).	X = -6 ? ;
X = 1 ? ;		rl		plr2
alblr3		X = 3 ? ;		X = -6 ? ;
X = 1 ? ;		plr2		alb2cldlp2r2
no		X = 3 ? ;		X = -6 ? ;
		alblc2dlp2	r2	d2p2r2
1 ?- x=o,	r (X).	X = 3 ? ;		X = -6 ? ;
rl		d2p2r2		c2dlp2r2
X = 0 ? ;		X = 3 ? ;		X = -6 ? ;
plr2		r3		d2p2r2
X = 0 ? ;		X = 3 ? ;		X = -6 ? ;
ala2p3r2		no		
X = 0 ? ;				
r3				
X = 0 ? ;				
no
■write(rl) . -p(X),write(r2). ■write(r3) .
■write(pi) . -a(X),b(X),!, c(X),d(X),write(p2). ■write(p3) .
■write(al) . ■write(a2) .
■   X > 0,  writeCbl).
■   X < 0,  write(b2).
■   X mod 2 =:= 0,  write(cl)
■   X mod  3 =:= 0,  write(c2)
■   abs(X)  < 10,  write(dl).
■   write(d2) .
1 ?- x=i,	r(X).			
rl				I ?- X= -6, r
X = 1 ? ;				rl
plr2				
		1 ?- X=3,r	(X).	X = -6 ? ;
X = 1 ? ;		rl		plr2
alblr3		X = 3 ? ;		X = -6 ? ;
X = 1 ? ;		plr2		alb2cldlp2r2
no		X = 3 ? ;		X = -6 ? ;
		alblc2dlp2	r2	d2p2r2
1 ?- x=o,	r(X).	X = 3 ? ;		X = -6 ? ;
rl		d2p2r2		c2dlp2r2
X = 0 ? ;		X = 3 ? ;		X = -6 ? ;
plr2		r3		d2p2r2
X = 0 ? ;		X = 3 ? ;		X = -6 ? ;
ala2p3r2		no		r3
X = 0 ? ;				X = -6 ? ;
r3				
X = 0 ? ;				
no
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
I ?- X=l, -write(rl).                                          rl
-p(X),write(r2).                             X = 1 ? ;
-write(r3).                                    plr2
-write(pi) . -a(X),b(X),!,
c(X),d(X),write(p2) -write(p3).
X = 1 ? ; alblr3 X = 1 ? ; no
:-write(al).                                    ■ ?_ X=Q
:-write(a2).                                      -
:- X > 0, write(bl).       X = 0  ?
:- X < 0, write(b2).        Plr2
X = 0  ? ala2p3r2
X = 0  ?
:- abs(X) < 10, write(dl).   r3
:- write(d2).                                  X = 0  ?
:- X mod 2 =:= 0, write(cl) :- X mod 3 =:= 0, write(c2)
no
Hana Rudová, Logické programování I, 23. března 2010
| ?- X=3,r(X).
rl
X = 3 ? ;
plr2
X = 3 ? ;
alblc2dlp2r2
X = 3 ? ;
d2p2r2
X = 3 ? ;
r3
X = 3 ? ;
no
| ?- X= -6, r(X).
rl
X = -6 ? ;
plr2
X = -6 ? ;
alb2cldlp2r2
X = -6 ?   ;
d2p2r2
X = -6 ?   ;
c2dlp2r2
X = -6 ?   ;
d2p2r2
X = -6 ?   ;
r3
X = -6 ?   ;
no
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, 23. března 201 0                     10
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.
Hana Rudová, Logické programování I, 23. března 201 0                     10
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í 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, 23. března 2010                     10                                                                                                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, 23. března 2010                     1 1
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).
-• 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, 23. března 2010                     1 1
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).
-• 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, 23. března 2010                     1 1
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).
-• 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?
Hana Rudová, Logické programování I, 23. března 2010                     11                                                                                                 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).
-• 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).
Hana Rudová, Logické programování I, 23. března 2010                     11                                                                                                 Seznamy, řez
Řez: delete
deleteC X,   [X|S],   S ).
deleteCX,   [Y|S],   [Y|S1]   )   :- delete(X,S,Sl).
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).
Hana Rudová, Logické programování I, 23. března 201 0                     12
Seznamy, řez
Řez: delete
deleteC X,   [X|S],   S ).
deleteCX,   [Y|S],   [Y|S1]   )   :- delete(X,S,Sl).
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).
Hana Rudová, Logické programování I, 23. března 201 0                     12
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, 23. března 201 0                     13
Seznamy, řez