Seznamy, řez
Reprezentace seznamu
& Seznam: [a, b, c], prázdný seznam []
& Hlava (libovolný objekt), telo (seznam): .(Hlava, Telo)
všechny strukturované objekty stromy - i seznamy -i- funktordva argumenty
.(a,  .(b,  .(c, []))) = [a, b, c] -i- notace: [ Hlava | Telo ] = [a|Te1o]
Telo je v [a|Te1o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ]
C Lze psát i: [a,b|Te1o]
J* pred "|"je libovolný pocet prvků seznamu , za "|"je seznam zbývajících prvků [a,b,c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] pozor: [ [a,b]  |  [c] ] = [ a,b |  [c] ]
& Seznam jako neúplná datová struktura: [a,b,c|T]
A Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S]
Hana Rudová, Logické programování I, 18. března 2011 2 Seznamy, rez
Cvičení: append/2
appendC [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).     % (2)
:- append([1,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). | (1)
| C=[3,4]    => A=[1,2,3,4], yes
Hana Rudová, Logické programování I, 18. března 2011
3
Seznamy, řez
Cvičení: append/2
appendC [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).     % (2)
:- append([1,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). | (1)
| C=[3,4]    => A=[1,2,3,4], yes
Předchůdce a naslednik prvku X v seznamu S
hledej(S,X,Pred,Po) :- append( _S1, [ Pred,X,Po | _S2 ], S)
Hana Rudová, Logické programování I, 18. března 2011 3 Seznamy, řez
Seznamy a append
append( [], S, S ).
append( [X|S1], S2,  [X|S3] )       append( S1, S2, S3).
Napište následující predikáty pomocí append/3:
Jí* prefix( S1, S2 ) :-DÚ: suffix(S1,S2)
Hana Rudová, Logické programování I, 18. března 2011
4
Seznamy, řez
Seznamy a append
append( [], S, S ).
append( [X|S1], S2,  [X|S3] )       append( S1, S2, S3).
Napište následující predikáty pomocí append/3:
Jí* prefix( S1, S2 )      append( S1, _S3, S2). DÚ: suffix(S1,S2)
Hana Rudová, Logické programování I, 18. března 2011
4
Seznamy, řez
Seznamy a append
append( [], S, S ).
append( [X|S1], S2,  [X|S3] )       append( S1, S2, S3).
Napište následující predikáty pomocí append/3:
Jí* prefix( S1, S2 )      append( S1, _S3, S2). DÚ: suffix(S1,S2)
M last( X, S ) :-
append([3,2],  [6],  [3,2,6]). X=6, S=[3,2,6]
Hana Rudová, Logické programování I, 18. března 2011
4
Seznamy, řez
Seznamy a append
append( [], S, S ).
append( [X|S1], S2,  [X|S3] )       append( S1, S2, S3).
Napište následující predikáty pomocí append/3:
Jí* prefix( S1, S2 )      append( S1, _S3, S2). DÚ: suffix(S1,S2)
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, 18. března 2011
4
Seznamy, řez
Seznamy a append
append( [], S, S ).
append( [X|S1], S2,  [X|S3] )       append( S1, S2, S3).
Napište následující predikáty pomocí append/3:
prefix( S1, S2 )      append( S1, _S3, S2). DÚ: suffix(S1,S2)
last( X, S )      append( _S1, [X], S). append([3,2],  [6],  [3,2,6]). X=6, S=[3,2,6]
& member( X, S )
append([3,4,1], [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, 18. března 2011
4
Seznamy, řez
Seznamy a append
append( [], S, S ).
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).
Napište následující predikáty pomocí append/3:
& prefix( S1, S2 ) :- append( S1, _S3, S2). DÚ: suffix(S1,S2)
last( X, S ) :- append( _S1, [X], S). append([3,2],  [6],  [3,2,6]). X=6, S=[3,2,6]
& member( X, S ) :- append( S1, [X|S2], S ).
append([3,4,1], [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, 18. března 2011
4
Seznamy, řez
Seznamy a append
append( [], S, S ).
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).
Napište následující predikáty pomocí append/3:
& prefix( S1, S2 ) :- append( S1, _S3, S2). DÚ: suffix(S1,S2)
last( X, S ) :- append( _S1, [X], S). append([3,2],  [6],  [3,2,6]). X=6, S=[3,2,6]
& member( X, S ) :- append( S1, [X|S2], S ).
append([3,4,1], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S)
J£ % sublist(+S,+ASB) sublist(S,ASB) :-
Hana Rudová, Logické programování I, 18. března 2011
4
Seznamy, řez
Seznamy a append
append( [], S, S ).
appendC [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).
Napište následující predikáty pomocí append/3:
& prefix( S1, S2 ) :- append( S1, _S3, S2). DÚ: suffix(S1,S2)
last( X, S ) :- append( _S1, [X], S). append([3,2],  [6],  [3,2,6]). X=6, S=[3,2,6]
& member( X, S ) :- append( S1, [X|S2], S ).
append([3,4,1],  [2,6],  [3,4,1,2,6]).       X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S)
J£ % 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, 18. března 2011 4 Seznamy, rez
Optimalizace posledního volání
Last Call Optimization (LCO)
Implementační technika snižující nároky na paměť
Mnoho vnorených rekurzivních volání je náročné na paměť
Použití LCO umožnuje vnorenou rekurzi s konstantními palmetovými nároky Typický príklad, kdy je možné použití LCO:
A procedura musí mít pouze jedno rekurzivní volání: v posledním cíli poslední klauzule
A cíle predcházející tomuto rekurzivnímu volání musí být deterministické
-i> p( ... ) :- ... % žádné rekurzivní volání v těle klauzule
p( ...):- ... % žádné rekurzivní volání v těle klauzule
p(...) :- !, p( ... ). % rez zajišťuje determinismus
& Tento typ rekurze lze převést na iteraci
Hana Rudová, Logické programování I, 18. března 2011 5 Seznamy, rez
LCO a akumulátor
-í* Reformulace rekurzivní procedury, aby umožnila LCO VýpoCet délky seznamu 1ength( Seznam, Delka )
1ength( [], 0 ).
1ength( [ H | T ], Delka ) :- 1ength( T, DelkaO ), Delka is 1 + DelkaO.
Hana Rudová, Logické programování I, 18. března 2011 6 Seznamy, řez
LCO a akumulátor
-í* Reformulace rekurzivní procedury, aby umožnila LCO & VýpoCet délky seznamu 1ength( Seznam, Delka )
1ength( [], 0 ).
1ength( [ H | T ], Delka ) :- 1ength( T, DelkaO ), Delka is 1 + DelkaO.
-í* Upravená procedura, tak aby umožnila LCO:
% 1ength( Seznam, ZapocitanaDelka, CelkovaDelka ):
% CelkovaDelka = ZapocitanaDelka + ,,poCet prvků v Seznam''
Hana Rudová, Logické programování I, 18. b rezna 2011
6
Seznamy, rez
LCO a akumulátor
-í* Reformulace rekurzivní procedury, aby umožnila LCO & Výpocet délky seznamu length( Seznam, Delka )
length( [], 0 ).
length( [ H | T ], Delka )      length( T, DelkaO ), Delka is 1 + DelkaO.
-í* Upravená procedura, tak aby umožnila LCO:
% length( Seznam, ZapocitanaDelka, CelkovaDelka ):
% CelkovaDelka = ZapocitanaDelka + ,,počet prvku v Seznam''
length( Seznam, Delka )      length( Seznam, 0, Delka ). % pomocný predikát
length( [], Delka, Delka ). % celková délka = zapocítaná délka
length( [ H | T ], A, Delka )      A0 is A + 1, length( T, A0, Delka ).
& Prídavný argument se nazývá akumulátor
Hana Rudová, Logické programování I, 18. b rezna 2011
6
Seznamy, rez
Akumulátor a sum_list(S,Sum)
?- sum_list( [2,3,4], Sum ).
Hana Rudová, Logické programování I, 18. b rezna 2011
7
Seznamy, rez
Akumulátor a sům_1ist(S,Sům)
?- sům_1ist( [2,3,4], Sům ).
bez akumulátoru: sům_1ist( [], 0 ).
sům_1ist( [H|T], Sům ) :- sům_1ist( T, SůmT ),
Sům is H + SůmT.
s akumulátorem:
sům_1ist( S, Sům ) :-   sům_1ist( S, 0, Sům ).
sům_1ist( [], Sům, Sům ).
sům_1ist( [H|T], A, Sům )  :- A1 is A + H,
sům_1ist( T, A1, Sům).
Hana Rudová, Logické programování I, 18. b rezna 2011
7
Seznamy, rez
Výpočet faktoriálu fact(N,F)
s akumulátorem:
Hana Rudová, Logické programování I, 18. b rezna 2011
8
Seznamy, rez
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,
A1 is N * A, N1 is N - 1, fact( N1, A1, F ).
Hana Rudová, Logické programování I, 18. b rezna 2011
8
Seznamy, rez
r(X):-write(r1).
r(X):-p(X),write(r2).
r(X):-write(r3).
Prozkoumejte trasy výpoctu a navracení napr. pomocí následujících dotazů (vždy si stredníkem vyžádejte navracení):
p(X):-write(p1). p(X):-a(X),b(X),l,
(1) X=1,r(X). (3) X=Q,r(X).
(2) X=3,r(X). (4) X= -6,r(X).
c(X),d(X),write(p2). p(X):-write(p3).
a(X):-write(a1). a(X):-write(a2).
b(X):- X > 0, write(b1). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2).
d(X):- abs(X) < 10, write(d1). d(X):- write(d2).
r(X):-wn'te(r1). r(X):-p(X),write(r2). r(X):-wn'te(r3).
p(X):-wn'te(p1). p(X):-a(X),b(X),l,
c(X),d(X),write(p2). p(X):-wn'te(p3).
a(X):-write(al). a(X):-wn'te(a2).
b(X):- X > 0, write(bl). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, wn'te(cl). c(X):- X mod 3 =:= 0, wn'te(c2).
d(X):- abs(X) < 10, write(dl). d(X):- wnte(d2).
Prozkoumejte trasy výpoCtu a navracení nap r . pomocí následujících dotazů (vždy si stredníkem vyžádejte navracení):
(1) X=1,r(X). (3) X=0,r(X).
(2) X=3,r(X). (4) X= -6,r(X).
rez v predikátu p/1 neovlivní alternativy predikátu r/1
dokud nebyl proveden rez, alternativy predikátu a/1 se uplatnují, p r . neúspech b/1 v dotazu (3)
p r i neúspechu cíle za rezem se výpocet navrací až k volající procedu r e r/1, viz (1)
alternativy vzniklé po provedení rezu se zachovávají - další možnosti predikátu c/1 viz (2) a (4)
Hana Rudová, Logické programování I, 18. b rezna 2011
Seznamy, rez
9
r(X):-write(r1).
r(X):-p(X),write(r2).
r(X):-write(r3).
p(X):-write(p1). p(X):-a(X),b(X),!,
c(X),d(X),write(p2). p(X):-write(p3).
a(X):-write(a1). a(X):-write(a2).
b(X):- X > 0, write(b1). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2).
d(X):- abs(X) < 10, write(d1). d(X):- write(d2).
r(X)i-write(rl).
r(X)i-p(X),write(r2).
r(X)i-write(rB).
pCX)i-write(pl). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). pCX)i-write(pB).
a(X)i-write(al). a(X)i-write(a2).
b(X)i- X > G, write(bl). b(X)i- X < G, write(b2).
c(X)i- X mod 2 =i= G, write(cl). c(X)i- X mod B =i= G, write(c2).
j ?- X=l,r(X).
d(X)i- abs(X) < 1G, write(dl). d(X)i- write(d2).
r(X)i-write(r1).
r(X)i-p(X),write(r2).
r(X)i-write(r3).
p(X)i-write(p1). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). p(X)i-write(p3).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > O, write(b1). b(X)i- X < O, write(b2).
c(X)i- X mod 2 =i= O, write(c1). c(X)i- X mod 3 =i= O, write(c2).
d(X)i- abs(X) < 1O, write(d1). d(X)i- write(d2).
j ?- X=1,r(X). r1
X = 1 ? ;
j ?- X=1,r(X).
r(X):-write(r1).
r(X):-p(X),write(r2).
r(X):-write(r3).
X=
p1r2
r1
1 ? ■
X=
p(X):-write(p1). p(X):-a(X),b(X),!,
c(X),d(X),write(p2). p(X):-write(p3).
a(X):-write(a1). a(X):-write(a2).
b(X):- X > 0, write(b1). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2).
d(X):- abs(X) < 10, write(d1). d(X):- write(d2).
r(X)i-write(r1).
r(X)i-p(X),write(r2).
r(X)i-write(r3).
p(X)i-write(p1). p(X)i-aCX),b(X),i,
c(X),d(X),write(p2). p(X)i-write(p3).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > G, write(b1). b(X)i- X < G, write(b2).
c(X)i- X mod 2 =i= G, write(c1). c(X)i- X mod 3 =i= G, write(c2).
d(X)i- abs(X) < 1G, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ ; p1r2
X = 1 ľ ;
a1b1r3 X = 1 ľ ;
r(X)i-write(rl).
r(X)i-p(X),write(r2).
r(X)i-write(rB).
pCX)i-write(pl). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). pCX)i-write(pB).
a(X)i-write(al). a(X)i-write(a2).
b(X)i- X > G, write(bl). b(X)i- X < G, write(b2).
c(X)i- X mod 2 =i= G, write(cl). c(X)i- X mod B =i= G, write(c2).
d(X)i- abs(X) < 1G, write(dl). d(X)i- write(d2).
j ľ- X=l,r(X). rl
X = 1 ľ ; plr2
X = 1 ľ ; alblrB X = 1 ľ ; no
r(X)i-write(rl). r(X)i-p(X),write(r2).
r(X)i-writeCrB).
pCX)i-write(pl). pCX)i-aCX),bCX),i,
c(X),d(X),write(p2).
pCX)i-write(pB).
a(X)i-writeCal). a(X)i-writeCa2).
b(X)i- X > G, write(bl). b(X)i- X < G, write(b2).
c(X)i- X mod 2 =i= G, write(cl). c(X)i- X mod B =i= G, write(c2).
d(X)i- abs(X) < 1G, write(dl). d(X)i- write(d2).
j ľ- X=l,rCX). rl
X = 1 ľ ; plr2
X = 1 ľ ;
alblrB X = 1 ľ ;
no
j ľ- X=G,r(X).
r(X)i-write(r1).
r(X):-p(X),write(r2).
r(X)i-write(r3).
p(X)i-write(p1). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). p(X)i-write(p3).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > O, write(b1). b(X)i- X < O, write(b2).
c(X)i- X mod 2 =i= O, write(c1). c(X)i- X mod 3 =:= O, write(c2).
d(X)i- abs(X) < 1O, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ ; p1r2
X = 1 ľ ;
a1b1r3 X = 1 ľ ;
no
j ľ- X=O,r(X). r1
X = O ľ ;
r(X)i-write(r1).
r(X)i-p(X),write(r2).
r(X)i-write(r3).
p(X)i-write(p1). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). p(X)i-write(p3).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2).
c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod 3 =i= 0, write(c2).
d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ i p1r2
X = 1 ľ i a1b1r3 X = 1 ľ i no
j ľ- X=0,r(X). r1
X = 0 ľ i p1r2
X = 0 ľ i
r(X)i-write(r1).
r(X)i-p(X),write(r2).
r(X)i-write(r3).
p(X)i-write(p1). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). p(X)i-write(p3).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > O, write(b1). b(X)i- X < O, write(b2).
c(X)i- X mod 2 =i= O, write(c1). c(X)i- X mod 3 =i= O, write(c2).
d(X)i- abs(X) < 1O, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ i p1r2
X = 1 ľ i a1b1r3 X = 1 ľ i no
j ľ- X=O,r(X). r1
X = O ľ i p1r2
X = O ľ i a1a2p3r2 X = O ľ i
r(X):-write(r1).
r(X):-p(X),write(r2).
r(X):-write(r3).
p(X):-write(p1). p(X):-a(X),b(X),!,
c(X),d(X),write(p2). p(X):-write(p3).
a(X):-write(a1). a(X):-write(a2).
b(X):- X > 0, write(b1). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2).
d(X):- abs(X) < 10, write(d1). d(X):- write(d2).
j ?- X=1,r(X). r1
X = 1 ? i p1r2
X = 1 ? i a1b1r3 X = 1 ? i no
j ?- X=0,r(X). r1
X = 0 ? i p1r2
X = 0 ? i a1a2p3r2 X = 0 ? i r3
X = 0 ? i
r(X)i-write(rl).
r(X)i-p(X),write(r2).
r(X)i-write(rB).
pCX)i-write(pl). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). pCX)i-write(pB).
a(X)i-write(al). a(X)i-write(a2).
b(X)i- X > G, write(bl). b(X)i- X < G, write(b2).
c(X)i- X mod 2 =i= G, write(cl). c(X)i- X mod B =i= G, write(c2).
d(X)i- abs(X) < 1G, write(dl). d(X)i- write(d2).
j ľ- X=l,r(X). rl
X = 1 ľ i plr2
X = 1 ľ i alblrB X = 1 ľ i no
j ľ- X=G,r(X). rl
X = G ľ i plr2
X = G ľ i ala2pBr2 X = G ľ i rB
X = G ľ i no
r(X):-write(r1).
r(X):-p(X),write(r2).
r(X)i-write(rB).
p(X)i-write(p1). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). pCX)i-write(pB).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > G, write(b1). b(X)i- X < G, write(b2).
c(X)i- X mod 2 =i= G, write(d). c(X)i- X mod B =:= G, write(c2).
d(X)i- abs(X) < 1G, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ i p1r2
j ľ- X=B,r(X).
X = 1 ľ i a1b1rB X = 1 ľ i no
j ľ- X=G,r(X). r1
X = G ľ i p1r2
X = G ľ i a1a2pBr2 X = G ľ i rB
X = G ľ i no
r(X)i-write(r1).
r(X)i-p(X),write(r2).
rCX^-writeCrS).
p(X)i-write(p1). p(X)i-aCX),b(X),i,
c(X),d(X),write(p2). pCX^-writeCpS).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > G, write(b1). b(X)i- X < G, write(b2).
c(X)i- X mod 2 =i= G, write(c1). c(X)i- X mod S =i= G, write(c2).
d(X)i- abs(X) < 1G, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ i p1r2
j ľ- X=3,r(X).
X = 1 ľ i
r1
a1b1rS
X = S ľ i
X = 1 ľ i no
j ľ- X=G,r(X). r1
X = G ľ i p1r2
X = G ľ i a1a2pSr2 X = G ľ i rS
X = G ľ i no
r(X)i-write(rl). r(X)i-p(X),write(r2).
r(X)i-writeCrB).
pCX)i-write(pl). pCX)i-aCX),bCX),i,
c(X),d(X),write(p2).
pCX)i-write(pB).
a(X)i-writeCal). a(X)i-writeCa2).
b(X)i- X > G, write(bl). b(X)i- X < G, write(b2).
c(X)i- X mod 2 =i= G, write(cl). c(X)i- X mod B =i= G, write(c2).
d(X)i- abs(X) < 1G, write(dl). d(X)i- write(d2).
j ľ- X=l,rCX). rl
X = 1 ľ i plr2
X = 1 ľ i alblrB X = 1 ľ i no
j ľ- X=G,r(X). rl
X = G ľ i plr2
X = G ľ i ala2pBr2 X = G ľ i rB
X = G ľ i no
j ľ- X=B,r(X).
rl
X=Bľi plr2
X=Bľi
r(X)i-write(r1).
r(X):-p(X),write(r2).
r(X)i-write(r3).
p(X)i-write(p1). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). p(X)i-write(p3).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > O, write(b1). b(X)i- X < O, write(b2).
c(X)i- X mod 2 =i= O, write(c1). c(X)i- X mod 3 =:= O, write(c2).
d(X)i- abs(X) < 1O, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ ; p1r2
j ľ- X=3,r(X).
X = 1 ľ ;
r1
a1b1r3
X = 3 ľ ;
X = 1 ľ ;
p1r2
no
X = 3 ľ ; a1b1c2d1p2r2
j ľ- X=O,r(X).
X = 3 ľ ;
r1
X = O ľ ; p1r2
X = O ľ ; a1a2p3r2 X = O ľ ; r3
X = O ľ ; no
r(X)i-write(r1).
r(X)i-p(X),write(r2).
r(X)i-write(r3).
p(X)i-write(p1). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). p(X)i-write(p3).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2).
c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod 3 =i= 0, write(c2).
d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ i p1r2
j ľ- X=3,r(X).
X = 1 ľ i
r1
a1b1r3
X = 3 ľ i
X = 1 ľ i
p1r2
no
X = 3 ľ i a1b1c2d1p2r2
j ľ- X=0,r(X).
X = 3 ľ i
r1
d2p2r2
X = 0 ľ i
X = 3 ľ i
p1r2
X = 0 ľ i a1a2p3r2 X = 0 ľ i r3
X = 0 ľ i no
r(X)i-write(r1).
r(X)i-p(X),write(r2).
r(X)i-write(r3).
p(X)i-write(p1). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). p(X)i-write(p3).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2).
c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod 3 =i= 0, write(c2).
d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ i p1r2
j ľ- X=3,r(X).
X = 1 ľ i
r1
a1b1r3
X = 3 ľ i
X = 1 ľ i
p1r2
no
X = 3 ľ i a1b1c2d1p2r2
j ľ- X=0,r(X).
X = 3 ľ i
r1
d2p2r2
X = 0 ľ i
X = 3 ľ i
p1r2
r3
X = 0 ľ i
X = 3 ľ i
a1a2p3r2 X = 0 ľ i r3
X = 0 ľ i no
r(X):-write(r1).
r(X):-p(X),write(r2).
r(X):-write(r3).
p(X):-write(p1). p(X):-a(X),b(X),!,
c(X),d(X),write(p2). p(X):-write(p3).
a(X):-write(a1). a(X):-write(a2).
b(X):- X > 0, write(b1). b(X):- X < 0, write(b2).
c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2).
d(X):- abs(X) < 10, write(d1). d(X):- write(d2).
j ?- X=1,r(X). r1
X = 1 ? i p1r2
X = 1 ? i a1b1r3 X = 1 ? i no
j ?- X=0,r(X). r1
X = 0 ? i p1r2
X = 0 ? i a1a2p3r2 X = 0 ? i r3
X = 0 ? i no
j ?- X=3,r(X).
r1
X = 3 ? i
p1r2
X = 3 ? i
a1b1c2d1p2r2
X = 3 ? i
d2p2r2
X = 3 ? i
r3
X = 3 ? i no
r(X)i-write(rl).
r(X)i-p(X),write(r2).
r(X)i-write(rB).
pCX)i-write(pl). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). pCX)i-write(pB).
a(X)i-write(al). a(X)i-write(a2).
b(X)i- X > G, write(bl). b(X)i- X < G, write(b2).
c(X)i- X mod 2 =i= G, write(cl). c(X)i- X mod B =i= G, write(c2).
d(X)i- abs(X) < 1G, write(dl). d(X)i- write(d2).
j ľ- X=l,r(X). rl
X = 1 ľ i plr2
X = 1 ľ i alblrB X = 1 ľ i no
j ľ- X=G,r(X). rl
X = G ľ i plr2
X = G ľ i ala2pBr2 X = G ľ i rB
X = G ľ i no
j ľ- X= -6, r(X).
j ľ- X=B,r(X).
rl
X=Bľi plr2
X=Bľi
alblc2dlp2r2
X=Bľi
d2p2r2
X=Bľi
rB
X=Bľi
no
r(X)i-write(r1).
r(X)i-p(X),write(r2).
rCX^-writeCrS).
p(X)i-write(p1). p(X)i-aCX),b(X),i,
c(X),d(X),write(p2). pCX^-writeCpS).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > G, write(b1). b(X)i- X < G, write(b2).
c(X)i- X mod 2 =i= G, write(c1). c(X)i- X mod S =i= G, write(c2).
d(X)i- abs(X) < 1G, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ i p1r2
X = 1 ľ i a1b1rS X = 1 ľ i no
j ľ- X=G,r(X). r1
X = G ľ i p1r2
X = G ľ i a1a2pSr2 X = G ľ i rS
X = G ľ i no
j ľ- X=3,r(X).
r1
X=Sľi p1r2
X=Sľi
a1b1c2d1p2r2
X=Sľi
d2p2r2
X=Sľi
rS
X=Sľi
no
j ľ- X= -6, r(X).
r1
X = -6 ľ i
r(X):-write(r1).
r(X):-p(X),write(r2).
r(X)i-write(rB).
p(X)i-write(p1). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). pCX)i-write(pB).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > G, write(b1). b(X)i- X < G, write(b2).
c(X)i- X mod 2 =i= G, write(d). c(X)i- X mod B =:= G, write(c2).
d(X)i- abs(X) < 1G, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ i p1r2
X = 1 ľ i a1b1rB X = 1 ľ i no
j ľ- X=G,r(X). r1
X = G ľ i p1r2
X = G ľ i a1a2pBr2 X = G ľ i rB
X = G ľ i no
j ľ- X=B,r(X).
r1
X = B ľ i
p1r2
X = B ľ i
a1b1c2d1p2r2
X = B ľ i
d2p2r2
X = B ľ i
rB
X = B ľ i no
j ľ- X= -6, r(X).
r1
X = -6 ľ i
p1r2
X = -6 ľ i
r(X)i-write(r1).
r(X):-p(X),write(r2).
r(X)i-write(r3).
p(X)i-write(p1). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). p(X)i-write(p3).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > O, write(b1). b(X)i- X < O, write(b2).
c(X)i- X mod 2 =i= O, write(c1). c(X)i- X mod 3 =:= O, write(c2).
d(X)i- abs(X) < 1O, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ ; p1r2
X = 1 ľ ; a1b1r3 X = 1 ľ ; no
j ľ- X=O,r(X). r1
X = O ľ ; p1r2
X = O ľ ; a1a2p3r2 X = O ľ ; r3
X = O ľ ; no
j ľ- X=3,r(X).
r1
X=3ľ; p1r2
X=3ľ;
a1b1c2d1p2r2
X=3ľ;
d2p2r2
X=3ľ;
r3
X=3ľ;
no
j ľ- X= -G, r(X).
r1
X = -G ľ ;
p1r2
X = -G ľ ;
a1b2c1d1p2r2
X = -G ľ ;
r(X)i-write(r1).
r(X)i-p(X),write(r2).
r(X)i-write(r3).
p(X)i-write(p1). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). p(X)i-write(p3).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2).
c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod 3 =i= 0, write(c2).
d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ i p1r2
X = 1 ľ i a1b1r3 X = 1 ľ i no
j ľ- X=0,r(X). r1
X = 0 ľ i p1r2
X = 0 ľ i a1a2p3r2 X = 0 ľ i r3
X = 0 ľ i no
j ľ- X=3,r(X).
r1
X=3ľi p1r2
X=3ľi
a1b1c2d1p2r2
X=3ľi
d2p2r2
X=3ľi
r3
X=3ľi
no
j ľ- X= -6, r(X).
r1
X = -6 ľ i
p1r2
X = -6 ľ i
a1b2c1d1p2r2
X = -6 ľ i
d2p2r2
X = -6 ľ i
r(X)i-write(r1).
r(X)i-p(X),write(r2).
r(X)i-write(r3).
p(X)i-write(p1). p(X)i-a(X),b(X),!,
c(X),d(X),write(p2). p(X)i-write(p3).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2).
c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod 3 =i= 0, write(c2).
d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ i p1r2
X = 1 ľ i a1b1r3 X = 1 ľ i no
j ľ- X=0,r(X). r1
X = 0 ľ i p1r2
X = 0 ľ i a1a2p3r2 X = 0 ľ i r3
X = 0 ľ i no
j ľ- X=3,r(X).
r1
X = 3 ľ i
p1r2
X = 3 ľ i
a1b1c2d1p2r2
X = 3 ľ i
d2p2r2
X = 3 ľ i
r3
X = 3 ľ i no
j ľ- X= -G, r(X).
r1
X = -G ľ i
p1r2
X = -G ľ i
a1b2c1d1p2r2
X = -G ľ i
d2p2r2
X = -G ľ i
c2d1p2r2
X = -G ľ i
r(X)i-write(r1).
r(X)i-p(X),write(r2).
rCX^-writeCrS).
p(X)i-write(p1). p(X)i-aCX),b(X),i,
c(X),d(X),write(p2). pCX^-writeCpS).
a(X)i-write(a1). a(X)i-write(a2).
b(X)i- X > G, write(b1). b(X)i- X < G, write(b2).
c(X)i- X mod 2 =i= G, write(c1). c(X)i- X mod S =i= G, write(c2).
d(X)i- abs(X) < 1G, write(d1). d(X)i- write(d2).
j ľ- X=1,r(X). r1
X = 1 ľ i p1r2
X = 1 ľ i a1b1rS X = 1 ľ i no
j ľ- X=G,r(X). r1
X = G ľ i p1r2
X = G ľ i a1a2pSr2 X = G ľ i rS
X = G ľ i no
j ľ- X=3,r(X).
r1
X=Sľi p1r2
X=Sľi
a1b1c2d1p2r2
X=Sľi
d2p2r2
X=Sľi
rS
X=Sľi
no
j ľ- X= -6, r(X).
r1
X = -6 ľ i
p1r2
X = -6 ľ i
a1b2c1d1p2r2
X = -6 ľ i
d2p2r2
X = -6 ľ i
c2d1p2r2
X = -6 ľ i
d2p2r2
X = -6 ľ i
r(X):-write(rl).
r(X):-p(X),write(r2).
r(X):-write(rB).
p(X):-write(pl). p(X):-a(X),b(X),!,
c(X),d(X),write(p2). p(X):-write(pB).
a(X):-write(al). a(X):-write(a2).
b(X):- X > G, write(bl). b(X):- X < G, write(b2).
c(X):- X mod 2 =:= G, write(cl). c(X):- X mod B =:= G, write(c2).
d(X):- abs(X) < 1G, write(dl). d(X):- write(d2).
j ľ- X=l,r(X). rl
X = 1 ľ i plr2
X = 1 ľ i alblrB X = 1 ľ i no
j ľ- X=G,r(X). rl
X = G ľ i plr2
X = G ľ i ala2pBr2 X = G ľ i rB
X = G ľ i no
j ľ- X=B,r(X).
rl
X=Bľi plr2
X=Bľi
alblc2dlp2r2
X=Bľi
d2p2r2
X=Bľi
rB
X=Bľi
no
j ľ- X= -G, r(X).
rl
X = -G ľ i
plr2
X = -G ľ i
alb2cldlp2r2
X = -G ľ i
d2p2r2
X = -G ľ i
c2dlp2r2
X = -G ľ i
d2p2r2
X = -G ľ i
rB
X = -G ľ i
r(X):-write(r1).
r(X):-p(X),write(r2).
r(X):-write(r3).
p(X):-write(p1). p(X):-a(X),b(X),l,
c(X),d(X),write(p2). p(X):-write(p3).
a(X):-write(a1). 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,r(X). r1
X = 1 ? ; p1r2
X = 1 ? ; a1b1r3 X = 1 ? ; no
| ?- X=0,r(X). r1
X = 0 ? ; p1r2
X = 0 ? ; a1a2p3r2 X = 0 ? ; r3
X = 0 ? ; no
| ?- X=3,r(X).
r1
X=3?; p1r2
X=3?;
a1b1c2d1p2r2
X=3?;
d2p2r2
X=3?;
r3
X=3?;
no
| ?- X= -6, r(X).
r1
X = -6 ? ;
p1r2
X = -6 ? ;
a1b2c1d1p2r2
X = -6 ? ;
d2p2r2
X = -6 ? ;
c2d1p2r2
X = -6 ? ;
d2p2r2
X = -6 ? ;
r3
X = -6 ? ; no
Hana Rudová, Logické programování I, 18. b rezna 2011
10
Seznamy, rez
Řez: maximum
Je tato definice predikátu max/3 korektní?
max(X,Y,X):-X>=Y,l. max(X,Y,Y).
Hana Rudová, Logické programování I, 18. b rezna 2011
11
Seznamy, rez
Rez: maximum
Je tato definice predikátu max/3 korektní?
max(X,Y,X):-X>=Y,l. max(X,Y,Y).
Není, následující dotaz uspeje: ?- max(2,1,1).
Uved'te dve možnosti opravy, se zachováním použití r ezu a bez.
Hana Rudová, Logické programování I, 18. b rezna 2011
11
Seznamy, rez
Ř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 uspeje: ?- max(2,1,1).
Uved'te dve možnosti opravy, se zachováním použití r 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
Pr i použití r ezu je tr eba striktne oddelit vstupní podmínky od výstupních unifikací a výpoctu.
Hana Rudová, Logické programování I, 18. b rezna 2011
11
Seznamy, rez
Ř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 r . pomocí member( X, [1,2,3] ).
mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(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, 18. b rezna 2011
12
Seznamy, rez
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 napr. pomocí member( X, [1,2,3] ).
mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(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, pri porovnávání hledaného prvku s prvky seznamu muže dojít k vázání promenných (může sloužit ke generování všech prvků seznamu)
Hana Rudová, Logické programování I, 18. března 2011
12
Seznamy, rez
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 r . pomocí member( X, [1,2,3] ).
mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(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 r i porovnávání hledaného prvku s prvky seznamu muže dojít k vázání promenných (může sloužit ke generování všech prvků seznamu)
-í* mem2/2 najde jenom první výskyt, taky váže promenné
Hana Rudová, Logické programování I, 18. b rezna 2011
12
Seznamy, rez
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 napr. pomocí member( X, [1,2,3] ).
mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(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).
& mem1/2 vyhledá všechny výskyty, pri porovnávání hledaného prvku s prvky seznamu muže dojít k vázání promenných (může sloužit ke generování všech prvků seznamu)
-í* mem2/2 najde jenom první výskyt, taky váže promenné
-i* mem3/2 najde jenom první výskyt, promenné neváže (hledá pouze identické prvky)
Dokážete napsat variantu, která hledá jenom identické prvky a pritom najde všechny výskyty?
Hana Rudová, Logické programování I, 18. března 2011 12 Seznamy, rez
Rez: member
Jaký je rozdíl mezi následujícími definicemi predikátu member/2. Ve kterých odpovedích se budou lišit? Vyzkoušejte nap r . pomocí member( X, [1,2,3] ).
mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(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).
& mem1/2 vyhledá všechny výskyty, p r i porovnávání hledaného prvku s prvky seznamu muže dojít k vázání promenných (může sloužit ke generování všech prvků seznamu)
-í* mem2/2 najde jenom první výskyt, taky váže promenné
& mem3/2 najde jenom první výskyt, promenné neváže (hledá pouze identické prvky)
Dokážete napsat variantu, která hledá jenom identické prvky
a p r itom najde všechny výskyty?      mem4(H,[K|_]) :- H==K.  mem4(H,[K|T]):- mem4(H,T).
Hana Rudová, Logické programování I, 18. b rezna 2011 12 Seznamy, rez
Řez: delete
delete( X, [X|S], S ).
delete( X,  [Y|S],  [Y|S1] ) :- delete(X,S,S1).
Napište predikát delete(X,S,S1), který odstraní všechny výskyty X (pokud se X v S nevyskytuje, tak predikát uspeje).
Hana Rudová, Logické programování I, 18. brezna 2011
13
Seznamy, rez
Řez: delete
delete( X,  [X|S], S ).
delete( X,  [Y|S],  [Y|S1] ) :- delete(X,S,S1).
Napište predikát delete(X,S,S1), který odstraní všechny výskyty X (pokud se X v S nevyskytuje, tak predikát uspeje).
delete( _X, [], [] ).
delete( X,  [X|S], S1 ) :- !, delete(X,S,S1). delete( X,  [Y|S],  [Y|S1] ) :- delete(X,S,S1).
Hana Rudová, Logické programování I, 18. b rezna 2011
13
Seznamy, rez
Seznamy: intersection(A,B,C)
DÚ: Napište predikát pro výpocet průniku dvou seznamu. Nápoveda: využijte predikát member/2
DÚ: Napište predikát pro výpoctu rozdílu dvou seznamu. Nápoveda: využijte predikát member/2
Hana Rudová, Logické programování I, 18. b rezna 2011
14
Seznamy, rez