Reprezentace seznamu
Seznamy
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, 9. března 2012 2
Prvek seznamu
■ member( X, S )
■ platí: member( b,  [a,b,c] ).
■ neplatí: member( b,  [[a,b]|[c]] ).
■ Xje prvek seznamu S, když
■ Xje hlava seznamu S nebo member( X,  [ X | _ ] ). %(1)
■ Xje prvek těla seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
■ Příklady použití:
■ memberCl,[2,1,3]).
■ memberCX,[1,2,3]) .
Hana Rudová, Logické programování I, 9. března 2012 3
dle (1).
□ yes
dle(1).
□ yes
member(1,[2,1,3,1,4])
dle (2) member(1,[1,3,1,4])
dle (2) member(1,[3,1,4])
dle (2) member(1 ,[1,4])
dle (2) member(1 ,[4])
|  dle (2) member(1,[]) dle (2)
no
Spojení seznamů
append( LI, L2, L3 )
Platí: append( [a,b],  [c,d],  [a,b,c,d] )
Neplatí: append( [b,a],  [c,d],  [a,b,c,d] ), append( [a,[b]],  [c,d],  [a,b,c,d] )
Definice:
■ pokud je 1. argument prázdný seznam, pak 2. a 3. argument jsou stejné seznamy: append( [], S, S ).
■ pokud je 1. argument neprázdný seznam, pak má 3. argument stejnou hlavu jako 1.: append( [X|S1], S2,  [X|S3] )  :- append( SI, S2, S3).
X
S1
S2
S3
Hana Rudová, Logické programování I, 9. března 2012
Cvičení: append/2
Optimalizace posledního volání
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]
I
:- append([2],[3,4],B). I (2)
I B=[2|C]   => A=[1,2|C]
I
:- append([],[3,4],Q.
I CD
| C=[3,4]   => A=[l,2,3,4],
I
yes
Hana Rudová, Logické programování I, 9. března 2012 5 Seznamy
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 I 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, 9. března 2012 7 Seznamy
■ 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, 9. března 2012 6 Seznamy
max_list s akumulátorem
Výpočet největšího prvku v seznamu max_"list(Seznam, Max)
max_listC[X], X).
max_listC[X|T], Max) :-max_li st CT,MaxT), C MaxT >= X,  !, Max = MaxT
Max = X ).
max_listC[H|T],Max) :- max_listCT,H,Max).
max_listC[], Max, Max). max_li st C[H|T], CastecnyMax, Max) :-C H > CastecnyMax, !, max_listCT, H, Max )
max_listCT, CastecnyMax, Max) ).
Hana Rudová, Logické programování I, 9. března 2012 8 Seznamy
Akumulátor jako seznam
Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam )
■ reverseC [] ,  [] ) .
reverseC [ H | T ], Opacny ) :-reverseC T, OpacnyT ), appendC OpacnyT,  [ H ], Opacny ).
■ naivní reverse s kvadratickou složitosti
reverse pomocí akumulátoru s lineární složitostí
■% reverseC Seznam, Akumulátor, Opacny ): %    Opacny obdržíme přidáním prvků ze  Seznam do Akumulátor v opačném poradi reverse( Seznam, OpacnySeznam ) :- reverse( Seznam, [], OpacnySeznam).
reversef [], S, S ).
reversef [ H | T ], A, Opacny ) :■
reversef T, [ H | A ], Opacny ). % přidání H do akumulátoru
■ zpětná konstrukce seznamu (srovnej s předchozí dopřednou konstrukcí, např. append)
Hana Rudová, Logické programování I, 9. března 2012 9 Seznamy
Neefektivita při spojování seznamů
Sjednocení dvou seznamů append( [], S, S ).
append( [X|S1], 52,  [X|S3] ) :- append( SI, S2, S3 ).
?- append( [2,3],  [1], S ). postupné volání cílů:
append( [2,3], [1], S ) — append( [3], [1], S') - append( [], [1], S" )
Vždyje nutné projít celý první seznam
Hana Rudová, Logické programování I, 9. března 2012
Seznamy
reverse/2: cvičení
reverseC Seznam, OpacnySeznam ) :- % (1)
reverseC Seznam,  [], OpacnySeznam).
reverseC [], S, S ). % (.2)
reverseC [ H | T ], A, Opacny ) :- % C3)
reverseC T, [ H I A ], Opacny ).
? - reverse([l,2,3],0). reverseC[l,2,3] ,0) - CD
reverseC[1,2,3], □ , 0) - C3)
reverseC[2,3], [1], 0) - C3) reverseC[3], [2,1], 0) - C3)
reverseC[] ,  [3,2,1] , 0) - (2) yes 0=[3,2,1]
Hana Rudová, Logické programování I, 9. března 2012
Seznamy
Rozdílové seznamy
Zapamatování konce a připojení na konec: rozdílové seznamy [a,b] = L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] Reprezentace prázdného seznamu: L-L
A1      Z1 A2
Z2
L1
	1
L2	\
append( Al-Zl, Z1-Z2, A1-Z2 ). LI        L2 L3 [2,3]       [1] [2,3,1] [2,3|Z1]-Z1 [1|Z2]-Z2 [2,3,1|Z2]-Z2
L3
?- append( [2,3|Z1]-Z1,  [1|Z2]-Z2, S ).
S = AI - Z2 =    [2,3|Zl] - Z2 = [2,3|   [1|Z2] ] - Z2
Zl = [1|Z2]        S = [2,3,1|Z2]-Z2
Jednotková složitost, oblíbená technika ale není tak flexibilní
Hana Rudová, Logické programování I, 9. března 2012 12
Seznamy
Akumulátor vs. rozdílové seznamy: reverse
reverseC [] ,  [] ) .
reverseC [ H | T ], Opacny ) :-
reverseC T, OpacnyT ),
appendC OpacnyT,  [ H ], Opacny ).
kvadratická složitost
reverseC Seznam, Opacny ) :- reverseOC Seznam,  [], Opacny ).
reverseOC [] , S, S ) .
reverseOC [ H | T ], A, Opacny ) :-
reverseOC T,  [ H | A ], Opacny ).
akumulátor Oineárni)
reverseC Seznam, Opacny ) :- reverseOC Seznam, Opacny-[]). reverseOC [] , S-S ) .
reverseOC [ H | T ], Opacny-OpacnyKonec   ) :-
reverseOC T, Opacny-[ H | OpacnyKonec] ).
rozdílové seznamy Cl i neárni)
Příklad: operace pro manipulaci s frontou ■ test na prázdnost, přidání na konec, odebrání ze začátku
Hana Rudová, Logické programování I, 9. března 2012 13
Vestavěné predikáty
■ Predikáty pro řízení běhu programu
■ fail, true,...
■ Různé typy rovností
■ unifikace, aritmetická rovnost, ...
■ Databázové operace
■ změna programu (programové databáze) za jeho běhu
■ Vstup a výstup
■ Všechna řešení programu
■ Testování typu termu
■ proměnná?, konstanta?, struktura?, ...
■ Konstrukce a dekompozice termu
■ argumenty?, funktor?, ...
Hana Rudová, Logické programování I, 9. března 201 2 15
Vestavěné predikáty
Vestavěné predikáty
Databázové operace
Databáze: specifikace množiny relací
Prologovský program: programová databáze, kde jsou relace specifikovány explicitně (fakty) i implicitně (pravidly)
Vestavěné predikáty pro změnu databáze během provádění programu:
assert( Klauzule )       přidání  Klauzule do programu asserta( Klauzule )      přidání na začátek assertz( Klauzule )      přidání na konec
retract( Klauzule ) smazání klauzule unifikovatelné s Klauzule Pozor: nadměrné použití těchto operací snižuje srozumitelnost programu
Hana Rudová, Logické programování I, 9. března 2012
Vestavěné predikáty
Príklad: databázové operace
■ Caching odpovědi na dotazyjsou přidány do programové databáze
■ ?- solve( problem, Solution),
asserta( solve( problem, Solution) ).
■ :- dynamic solve/2. % nezbytné při použití v SICStus Prologu
■ Příklad:
uloz_trojice( Seznámí, Seznam2 ) :-member( XI, Seznámí ), member( X2, Seznam2 ), spocitej_treti( XI, X2, X3 ), assertz( trojice( XI, X2, X3 ) ), f a i 1.
uloz_trojice( _, _ ) :- !.
Hana Rudová, Logické programování I, 9. března 201 2
17
Vestavěné predikáty