Prolog - prohledávání, rozdílové seznamy

Většina programů, které jsme zatím v Prologu napsali, se chovala deterministicky, tj. v každém kroku byla jen jedna (rozumná) možnost, co udělat, a tedy jsme se snažili, aby Prolog právě tuto variantu zvolil. V Prologu je ale mnohem běžnější používat prohledávání a programy jsou tedy často nedeterministické - Prolog zkouší různé klauzule z definice procedury dokud nenajde správné řešení.

Prohledávání

Jako příklad nedeterministického programu můžeme vyřešit známý problém loupežníků - vybrat ze seznamu čísla, jejichž součet se rovná zadanému číslu. Jedno z řešení může vypadat například následujícím způsobem.

% vyber(S, N, Z) :- vybere ze seznamu S seznam Z jehoz soucet je presne N
vyber([], N, _):-N>0, fail.
vyber([], 0, []).
vyber([H|T], N, [H|Z]):-N1 is N-H,vyber(T,N1,Z).
vyber([_|T],N,Z):-vyber(T,N,Z).

Poslední dvě klauzule v tomto řešení říkají, že buď první číslo seznamu máme dát (druhá řádka od konce), nebo nemáme (poslední řádka). Prolog tedy napřed zkusí do seznamu číslo dát, a vyřešit nový problém s kratším seznamem a menším číslem, když se to nepovede, selže a zkusí variantu, kde tam číslo nedá.

Program můžeme i zjednodušit. Poslední dvě řádky v sobě vlastně obsahují predikát member. Dají se napsat i pomocí něj, nebo pomocí predikátu select, který funguje podobně, ale kromě samotného prvku ze seznamu vrací i seznam bez tohoto prvku. Druhá varianta řešení tedy může vypadat například takto:

vyber2(X, N, Z):-vyber2(X, N, 0, [], Z).
vyber2(_, N, N, Z, Z).
vyber2(X, N, A, Z, V):-select(P, X, Xs), 
                       B is A + P, 
                       B =< N, 
                       vyber2(Xs, N, B, [P|Z], V).	

Třídění

Pro implementaci quicksortu se hodí procedura, která rozdělí seznam na dva, v jednom nich jsou čísla menší než zvolené číslo, ve druhém větší.

% rozdel(+S, +Pivot, -Mensi, -Vetsi) :- rozdeli S tak, ze v seznamu Mensi jsou
% 	prvky mensi nebo rovny Pivotu a v seznamu vetai jsou prvky vetai nez Pivot

rozdel([], _, [], []).
rozdel([H|T], Pivot, [H|Mensi], Vetsi):-H=<Pivot,rozdel(T,Pivot,Mensi,Vetsi).
rozdel([H|T], Pivot, Mensi, [H|Vetsi]):-H>Pivot,rozdel(T,Pivot,Mensi,Vetsi).

Abychom mohli napsat quicksort, potřebujeme ještě napsat spojení dvou seznamů. To by mělo být jednoduché. (V Prologu je spojení také definované jako procedura append):

% spojeni(?X, ?Y, ?Z) :- do seznamu Z ulozi spojeni seznamu X a Y
spojeni([],X,X).
spojeni([H|T], X, [H|S]):-spojeni(T,X,S).

A teď už máme všechno a můžeme klidně napsat quicksort. T\=[] v poslední klauzuli zajišťuje, že Prolog nebude vracet stejné odpovědi vícekrát, ale není ho tam nutné mít (všechny vrácené odpovědi jsou správné, dalo by se mu vyhnout i tak, že bychom chtěli, aby seznam měl aspoň dva prvky [H1, H2|T]).

% qsort(+X,-Y) :- do seznamu Y ulozi setrideny seznam X
qsort([],[]).
qsort([A],[A]).
qsort([H|T],X):-T\=[],rozdel(T,H,Mensi,Vetsi),
                qsort(Mensi,X1),qsort(Vetsi,X2),
                spojeni(X1,[H|X2],X).

Rozdílové seznamy

Při implementaci quicksortu jsme potřebovali zřetězovat seznamy. Zřetězení seznamů trvá dlouho (lineárně v délce prvního seznamu), v Prologu ale můžeme použít trik, kterému se říká rozdílový seznam. Spojeni rozdílových seznamů potom jde napsat v konstantním čase.

Jak ten trik funguje? Místo použití pouze samostatného seznamu použijeme seznam a volnou proměnnou. Běžně se tyto dvě části oddělují symbolem - (proto se jim asi říká rozdílové seznamy), můžete si je ale klidně oddělit i jinak, případně si nadefinovat vlastní datovou strukturu (binární term).

Rozdílový seznam tedy má dvě části, samotný seznam a volnou proměnnou, např. S-X. Tohle ale samo o sobě nestačí, důležité je, že ta proměnná X je zároveň použita jako konec seznamu S. Takový rozdílový seznam například může vypadat následujícím způsobem [a,b,c|X]-X.

Napsat převod seznamu na rozdílový seznam je snadné (v lineárním čase).

% narozdil(+S,-RS) :- prevadi seznam S na rozdilovy seznam RS
narozdil([],X-X).
narozdil([H|T],[H|S]-X):-narozdil(T,S-X).

Převod z rozdílového seznamu na obyčejný seznam je ještě jednodušší (a dokonce v konstantním čase).

% naobyc(+RS,S):- prevadi rozdilovy seznam RS na obycejny seznam S
naobyc(X-[],X).

Když nyní v rozdílovém seznamu [a,b,c|X]-X unifikujeme X s libovolným seznamem (např. [d,e]), dostaneme [a,b,c,d,e]-[d,e] (v jednom kroku) a vidíte, ze máme spojení seznamu (+ nějaký ocásek navíc). Ještě zajímavější situace by nastala, kdybychom spojili náš původní seznam s rozdílovým seznamem, např. s [d,e|Y]-Y, a dostali bychom [a,b,c,d,e|Y]-Y - tedy zase rozdílový seznam. Takové spojení se ale dá opět napsat velmi snadno:

%spojeniRS(+A,+B,-C):-rozdilovy seznam C je spojeni rozdilovych seznamu A a B
spojeniRS(A-B,B-B1,A-B1).

Poslední úkol pro dnešek (víceméně nesouvisející s předcházejícím) je napsání transpozice matice. Matice je zadaná jako seznam seznamů. Pro transpozici (tuhle implementaci) potřebujeme pomocnou proceduru, která ze seznamu seznamů odebere první prvky a vrátí zbytky.

%vsePrazdne(+SeznamSeznamu):-vsechny seznamy v SeznamSeznamu jsou prazdne
vsePrazdne([]).
vsePrazdne([[]|Z]):-vsePrazdne(Z).

%hlavyZbytky(+SeznamSeznamu, -Hlavy, -Zbytky):-rozdeli vsechny seznamu v SeznamSeznamu na Hlavy a Zbytky
hlavyZbytky([], [], []).
hlavyZbytky([[H|T] | Z], [H|PP], [T|ZB]):-hlavyZbytky(Z, PP, ZB).

%transpozice(+M, -TM):-TM je transpozice matice M
transpozice(M, []):-vsePrazdne(M).
transpozice(M, [H|TM]):-hlavyZbytky(M, H, Z), transpozice(Z, TM).