Reprezentace seznamu
Seznamy, řez
1 Seznam: [a, b, c], prázdný seznam []
1 Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo)
■ všechny strukturované objekty stromy - i seznamy
■ funktordva argumenty
■ .(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 ] ] ' 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] ]
1 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 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:
■ prefix( SI, S2 ) :- appendC SI, _S3, S2). DÚ: suffix(Sl,S2)
■ last( 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 ). appendC[3,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, 23. března 2010 3 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, kdy je možné použití LCO:
■ procedura musí mít pouze jedno rekurzivní volání: v posledním cíli poslední klauzule
■ cíle předcházející tomuto rekurzivnímu volání musí být deterministické
■ pC ...):- ... % žádné rekurzivní voláni v těle klauzule pC •••):- ... % žádné rekurzivní voláni v těle klauzule
pC-..) :- !, pC ■■■ )■ % řez zajišťuje determinismus
■ Tento typ rekurze lze převést na iteraci
Hana Rudová, Logické programování I, 23. března 2010 4 Seznamy, řez
LCO a akumulátor
Akumulátor a sum_l i st (S, Sum)
■ Reformulace rekurzivní procedury, aby umožnila LCO
■ Výpočet délky seznamu length( Seznam, Délka )
lengthC [] , 0 ) .
lengthC [ H | T ], Délka ) :- lengthC T, DelkaO ), Délka is 1 + DelkaO.
■ Upravená procedura, tak aby umožnila LCO:
% lengthC Seznam, ZapocitanaDelka, CelkovaDelka ):
% CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam''
length C Seznam, Délka ) :- length ( Seznam, 0, Délka ). % pomocný predikát
length C [] , Délka, Délka ). % celková délka = započítaná délka
lengthC [ H | T ], A, Délka ) :- AO is A + 1, lengthC T, AO, Délka ).
■ Přídavný argument se nazývá akumulátor
Hana Rudová, Logické programování I, 23. března 2010 5 Seznamy, řez
Výpočet faktoriálu fact(N, F)
s akumulátorem:
fact( 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 Seznamy, řez
?- 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 Seznamy, řez
		Prozkoumejte trasy výpočtu  a navracení
r(X)	-write Crl).	např. pomocí následujících dotazů (vždy si
r(X)	-p(X),write(r2).	
r(X)	-write(r3).	středníkem vyžádejte navracení):
P(X)	-write(pl).	(1) X=l,r(X).          (2) X=3,r(X).
		(3) X=0,r(X).          (4) X= -6,r(X).
P(X)	-a(X),b(X), ! ,	
	c(X),d(X),write(p2) .	■ řez v predikátu p/1 neovlivní alternativy
P(X)	-write(p3).	predikátu r/1
a(X)	-write(al).	■ dokud nebyl proveden řez, alternativy
a(X)	-write(a2).	predikátu a/l se uplatňují, př. neúspěch
b(X)	- X > 0, write(bl).	b/1 v dotazu (3)
b(X)	- X < 0, write(b2).	■ při neúspěchu cíle za řezem se výpočet
c(X)	- X mod 2 =:= 0, write(cl)	navrací až k volající proceduře r/1, viz (1)
c(X)	- X mod 3 =:= 0, write(c2)	
		■ alternativy vzniklé po provedení řezu se
d(X)	- abs(X) < 10, write(dl).	
d(X)	- write(d2).	zachovávají - další možnosti predikátu 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(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).
X mod 2 X mod 3
write(cl) . write(c2).
abs(X) < 10, write(dl). 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
I ?- X=3,r(X). rl
X = 3 ? ; plr2
X = 3 ? ;
alblc2dlp2r2
X = 3 ? ;
d2p2r2
X = 3 ? ;
r3
X = 3 ? ; no
X=
6, rC
I ? rl
X = -6 ? ; plr2
X = -6 ? ;
alb2cldlp2r2
X = -6 ? ;
d2p2r2
X = -6 ? ;
c2dlp2r2
X = -6 ? ;
d2p2r2
X = -6 ? ;
r3
X = -6 ? ; no
Rez: maximum
Je tato definice predikátu max/3 korektní?
max(X,Y,X):-X>=Y,!. max(X,Y,Y).
Není, následující dotaz uspěje: ?- max(2 ,1,1).
Uveďte dvě možnosti opravy, se zachováním použití řezu a bez.
max(X,Y,X):-X>=Y. max(X,Y,Y):-Y>X.
max(X,Y,Z):-X>=Y,!,Z=X. max(X,Y,Y).
Problém byl v definici, v první verzi se tvrdilo: X=Z a X>=Y => Z=X
správná definice je: X>=Y => Z=X
Při použití řezu je třeba striktně oddělit vstupní podmínky od výstupních unifikací a výpočtu.
Hana Rudová, Logické programování I, 23. března 2010
Hana Rudová, Logické programování I, 23. března 2010
Ř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|_]).
memlCH,[_|T]) :- meml(H,T).
mem2(H, [H |_]) :- !. mem3(H, [K|_]) :-H==K.
mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T).
■ meml/2 vyhledá všechny výskyty, při porovnávání hledaného prvku s prvky seznamu může dojít k vázání proměnných (může sloužit ke generování všech prvků seznamu)
■ mem2/2 najde jenom první výskyt, taky váže proměnné
■ mem3/2 najde jenom první výskyt, proměnné neváže (hledá pouze identické prvky)
Řez: delete
deleteC X,  [X|S], S ) .
deleteC X,  [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,  [] ,  [] ) .
deleteC X,  [X|S], SI) :- !, delete(X,S,Sl). deleteC X,  [Y|S],  [Y|S1] ) :- delete(X,S,Sl).
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
Hana Rudová, Logické programování I, 23. března 2010
12
Seznamy, řez
Seznamy: i nte rsecti on (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 2010
13
Seznamy, řez