Seznamy
Reprezentace seznamu
Seznam: [a, b, c], prázdný seznam []
Hlava (libovolný objekt), tělo (seznam): . (Hlava, Telo)
3 všechny strukturované objekty stromy - i seznamy
3 funktordva argumenty
M .(a,  .(b,  .(c, []))) = [a, b, c]
M notace: [ Hlava | Telo ] = [a | Tel o]
Hana Rudová, Logické programování I, 9. března 201 2
2
Seznamy
Reprezentace seznamu
Seznam: [a, b, c], prázdný seznam []
Hlava (libovolný objekt), tělo (seznam): . (Hlava, Telo)
3 všechny strukturované objekty stromy - i seznamy
3 funktordva argumenty
M .(a,  .(b,  .(c, []))) = [a, b, c]
M notace: [ Hlava | Telo ] = [a | Tel o]
Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ]
Hana Rudová, Logické programování I, 9. března 201 2
2
Seznamy
Reprezentace seznamu
Seznam: [a, b, c], prázdný seznam []
Hlava (libovolný objekt), tělo (seznam): . (Hlava, Telo)
3 všechny strukturované objekty stromy - i seznamy
3 funktordva argumenty
M .(a,  .(b,  .(c, []))) = [a, b, c]
M 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 "|" je seznam zbývajících prvků 3 [a.b.c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]]
Hana Rudová, Logické programování I, 9. března 201 2
2
Seznamy
Reprezentace seznamu
Seznam: [a, b, c], prázdný seznam []
Hlava (libovolný objekt), tělo (seznam): . (Hlava, Telo)
3 všechny strukturované objekty stromy - i seznamy
3 funktordva argumenty
M .(a,  .(b,  .(c, []))) = [a, b, c]
3 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 "|" je seznam zbývajících prvků 3 [a.b.c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] 3 pozor: [ [a,b]  I  [c] ] ^ [ a,b |  [c] ]
Hana Rudová, Logické programování I, 9. března 201 2
2
Reprezentace seznamu
Seznam: [a, b, c], prázdný seznam []
Hlava (libovolný objekt), tělo (seznam): . (Hlava, Telo)
3 všechny strukturované objekty stromy - i seznamy
3 funktordva argumenty
M .(a,  .(b,  .(c, []))) = [a, b, c]
3 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 "|" je seznam zbývajících prvků 3 [a.b.c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] 3 pozor: [ [a,b]  I  [c] ] ^ [ a,b |  [c] ]
M 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, 9. března 201 2 2
Prvek seznamu
member( X, S ) platí: member( b,  [a,b,c] ). 3 neplatí: member( b,  [[a,b]|[c]] ). X je prvek seznamu S, když
X je hlava seznamu S nebo
memberC X,  [ X | _ ] ). %(1)
X je prvek těla seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
Hana Rudová, Logické programování I, 9. března 201 2
3
Prvek seznamu
member(1 ,[2,1,3,1,4])
memberC X, S ) platí: memberC b,  [a,b,c] ). 3 neplatí: memberC b,  [[a,b]|[c]] ). X je prvek seznamu S, když
X je hlava seznamu S nebo
memberC X, [ X | _ ] ). %CD
X je prvek těla seznamu S
memberC X,  [ _ | Telo ] ) :-
memberC X, Telo ). %C2)
Hana Rudová, Logické programování I, 9. března 201 2
3
Seznamy
Prvek seznamu
memberC X, S )
platí: member( b,  [a,b,c] ). neplatí: member( b,  [[a,b]|[c]] ). X je prvek seznamu S, když
X je hlava seznamu S nebo
memberC X,  [ X | _ ] ). %(1)
X je prvek těla seznamu S
memberC X,  [ _ | Telo ] ) :-
memberC X, Telo ). %C2)
member(1,[2,1,3,1,4])
dle (2)
member(1,[1,3,1,4])
Hana Rudová, Logické programování I, 9. března 201 2
3
Seznamy
Prvek seznamu
memberC X, S )
platí: member( b,  [a,b,c] ). neplatí: member( b,  [[a,b]|[c]] ). X je prvek seznamu S, když
X je hlava seznamu S nebo
memberC X,  [ X | _ ] ). %(1)
X je prvek těla seznamu S
memberC X,  [ _ | Telo ] ) :-
memberC X, Telo ). %C2)
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])
Hana Rudová, Logické programování I, 9. března 201 2
3
Seznamy
Prvek seznamu
member( X, S )
platí: member( b,  [a,b,c] ). neplatí: member( b,  [[a,b]|[c]] ). X je prvek seznamu S, když
X je hlava seznamu S nebo
memberC X,  [ X | _ ] ). %(1)
^ X je prvek těla seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
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])
Hana Rudová, Logické programování I, 9. března 201 2
3
Seznamy
Prvek seznamu
member( X, S )
platí: member( b,  [a,b,c] ). neplatí: member( b,  [[a,b]|[c]] ). X je prvek seznamu S, když
X je hlava seznamu S nebo
memberC X,  [ X | _ ] ). %(1)
^ X je prvek těla seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
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])
Hana Rudová, Logické programování I, 9. března 201 2
3
Seznamy
Prvek seznamu
memberC X, S )
platí: memberC b, [a,b,c] ). neplatí: memberC b,  [[a,b]|[c]] ). X je prvek seznamu S, když M X je hlava seznamu S nebo
memberC X, [ X | _ ] ). %CD 3 X je prvek těla seznamu S
memberC X,  [ _ | Telo ] ) :-
memberC X, Telo ). %C2)
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,[351,4])
dle (2) member(1,[1,4])
dle (2) member(1 ,[4])
dle (2) member(1,[ ])
Hana Rudová, Logické programování I, 9. března 201 2
Seznamy
Prvek seznamu
memberC X, S )
platí: member( b, [a,b,c] ). neplatí: member( b,  [[a,b]|[c]] ). X je prvek seznamu S, když
X je hlava seznamu S nebo
memberC X,  [ X | _ ] ). %(1)
«• X je prvek těla seznamu S
memberC X,  [ _ | Telo ] ) :-
memberC X, Telo ). %C2)
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,[351,4])
dle (2) member(1,[1,4])
dle (2) member(1 ,[4])
dle (2) member(1,[ ])
dle (2)
Hana Rudová, Logické programování I, 9. března 201 2
no
Seznamy
Prvek seznamu
memberC X, S )
platí: memberC b,  [a,b,c] ). neplatí: memberC b,  [[a,b]|[c]] ). X je prvek seznamu S, když 3 X je hlava seznamu S nebo
memberC X, [ X | _ ] ). %CD
X je prvek těla seznamu S
memberC X,  [ _ | Telo ] ) :-
memberC X, Telo ). %C2)
Příklady použití:
* member(1,[2,1,3]).
member(X,[1,2,3]).
Hana Rudová, Logické programování I, 9. března 201 2
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
Seznamy
Spojení seznamů
M append( LI, L2, L3 )
Platí: append( [a,b],  [c,d],  [a,b,c,d] )
M Neplatí: append( [b,a],  [c,d],  [a,b,c,d] ), append( [a,[b]], [c,d], [a,b,c,d] )
Hana Rudová, Logické programování I, 9. března 201 2
4
Spojení seznamů
M append( LI, L2, L3 )
Platí: append( [a,b],  [c,d],  [a,b,c,d] )
M Neplatí: append( [b,a],  [c,d],  [a,b,c,d] ), append( [a,[b]], [c,d], [a,b,c,d] )
M Definice:
3 pokud je 1. argument prázdný seznam, pak 2. a 3. argument jsou stejné seznamy
append( [], S, S ).
Hana Rudová, Logické programování I, 9. března 201 2
4
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:
3 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 201 2
Cvičení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2, [X|S3] ) :- append( SI, S2, S3). % (2) :- append([l,2],[3,4],A).
Hana Rudová, Logické programování I, 9. března 201 2
5
Seznamy
Cvičení: append/2
appendC [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).     % (2)
:- append([l,2],[3,4],A). I (2) I A=[1|B]
Hana Rudová, Logické programování I, 9. března 201 2
5
Seznamy
Cvičení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).     % (2)
:- append([l,2],[3,4],A). I (2) I A=[1|B]
I
:- append([2],[3,4],B).
Hana Rudová, Logické programování I, 9. března 201 2
5
Seznamy
Cvičení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( 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]
Hana Rudová, Logické programování I, 9. března 201 2
5
Seznamy
Cvičení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( 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] :- append([],[3,4],C)■
Hana Rudová, Logické programování I, 9. března 201 2
5
Seznamy
Cvičení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).     % (2)
:- append([l,2],[3,4],A). I (2) I A=[1|B]
I
:- append([2],[3,4],B). I (2)
| B=[2|C]   => A=[1,2|C] I
:- append([],[3,4],C). I (D
| C=[3,4]    => A=[l,2,3,4],
I
yes
Hana Rudová, Logické programování I, 9. března 201 2
5
Seznamy
Optimalizace posledního volání
M Last Call Optimization (LCO)
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ěť
M 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:
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é
M p( ...):-.. . % žádné rekurzivní voláni v těle klauzule
p( ...):- ... % žádné rekurzivní voláni v těle klauzule
p(...) :- !, p( ... ). % řez zajišťuje determinismus
M Tento typ rekurze lze převést na iteraci
Hana Rudová, Logické programování I, 9. března 201 2
6
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 i s 1 + DelkaO.
Hana Rudová, Logické programování I, 9. března 201 2
7
Seznamy
LCO a akumulátor
M Reformulace rekurzivní procedury, aby umožnila LCO M Výpočet délky seznamu length( Seznam, Délka ) lengthC [] , 0 ).
length( [ H | T ], Délka ) :- length( T, Del kaO ), Délka is 1 + DelkaO.
M Upravená procedura, tak aby umožnila LCO:
% length( Seznam, ZapocitanaDelka, CelkovaDelka ):
% CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam''
Hana Rudová, Logické programování I, 9. března 201 2
7
Seznamy
LCO a akumulátor
M Reformulace rekurzivní procedury, aby umožnila LCO M Výpočet délky seznamu length( Seznam, Délka ) lengthC [] , 0 ).
length( [ H | T ], Délka ) :- length( T, Del kaO ), Délka is 1 + DelkaO.
M Upravená procedura, tak aby umožnila LCO:
% length( Seznam, ZapocitanaDelka, CelkovaDelka ):
length( Seznam, Délka ) :- length( Seznam, 0, Délka ). % pomocný predikát
length ( [H | T ] , A, Délka ) :- AO is A + 1, length ( T, AO, Del ka ).
M Přídavný argument se nazývá akumulátor
CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam
length( [] , Délka, Délka ).
Hana Rudová, Logické programování I, 9. března 201 2
7
Seznamy
max_list s akumulátorem
Výpočet největšího prvku v seznamu max_li st (Seznam, Max)
max_list([X], X).
max_list([X|T], Max) :-max_li st(T,MaxT), ( MaxT >= X,  !, Max = MaxT
Max = X ).
Hana Rudová, Logické programování I, 9. března 201 2
8
Seznamy
max_list s akumulátorem
Výpočet největšího prvku v seznamu max_li st (Seznam, Max)
max_list([X], X).
max_list([X|T], Max) :-max_li st(T,MaxT), ( MaxT >= X,  !, Max = MaxT
Max = X ).
max_list([H|T],Max) :- max_li st(T,H,Max).
max_list([], Max, Max). max_list([H|T], CastecnyMax, Max) :-C H > CastecnyMax,  !, max_list(T, H, Max )
max_list(T, CastecnyMax, Max) ).
Hana Rudová, Logické programování I, 9. března 2012 8 Seznamy
Akumulátor jako seznam
M Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam )
3 reverse( [] ,  [] ).
reverse( [ H | T ], Opacny ) :-
Hana Rudová, Logické programování I, 9. března 201 2
9
Seznamy
Akumulátor jako seznam
Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam )
3 reverse( [] ,  [] ).
reverse( [ H | T ], Opacny ) :-reverse( T, OpacnyT ), append( OpacnyT,  [ H ], Opacny ).
3 naivní reverse s kvadratickou složitosti
Hana Rudová, Logické programování I, 9. března 201 2
9
Seznamy
Akumulátor jako seznam
Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam )
3 reverse( [] ,  [] ).
reverse( [ H | T ], Opacny ) :-reverse( T, OpacnyT ), append( OpacnyT,  [ H ], Opacny ).
M naivní reverse s kvadratickou složitosti M reverse pomocí akumulátoru s lineární složitostí
M % reverse( Seznam, Akumulátor, Opacny ):
%    Opacny obdržíme přidáním prvků ze  Seznam  do Akumulátor v opačném poradi
Hana Rudová, Logické programování I, 9. března 201 2
9
Seznamy
Akumulátor jako seznam
Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam )
* reverse( [] ,  [] ).
reverse( [ H | T ], Opacny ) :-reverse( T, OpacnyT ), append( OpacnyT,  [ H ], Opacny ).
M naivní reverse s kvadratickou složitosti M reverse pomocí akumulátoru s lineární složitostí
M % reverse( 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).
reverse( [], S, S ).
reverse( [ H | T ], A, Opacny) :-
reverse( T, [ H | A ], Opacny ). % přidání H do akumulátoru
Hana Rudová, Logické programování I, 9. března 201 2
9
Seznamy
Akumulátor jako seznam
Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam )
3 reverse( [] ,  [] ).
reverse( [ H | T ], Opacny ) :-reverse( T, OpacnyT ), append( OpacnyT,  [ H ], Opacny ).
M naivní reverse s kvadratickou složitosti M reverse pomocí akumulátoru s lineární složitostí
M % reverse( 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).
reverse( [], S, S ).
reverse( [ H | T ], A, Opacny) :-
reverse( T, [ H | A ], Opacny ). % přidání H do akumulátoru
M 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
reverse/2: cvičení
reverse( Seznam, OpacnySeznam ) :- % (1)
reverse( Seznam,  [], OpacnySeznam).
reverse( [], S, S ). % (2)
reverse( [H | T ], A, Opacny ) :- % (3)
reverse( T,  [ H | A ], Opacny ).
? - reverse([l,2,3],0). reverse([l,2,3],0) —
Hana Rudová, Logické programování I, 9. března 201 2
10
Seznamy
reverse/2: cvičení
reverse( Seznam, OpacnySeznam ) :- % (1)
reverse( Seznam,  [], OpacnySeznam).
reverse( [], S, S ). % (2)
reverse( [H | T ], A, Opacny ) :- % (3)
reverse( T,  [ H | A ], Opacny ).
? - reverse([l,2,3],0). reverse([l,2,3],0) - (1)
reverse([l,2,3],  [], 0) -
Hana Rudová, Logické programování I, 9. března 201 2
10
Seznamy
reverse/2: cvičení
reverse( Seznam, OpacnySeznam ) :- % (1)
reverse( Seznam,  [], OpacnySeznam).
reverse( [], S, S ). % (2)
reverse( [H | T ], A, Opacny ) :- % (3)
reverse( T,  [ H | A ], Opacny ).
? - reverse([l,2,3],0). reverse([l,2,3],0) - (1)
reverse([l,2,3],  [], 0) - (3) reverse([2,3] ,  [1], 0) -
Hana Rudová, Logické programování I, 9. března 201 2
10
Seznamy
reverse/2: cvičení
reverse( Seznam, OpacnySeznam ) :- % (1)
reverse( Seznam,  [], OpacnySeznam).
reverse( [], S, S ). % (2)
reverse( [H | T ], A, Opacny ) :- % (3)
reverse( T,  [ H | A ], Opacny ).
? - reverse([l,2,3],0). reverse([l,2,3],0) - (1)
reverse([l,2,3],  [], 0) - (3)
reverse([2,3] ,  [1], 0) - (3) reverse([3],  [2,1], 0) -
Hana Rudová, Logické programování I, 9. března 201 2
10
Seznamy
reverse/2: cvičení
reverse( Seznam, OpacnySeznam ) :- % (1)
reverse( Seznam,  [], OpacnySeznam).
reverse( [], S, S ). % (2)
reverse( [ H | T ], A, Opacny ) :- % (3)
reverse( T,  [ H | A ], Opacny ).
? - reverse([l,2,3],0). reverse([l,2,3],0) - (1)
reverse([l,2,3],  [], 0) - (3)
reverse([2,3] ,  [1], 0) - (3) reverse([3],  [2,1], 0) - (3) reverse([],  [3,2,1], 0) -
Hana Rudová, Logické programování I, 9. března 201 2
10
Seznamy
reverse/2: cvičení
reverse( Seznam, OpacnySeznam ) :- % (1)
reverse( Seznam,  [], OpacnySeznam).
reverse( [], S, S ). % (2)
reverse( [H | T ], A, Opacny ) :- % (3)
reverse( T,  [ H | A ], Opacny ).
? - reverse([l,2,3],0). reverse([l,2,3],0) - (1)
reverse([l,2,3],  [], 0) - (3)
reverse([2,3] ,  [1], 0) - (3) reverse([3],  [2,1], 0) - (3)
reverse([],  [3,2,1], 0) - (2) yes 0=[3,2,1]
Hana Rudová, Logické programování I, 9. března 201 2
10
Seznamy
Neefektivita při spojování seznamů
M Sjednocení dvou seznamů
M append( [], S, S ).
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3 ).
Hana Rudová, Logické programování I, 9. března 201 2
Neefektivita při spojování seznamů
M Sjednocení dvou seznamů
M append( [], S, S ).
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3 ).
?- append( [2,3],  [1], S ).
Hana Rudová, Logické programování I, 9. března 201 2
Seznamy
Neefektivita při spojování seznamů
Sjednocení dvou seznamů
M append( [], S, S ).
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3 ).
3 ?- append( [2,3],  [1], S ). postupné volání cílů:
append( [2,3], [1], S ) - append( [3], [1], S') - append( [], [1], S" )
Hana Rudová, Logické programování I, 9. března 2012
Seznamy
Neefektivita při spojování seznamů
«• Sjednocení dvou seznamů append( [], S, S ).
append( [X|S1], S2,  [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ždy je nutné projít celý první seznam
Hana Rudová, Logické programování I, 9. března 201 2
Seznamy
Rozdílové seznamy
Zapamatování konce a připojení na konec: rozdílové seznamy
Hana Rudová, Logické programování I, 9. března 201 2
12
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
Hana Rudová, Logické programování I, 9. března 201 2
12
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
v v		l
L1	L2	\
^-^ L3		
append( Al-Zl, Z1-Z2, A1-Z2 ) LI        L2 L3
Hana Rudová, Logické programování I, 9. března 201 2
12
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
v v		l
L1	L2	\
^-^ L3		
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
Hana Rudová, Logické programování I, 9. března 201 2
12
Seznamy
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
v v		l
L1	L2	\
^-^ L3		
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
?- append( [2,3|Z1]-Z1, [1|Z2]-Z2, S ). S =
Hana Rudová, Logické programování I, 9. března 201 2
12
Seznamy
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
v v		l
L1	L2	\
^-^ L3		
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
?- append( [2,3|Z1]-Z1, [1|Z2]-Z2, S ). S = AI - Z2 =
Hana Rudová, Logické programování I, 9. března 201 2
12
Seznamy
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
v v		l
L1	L2	\
^-^ L3		
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
?- append( [2,3|Z1]-Z1, [1|Z2]-Z2, S ). S = AI - Z2 =    [2,3|Z1] - Z2 =
Hana Rudová, Logické programování I, 9. března 201 2
12
Seznamy
Kozaiiove seznamy
Zapamatování konce a připojení na konec: rozdílové seznamy M [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
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
^ ?- append( [2,3|Z1]-Z1,  [1|Z2]-Z2, S ).
S = AI - Z2 =    [2,3|Zl] - Z2 = [2,3|   [1|Z2] ] - Z2
A1      Z1 A2
MM
Z2
L1
L2
L3
Hana Rudová, Logické programování I, 9. března 201 2
12
Seznamy
Kozaiiove seznamy
Zapamatování konce a připojení na konec: rozdílové seznamy M [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
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
^ ?- 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
M Jednotková složitost, oblíbená technika ale není tak flexibilní
A1      Z1 A2
MM
Z2
L1
L2
L3
Hana Rudová, Logické programování I, 9. března 201 2
12
Seznamy
Akumulátor vs. rozdílové seznamy: reverse
reverse( [] , [] ) . reverse( [ H | T ], Opacny ) :-reverse( T, OpacnyT ),
append( OpacnyT,  [ H ], Opacny ). kvadratická složitost
reverse( Seznam, Opacny ) :- reverseO( Seznam,  [], Opacny ).
reverseO( [], S, S ).
reverseO( [ H | T ], A, Opacny ) :-
reverseO( T,  [H I A ], Opacny ). akumulátor (lineárni)
Hana Rudová, Logické programování I, 9. března 201 2
Seznamy
Akumulátor vs. rozdílové seznamy: reverse
reverse( [] , [] ) . reverse( [ H | T ], Opacny ) :-reverse( T, OpacnyT ),
append( OpacnyT,  [ H ], Opacny ). kvadratická složitost
reverse( Seznam, Opacny ) :- reverseO( Seznam,  [], Opacny ).
reverseO( [], S, S ).
reverseO( [ H | T ], A, Opacny ) :-
reverseO( T,  [ H | A ], Opacny ). akumulátor (lineárni)
reverse( Seznam, Opacny ) :- reverseO( Seznam, Opacny-[]). reverseO( [], S-S ).
reverseO( [ H | T ], Opacny-OpacnyKonec   ) :- rozdilové seznamy
reverseO( T, Opacny-[ H | OpacnyKonec] ). (lineárni)
Hana Rudová, Logické programování I, 9. března 201 2
Seznamy
Akumulátor vs. rozdílové seznamy: reverse
reverse( [] , [] ) . reverse( [ H | T ], Opacny ) :-reverse( T, OpacnyT ),
append( OpacnyT,  [ H ], Opacny ). kvadratická složitost
reverse( Seznam, Opacny ) :- reverseO( Seznam,  [], Opacny ).
reverseO( [], S, S ).
reverseO( [ H | T ], A, Opacny ) :-
reverseO( T,  [ H | A ], Opacny ). akumulátor (lineárni)
reverse( Seznam, Opacny ) :- reverseO( Seznam, Opacny-[]). reverseO( [], S-S ).
reverseO( [ H | T ], Opacny-OpacnyKonec   ) :- rozdilové seznamy
reverseO( T, Opacny-[ H | OpacnyKonec] ). (lineárni)
Příklad: operace pro manipulaci s frontou
3 test na prázdnost, přidání na konec, odebrání ze začátku
Hana Rudová, Logické programování I, 9. března 201 2
Seznamy
Vestavěné predikáty
Vestavěné predikáty
Predikáty pro řízení běhu programu
M fai 1 , true, ...
M Různé typy rovností
3 unifikace, aritmetická rovnost, ...
M Databázové operace
3 změna programu (programové databáze) za jeho běhu
M Vstup a výstup
M Všechna řešení programu M Testování typu termu
3 proměnná?, konstanta?, struktura?, ...
M Konstrukce a dekompozice termu
M argumenty?, funktor?, ...
Hana Rudová, Logické programování I, 9. března 2012 15 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 201 2
16
Vestavěné predikáty
Příklad: databázové operace
M Caching. odpovědi na dotazy jsou přidány do programové databáze
Hana Rudová, Logické programování I, 9. března 201 2
Vestavěné predikáty
Příklad: databázové operace
Caching: odpovědi na dotazy jsou přidány do programové databáze
M ?- solve( problem, Solution),
asserta( solve( problem, Solution) ).
3 :- dynamic solve/2. % nezbytné při použití v SICStus Prologu
Rudová, Logické programování I, 9. března 2012
Vestavěné predikáty
Příklad: databázové operace
M Caching, odpovědi na dotazy jsou přidány do programové databáze
M ?- solve( problem, Solution),
asserta( solve( problem, Solution) ).
3 :- dynamic solve/2. % nezbytné při použití v SICStus Prologu
3 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 ai 1 .
Hana Rudová, Logické programování I, 9. března 2012 17 Vestavěné predikáty
Příklad: databázové operace
M Caching, odpovědi na dotazy jsou přidány do programové databáze
M ?- solve( problem, Solution),
asserta( solve( problem, Solution) ).
3 :- dynamic solve/2. % nezbytné při použití v SICStus Prologu
3 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 ai 1 .
uloz_trojice( _, _ ) :- !.
Hana Rudová, Logické programování I, 9. března 2012 17 Vestavěné predikáty