Reprezentace seznamu
■ Seznam: [a, b, c], prázdný seznam []
■ Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo)
■ všechny strukturované objekty stromy - i seznamy
■ funktordva argumenty
Seznamy, řez ■ .ca, .(b, .cc □))) = [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 ] ]
■ Lze psát i: [a, b | Tel o]
■ před " |" je libovolný počet 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]]r[a,b|  [c] ]
■ Seznam jako neúplná datová struktura: [a,b,c|T]
■ Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S]
Hana Rudova, Logické programování I, 18. března 201 I 2 Seznamy, řez
Cvičení: append/2
appendC [], S, S ).        % CD
appendC [X|S1], S2,  [X|S3] ) :- appendC 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],Q.
I CD
I 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) :- appendC _S1,  [ Pred,X,Po | _S2 ], S)
Hana Rudová, Logické programování I, 18. března 2011 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:
■ prefixC SI, S2 ) :- appendC SI, _S3, S2). DÚ: suffix(Sl,S2)
■ lastC X, S ) :- appendC _S1,  [X], S). appendC[3,2] , [6],  [3,2,6]). X=6, S=[3,2,6]
■ memberC X, S ) :- appendC SI,  [X|S2], S ). appendC3,4,l] ,  [2,6],  [3,4,1,2,6]).       X=2 , S=[3 ,4,1,2 ,6] DÚ: adjacentCX.Y.S)
■ % 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, 18. března 201 1 4 Seznamy, řez
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, kdyje 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é
■ p( ...):- ... % žádné rekurzivní volám' 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í 1,18. března 2011 5 Seznamy, řez
Akumulátor a sum_l i st(S, Sum)
?- sum_list( [2,3,4], Sum ).
bez akumulátoru: sum_list( [], 0 ).
sum_list( [H|T], Sum ) :- sum_list( T, SumT ),
Sum i s H + SumT.
s akumulátorem:
sum_list( S, Sum ) :-   sum_list( S, 0, Sum ).
sum_list( [], Sum, Sum ).
sum_list( [H|T], A, Sum )  :- AI is A + H,
sunuli st( T, AI, Sum).
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 ).
■ Přídavný argument se nazývá akumulátor
Hana Rudová, Logické programování I, 18. března 201 1 6 Seznamy, řez
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, 18. března 2011 7 Seznamy, řez Hana Rudová, Logické programování I, 18. března 201 1
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) ,wn'te(p2) . -write(p3).
-write(al) . -write(a2).
- X > O, write(bl) .
- X < O, write(b2).
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).
X mod 2 X mod 3
abs(X) < 10, write(dl). write(d2).
(2) X=3,r(X). (4) X= -6,r(X).
0, write(cl). 0, write(c2).
Hana Rudová, Logické programování 1,18. března 2011
ř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/1 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)
9 Seznamy, řez
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).
-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
write(cl). write(c2).
abs(X) < 10, write(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
6, rC
I ?- X=3,r(X). rl
X = 3 ? ; plr2
X = 3 ? ;
alblc2dlp2r2
X = 3 ? ;
d2p2r2
X = 3 ? ;
r3
X = 3 ? ; no
I ?- X rl
X = -6 ? ; plr2
X = -6 ? ;
alb2cldlp2r2
X = -6 ? ;
d2p2r2
X = -6 ? ;
c2dlp2r2
X = -6 ? ;
d2p2r2
X = -6 ? ;
r3
X = -6 ? ; no
Hana Rudová, Logické programování I, 18. března 201 1
Ř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í 1,18. března 2011 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)
■ 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í 1,18. března 201 1 12 Seznamy, řez
Řez: delete
deleteC X,  [X|S], S ).
deleteC X,  [Y|S],  [Y|S1] ) :- delete(X,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,  [] ,  [] ) .
deleteC X,  [X|S], SI) :- !, delete(X,S,Sl). deleteC X,  [Y|S],  [Y|S1] ) :- delete(X,S,S1).
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
Hana Rudová, Logické programování 1,18. března 2011 13 Seznamy, řez Hana Rudová, Logické programování 1,18. března 201 1