Programowanie w Prologu, część 2
W poprzednim wpisie zademonstrowałem podstawy języka Prolog, dziś chciałbym kontynuować ten temat. Wiedza zademonstrowana niemalże miesiąc temu nie pozwala na zbyt wiele, jednak dzisiaj przedstawię coś, co umożliwi tworzenie wielu ciekawych programów. Tym czymś są...
Listy
Lista w prologu pozwala reprezentować dane w kolejności, co umożliwia nam przykładowo (trzymając się konwencji z poprzedniego wpisu) zbudowanie listy wszystkich przesiadek, które będziemy musieli uskutecznić by dostać się z miasta A do miasta B. Listy prologowe zapisujemy w nawiasach kwadratowych, a elementy wymieniamy po przecinku.
[wrocław,kraków,poznań]
Jak widać jest to dość mocno intuicyjne. Należy nadmienić, że elementy listy nie są numerowane, więc nie możemy odwołać się do elementu numer 2 na liście, tak jak to bywa w typach tablicowych (i często listowych) innych języków. Rozwiązaniem jest tutaj zapis typu (przypomnienie - wielkie litery oznaczają zmienne):
[H|T]
Czytamy to "głowa H i ogon T", a oznacza to, że H jest pierwszym elementem listy, a T jest całą resztą. W tym przypadku:
[wroclaw,krakow,poznan]
[code=Prolog]H = wroclaw, T=[krakow,poznan][/code]
Jak widać uzyskaliśmy dostęp do pierwszego elementu. Jak więc uzyskać dostęp do 2?
Drugi element listy trójelementowej (A) to pierwszy element listy pozostałej(B) po odcięciu pierwszego elementu tej listy(A)
Nieco zawiłe, więc jeśli nie zrozumiałeś zatrzymaj się chwilę i prześledź to wzrokiem jeszcze raz. Mając [wroclaw,krakow,poznan] i chcąc dostać się do "krakow" musimy usunąć "wroclaw" i wtedy odwołać się do pierwszego elementu który został.
Member
Faktem jest, że masa predykatów przydatnych do obsługi list w prologu jest wbudowana w maszynę prologową, jednak postaramy się zdefiniować własny predykant member(Y,X) aby zrozumieć jak działają listy. Jak sama nazwa sugeruje, predykat ten sprawdza czy X (jakiś element) jest w liście Y. Jeśli wyczuwasz tutaj rekurencję, masz dobry nos.
Czy poznan jest w liście [wroclaw,krakow,poznan]? Sprawdźmy czy poznan=wroclaw? Oczywiście nie, więc sprawdźmy czy poznan jest w liście [krakow,poznan]...
[code=Prolog] member(Y,X) :- X=[H|T], H=Y,!. member(Y,X) :- X=[H|T], member(Y,T).[/code]
Co tu się dzieje? Najpierw sprawdzamy czy X jest listą z głową H i ogonem T, następnie patrzymy czy głowa listy(H) = szukany element(Y). Jeśli nie, w drugiej linijce każemy sprawdzić czy Y jest w T, czyli liście bez pierwszego elementu. Wykrzyknik oznacza "Jeśli poprzednie warunki są spełnione, to nie szukaj dalej".
Parę ulepszeń składniowych
W pierwszej linijce naszego member nie używamy w ogóle T (chcemy żeby było, ale nie interesuje nas w tym momencie jak wygląda). Podobnie jak w drugiej nie używamy H. Zastosujmy więc pewien trick zwany zmiennymi anonimowymi. Zamiast nazywać zmienne, które nas nie interesują (ich zawartość nic dla nas nie znaczy w danym momencie) będziemy pisać znak niepodkreślenia. Tak więc nasz predykant po tej zmianie wygląda następująco:
[code=Prolog]member(Y,X) :- X=[H|_], H=Y,!. member(Y,X) :- X=[_|T], member(Y,T).[/code]
Można go jeszcze nieco upiększyć. Mianowice zauważmy, że w obu linijkach wymagamy, by X był w postać [H|_]. Możemy zastosować pewien skrót:
[code=Prolog]member(Y,[H|_]) :- H=Y,!. member(Y,[_|T]) :- member(Y,T).[/code]
Jeśli nie jest dla Ciebie jasne co się stało w tym "podrozdziale" to nie ma się czym martwić - jak pokazywałem wcześniej przed tym "mejkapem kodu" program także działa, choć w niektórych środowiskach może wyświetlać ostrzeżenia.
Listy w boju
Przypomnijmy program z poprzedniego wpisu, który sprawdzał czy możemy dojechać z miasta A do miasta B (z przesiadkami):
[code=Prolog]przesiadka(A,B) :- polaczenie(A,B); polaczenie(A,Z) , przesiadka(Z,B).[/code]
Niby wszystko fajnie, ale przychodząc na dworzec i pytając jak dostać się z Wrocławia do Warszawy od pani w okienku oczekujemy obszerniejszej odpowiedzi niż "true". Spróbujmy zatem stworzyć nową definicję "przesiadka(A,B,L)" która na pytanie o połączenie z A do B zwróci L które będzie listą miast które po drodze odwiedzimy. Będziemy do tego potrzebowali dodatkowej listy pomocniczej-akumulatora-w której będziemy budować naszą listę odwiedzonych miast. Jako, że umiemy dopisywać kolejne miasta na początek listy (nie na koniec), to lista odwiedzonych miast budowana będzie od tyłu, czyli od miasta docelowego:
Z Gliwic do Warszawy: Aku= [warszawa] Aku= [wrocław | warszawa] Aku= [gliwice | wroclaw, warszawa] L = Aku
Zdefiniujmy sobie taki oto zbiór połączeń bezpośrednich:
[code=Prolog] con(gliwice,wroclaw). con(wroclaw,warszawa). con(wroclaw,katowice). con(katowice,warszawa). con(katowice,wroclaw). [/code]
Jak już wspominałem, dla zapytania przesiadka(A,B,L) potrzebowali będziemy dodatkowej listy-akumulatora, tak więc zacząć musimy od tego że przesiadka/3 (czyli z 3 argumentami) jest spełniona wtedy gdy spełniona jest przesiadka/4 (czyli z dodatkowym akumulatorem)
[code=Prolog]przesiadka(A,B,L) :- Aku = [B], przesiadka(A,B,L,[B]),!. [/code]
Wykrzyknik na końcu znaczy tyle co "Jeśli poprzednie warunki są spełnione, to zwróć wynik i nie szukaj innego", czyli w tym przypadku "Jak dojechałeś z A do B, to nie szukaj alternatywnych połączeń". Jak widzicie Aku w naszym przypadku ma wpisane pierwsze miasto do listy, wszak miasto końcowe na pewno odwiedzimy na...końcu. Zastanówmy się co dalej, tradycyjnie najpierw prozą:
Jeśli szukam połączenia z A do B to szukam takiego C, z którego mogę dojechać do B. Dopisuję więc C na listę miast odwiedzonych, i szukam połączenia z A do C. (...) Jeśli szukam połączenia z A do X, ale X=A (tzn. z miasta początkowego do niego samego) to znaczy że zbudowałem listę przesiadek z A do B, W takim przypadku zwrócę tę listę i zakończę pracę
Tak więc szukam przedostatniego miasta z połączeniem do ostatniego. Później przedprzedostatniego z połączeniem do przedostatniego itd. Jeszcze przykład dla naszych zdefiniowanych połączeń (patrz wyżej):
Szukam połączenia z Gliwic do Warszawy (Aku = [warszawa]), więc szukam takiego X, żeby miało połączenie z Warszawą X= Wrocław Szukam połączenia z Gliwic do Wrocławia (Aku = [wroclaw|warszawa]), więc szukam takiego X, żeby miało połączenie z Wrocławiem X= Gliwice Szukam połączenia z Gliwic do Gliwic(Aku = [gliwice|wroclaw,warszawa]), więc mam przypisać L=Aku i zakończyć pracę
Jak to będzie wyglądało w kodzie:
[code=Prolog] przesiadka(A,B,L) :-Aku = [B], przesiadka(A,B,L,Aku),!. przesiadka(A,A,L,Aku) :- L=Aku. przesiadka(A,B,L,Aku) :- con(X,B), Aku2 = [X|Aku] , przesiadka(A,X,L,Aku2). [/code]
Dodatkowo nie chcielibyśmy jechać kilka razy przez to samo miasto, bo bez sensu jest kręcić się w kółko, wobec czego warto byłoby sprawdzać czy już w danym mieście nie byliśmy. Wykorzystamy do tego wcześniejszy predykat member/2:
[code=Prolog] przesiadka(A,B,L) :-Aku = [B], przesiadka(A,B,L,Aku),!. przesiadka(A,A,L,Aku) :- L=Aku. przesiadka(A,B,L,Aku) :- con(X,B), \+member(X,Aku), Aku2 = [X|Aku] , przesiadka(A,X,L,Aku2). [/code]
Znaczek ukośnika i plusa przed nazwą predykatu member jest czymś w rodzaju negacji, czyli tutaj znaczy "jeśli X nie należy do Aku".
Trochę się wpis przeciągnął, ale ciężko było mi pominąć niektóre kwestie, a jednocześnie nie chciałem dzielić go na mniejsze fragmenty, które osobno zbyt wiele by nie dawały. Tak więc gratuluję wytrwałości w czytaniu ;)