Przetwarzanie list¹

Listy to jedne z najbardziej efektywnych struktur występujących w Prologu. Listy są powszechnie używane w programowaniu nienumerycznym. Lista to uporządkowany zbiór elementów dowolnego typu. Najprościej zdefiniować listę poprzez wymienienie jej elementów. Przykłady poprawnych list:

[”A”, ”B”, [”C”, ”D”]]

[ ]

[[5, 3], [3, 2], [5, 8]]

[adam, lubi, grać, piłkę]

[”adam”, ”lubi”, ”grać w”, ”piłkę”]

Listy są jedynym sposobem przechowywania informacji w Prologu, przy pomocy którego jesteśmy w stanie reprezentować np.: zdania jako listy wyrazów, wyrazy jako listy liter, ciągi liczb jako listę liczb.

Mamy dwa przypadki list:

• pustą, która nie zawiera żadnych elementów i jest zapisywana jako [],

• niepustą, która zawiera element początkowy i listę (może być pusta).

Pierwszy element listy nazywamy głową listy, natomiast pozostałą część ogonem.

Pierwszym elementem listy może być cokolwiek (stała, zmienna, struktura), natomiast ogonem zawsze jest lista. Głowę i ogon możemy złączyć w jedno za pomocą operatora specjalnego „.”, który w liście pełni rolę funktora:

.(głowa, ogon)

Listę [adam, lubi, grać, piłka] można utworzyć w następujący sposób:

.(adam, .(lubi, .(grać, .(piłka, []))))

Zauważmy, że lista jednoelementowa [piłka] oprócz głowy posiada również ogon, który jest listą pustą. Zapis listy za pomocą notacji kropkowej jest bardzo niewygodny, dlatego zwykle używamy nawiasów kwadratowych. Musimy mieć jednak świadomość, w jaki sposób Prolog przetwarza utworzone przez nas listy.

Żeby podzielić listę na głowę i ogon wykorzystujemy operator „|”. Wpisanie zapytania

?- [a, b, c, d] = [X|Y].

daje odpowiedź

X = a,

Y = [b, c, d]

Operacje na listach wykonuje się wykorzystując rekurencję i operator „|”. Procedura rekurencyjna składa się z zespołu klauzul, zbudowanych w oparciu o ten sam predykat. W przypadku rekurencji będą to zwykle dwie klauzule:

• fakt opisujący sytuację zakończenia rekurencji (np. napotkanie listy pustej),

• reguła przedstawiającą sposób przetwarzania listy.

Bez użycia operacji na listach nie da się stworzyć praktycznie żadnego zaawansowanego programu.

Sprawdzanie czy element należy do listy

Spróbujmy zdefiniować procedurę postaci należy(X, L), sprawdzającą czy element X należy do listy L. Np.:

należy(a, [b, c, d, a]).

to prawda, ponieważ element a występuje w liście [b, c, d, a]. Natomiast:

należy(a, [b, c, d,[a, e]]).

to fałsz. Zaś:

należy([a, e], [b, c, d,[a, e]]).

To również prawda.

Podając zaś zapytanie:

?– należy(X, [b, c, d, a]).

uzyskamy wszystkie elementy listy:

X = b ;

X = c ;

X = d ;

X = a.

Procedura sprawdzająca bazuje na następującym stwierdzeniu:

X należy do listy L, jeśli:

1. X jest głową listy L, albo

2. X należy do ogona L.

Co w Prologu może być zapisane w postaci dwóch klauzul:

należy(X, [X|O]).

należy(X, [G|O]):- należy(X, O).

Zauważmy, że w pierwszej klauzuli nie ma znaczenia, jaki jest ogon listy, a w drugiej jaka jest głowa dlatego możemy użyć zmiennych anonimowych „_”.

należy(X, [X|_]).

należy(X, [_|O]):- należy(X, O).

Łączenie dwóch list

Spróbujmy zapisać procedurę złącz(L1, L2, L3), gdzie L1 i L2 to dwie listy początkowe, z których powstaje wynikowa lista L3. Przykładowe działanie procedury złącz:

?- złącz([a, b], [c, d], L3).

Otrzymujemy wynik postaci:

L3 = [a, b, c, d].

Procedura łączenia dwóch list złącz(L1, L2, L3) bazuje na stwierdzeniu:

1. Lista pusta dołączona do dowolnej listy daje w wyniku tą samą listę (warunek zatrzymania rekurencji),

2. Oraz regule mówiącej, że jeśli lista L1 jest niepusta, to głowa listy L1 staje się głową listy L3, natomiast ogonem listy L3 jest ogon listy L1 złączony z listą L2.

W Prologu powyższe stwierdzenie zapisujemy następująco:

złącz([ ], L, L).

złącz([X|L1], L2, [X|L3]):- złącz(L1, L2, L3).

Oczywiście konsekwentne odcinanie od listy L1 głowy doprowadzi w końcu do tego, iż stanie się ona listą pustą, a to z kolei zakończy działanie procedury.

Dodawanie elementu do listy

Aby dodać element do listy, najprościej jest dopisać go na początku tak, aby stał się nową głową listy. Jeśli nowym elementem jest X, a lista do której jest dodawany L, to rezultat będzie wyglądał następująco:

[X|L]

Zatem nie potrzebujemy specjalnej procedury dla dopisywania elementu na początek listy. Jeśli jednak taką procedurę chcielibyśmy stworzyć, to wyglądałaby ona następująco:

dodaj(X, L, [X|L]).

Usuwanie elementu z listy

Usunięcie elementu X z listy L możemy zapisać jako relację:

usuń(X, L, L1).

gdzie L1 to lista L pozbawiona elementu X. Podobnie jak w przypadku relacji należy musimy rozpatrzyć dwa przypadki:

1. Jeśli element X jest głową listy L, to wynik relacji usuń będzie po prostu ogon listy L,

2. Jeśli natomiast element X wchodzi w skład ogona listy L, to zostanie z niego usunięty.

usuń(X, [X|Ogon], Ogon).

usuń(X, [Y|Ogon], [Y|Ogon1]):-

usuń(X, Ogon, Ogon1).

Ponieważ relacja ta ma naturę niedeterministyczną, przy wystąpieniu w liście kilku elementów X, otrzymamy kilka możliwych rozwiązań. Np. zapytanie:

?- usuń(a, [a, b, a, a], L).

da nam w rezultacie:

L = [b, a, a];

L = [a, b, a];

L = [a, b, a];

false.

Znajdowanie długości listy

Ostatnia procedura którą omówimy, to procedura podająca liczbę elementów listy: długość(L, N) gdzie L to lista elementów, a N ich liczba.

Procedura łączenia dwóch list długość(L,N) bazuje na stwierdzeniu:

1. Długość listy pustej równa się 0,

2. oraz regule, która mówi że długość listy to długość jej ogona plus jeden.

Odpowiadający temu stwierdzeniu kod Prologa to:

długość([],0).

długość([_|Ogon], Dlug):-

długość(Ogon, X),

Dlug is X+1.

---

1. Przy opracowaniu niniejszych materiałów dydaktycznych wykorzystano:

   Podręcznik I. Bratko; Prolog programming for artificial intrligence. Addison-Wesley, 1986.

   Kurs J. Wójcik; Jezyki i paradygmaty programowania. WSIiZ, 2008.↩