Seznamy
-=-=-=-=-
A language that doesn't affect the way you think about programming is
not worth knowing.
Jak to tak už u neprocedurálních jazyků bývá, seznamy hrají
v prologu důležitou roli. Prolog reprezentuje seznamy pomocí
funktoru tečka a prázdného seznamu - []. Má ale i zjednodušený zápis
pomocí hranatých závorek:
[1,2,3,4] je to samé jako .(1,.(2,.(3,.(4,'[]'))))
.
/ \
1 .
/ \
3 .
/ \
4 []
Prolog navíc definuje operátor |, který odřezává hlavu od zbytku
seznamu. Například pokud výraz [X|Y] potřebuje zunifikovat se seznamem
[1,2,3,4,5] výsledek bude X=1, Y=[2,3,4,5]. Je možné odřezávat i víc
prvků apod:
[A,B|X] první dva prvky jsou A,B a zbytek je X (může to být i prázdný
senzam
[A|[B|X]] to samé.
Tedy platí:
[a,b,c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] = [a|[b|[c]]] =
[a|[b|[c|[]]]] = .(a,.(b,.(c,'[]'
Má i mnoho zabudovaných predikátů pro práci se seznamy. Ty
nejzákladnější tu uvedu i s jejich implementací:
member(X,Y) - zjištuje, jestli X je prvkem seznamu Y. V prologu
jde implementovat například takto:
member(X,[X,_]). % X je prvkem seznamu, pokud je na prvním místě
member(X,[_,L]) :- member(X,L). % nebo pokud je prvkem seznamu bez
% prvního prvku
member má samozřejmě i jiné použití. Například:
?- member(X,[1,2,3]).
X = 1 ;
X = 2 ;
X = 3 ;
No
Takto může být použit pro vyhledávání v seznamu.
1 ?- member(a,X).
X = [a|G980] ;
X = [G976,a|G992] ;
X = [G976,G988,a|G1004] ;
X = [G976,G988,G1000,a|G1016] ;
X = [G976,G988,G1000,G1012,a|G1028]
....
a takto může být použit pro generování všech seznamů obsahující
daný prvek. ([a|G980] znamená seznam z prvkem a na prvním místě.
G980 je volná proměná a program ji později může z něčím zunifikovat.
[G976,a|G992] je zase seznam z prvkem a na druhém místě atd...
Další užitečný predikát je append(X,Y,Z), který spojuje seznamy
X a Y do Z.
append([],L,L). % seznam spojený z prázdným seznamem je ten samý seznam
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
% pokud chces spojit dva seznamy, odřízni první prvek,
% potom spoj zbytek a první prvek zase přidej.
Append se opět může použít nejen pro spojování dvou seznamů, ale
také na dělění jednoho seznamu na dvě půlky - append(X,Y,[1,2,3,4]),
nebo odčítání jednoho seznamu od druhého.
Pomocí appendu lze například (neoptimálně) implementovat i member:
member(X,Y) :- append(_,[X|_],L).
Jiný zajímavý predikát je reverse, který otáčí seznam. Jeho
nejjednodušší implementace asi je:
reverse([],[]). %otočený prázdný seznam je prázdný seznam
reverse([X|L],R):- %na otočení seznamu napřed odřízní první prvek
reverse(L,R1), %otoč zbytek
append(R1,[X],R). %a potom první prvek přidej nakonec
Problém ale je, že potom potřebuje N^2 kroků - append pracuje
v lineárním čase narozdíl od přidávání na začátek, které je
jednoduché. To lze obejít pomocí akumulátoru:
reverse(L,R) :- rev1(L,[],R).
rev1([],R,R).
rev1([X|L],A,R) :- rev1(L,[X|A],R).
Tady se napřed zavolá pomocný predikát a akumulátor se snuluje.
Potom se na jeho první pozici přidá první prvek z L. První prvek se
z L odřízne a postup se opakuje. Probíhá to tedy následovně:
X = [1,2,3,4] Acc=[]
X = [2,3,4] Acc=[1]
X = [3,4] Acc=[2,1]
X = [4] Acc=[3,2,1]
X = [] Acc=[4,3,2,1]
Jak vidíte, v akumulátoru se nashromáždí obrácený seznam.
Nakonec je ho ale nutné dostat z rekurze ven. To se udělá tak,
že na konci se akumulátor zunifikuje z proměnou R, která se jinde
neměnila. Dostane se tedy z rekurze ven a výsledek se dostane do R
ve volání z predikátu reverse.
Rozdíl oproti předchozímu je, že se vždy přidávalo na začátek
a nebylo tedy nutné seznam procházet.
Predikát msort zadaný list setřidí. K tomu používá algoritmus
mergesort. Mergesort je jeden z nejvýkonějších a nejznámějších
algoritmů na třídění. Oproti asi nejpoužívanějšímu quicksortu ma
tu výhodu, že jeho nejhorší časová složitost je O(N*log(N)) a tak
v nejhorším případě je výrazně rychlejší než quicksort. V průměrném
případě je rychlost (až na konstantu) stejná.
Algoritmus probíhá tak, že aby setřídil n prvků, je napřed
libovolně rozdělí na dvě části o velikosti n/2. Potom tyto dvě části
stejným způsobem setřidí a nakonec setříděné posloupnosti spojí.
Spojit dve setříděné posloupnosti je jednoduché. Vždy se koukne
na první prvky obou posloupností a vybere ten menší, načež postup
opakuje.
Nejprve je tedy nutné posloupnost rozdělit. To lze implementovat
například takto:
split([],[],[]).
split([X],[X],[]).
split([A,B|X],[A|Y],[B|Z]) :- split(X,Y,Z).
Tato implementace rozděluje seznam podle lichých a sudých prvků.
Potom je nutné posloupnosti opět spojit:
mmerge([],[],[]). %prázdné seznamy se spojují do prázdného
mmerge([X],[],[X]). %jednoprvkový a prázdný seznam se spojuje do
%jednoprvkového
mmerge([],[X],[X]). %prázdný a jednoprvkový
mmerge([A|X],[B|Y],[A|Z]) :- A @< B,mmerge(X,[B|Y],Z).
%pokud je první prvek z prvního seznamu menší
mmerge([A|X],[B|Y],[B|Z]) :- A @>= B,mmerge([A|X],Y,Z).
%pokud je první prvek z prvního seznamu větší
Operátor X @< Y určuje jestli term X je menší, než term Y. Pokud
termy jsou čísla, je to jednoduché. Pokud se jedná o atomy, pořadí
je abecední a pokud jsou to struktury, napřed se porovnají funktory
a potom stejně jednotlivé parametry. Operátor @>= funguje stejně pro
větší, nebo rovno.
A nakonec můžeme napsat vlastní msort:
mmsort([],[]).
mmsort([X],[X]).
mmsort([X1,X2|X],Y) :- split([X1,X2|X],A,B),mmsort(A,C),mmsort(B,D),
mmerge(C,D,Y).
[X1,X2|X] je zde nutné, protože jinak by prolog unifikovat
poslední predikát i z prázdnými a jednoprvkovými seznamy a to je
špatně - dával by několik různých výsledků.
Jak vídíte, prolog se hodí i pro některé algoritmické problémy.
Třídění by samozžejmě šlo popsat deklarativně, ale prolog by pro
hledání setříděné posloupnosti použil nějakou metodu pokusu a omylu
a to by asi nebylo nejlepší. Na druhou stranu by ale asi takový
predikát šel použít i obráceně (na vygenerování všech permutací dané
posloupnosti)
výheň