Prolog Language
Rozumowanie danych

Uwagi

Rekurencja

Prolog nie ma iteracji, ale całą iterację można przepisać przy użyciu rekurencji. Rekurencja pojawia się, gdy predykat zawiera cel, który odnosi się do samego siebie. Podczas pisania takich predykatów w Prologu standardowy wzorzec rekurencyjny zawsze ma co najmniej dwie części:

• Podstawowa (nierekurencyjna) klauzula : Zazwyczaj reguła (-y) w podstawowym przypadku reprezentuje najmniejszy możliwy przykład (-y) problemu, który próbujesz rozwiązać - listę bez członków, lub tylko jednego członka, lub jeśli pracuje ze strukturą drzewa, może zajmować się pustym drzewem lub drzewem z tylko jednym węzłem itp. Nierekurencyjnie opisuje podstawę procesu rekurencyjnego.

• Klauzula rekurencyjna (kontynuacja) : zawiera dowolną logikę, w tym wywołanie do siebie, kontynuację rekurencji.

Jako przykład zdefiniujemy dobrze znany predykat append/3 . Patrząc deklaratywnie, append(L1,L2,L3) zachowuje się, gdy lista L3 jest wynikiem dołączenia list L1 i L2 . Kiedy próbujemy ustalić deklaratywne znaczenie predykatu, staramy się opisać rozwiązania, dla których predykat się utrzymuje. Trudność polega na tym, aby uniknąć powtarzających się szczegółów krok po kroku, pamiętając przy tym o zachowaniu proceduralnym, które powinien wykazywać orzecznik.

% Base case
append([],L,L).

% Recursive clause
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

Przypadek podstawowy deklaruje, że „każdy L dołączony do pustej listy to L”, zauważ, że nie mówi to nic o tym, że L jest pusty - lub nawet jest listą (pamiętaj, że w Prologu wszystko sprowadza się do warunków):

?- append(X,some_term(a,b),Z).
X = [],
Z = some_term(a, b).

Aby opisać regułę rekurencyjną, chociaż Prolog wykonuje reguły od lewej do prawej, pomijamy głowę na sekundę i najpierw patrzymy na ciało - czytając regułę od prawej do lewej:

    append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

Teraz mówimy, że jeśli ciało trzyma: „zakładając, że append(L1,L2,L3) trzyma”

    append([X|L1],L2,[X|L3]) :-  append(L1,L2,L3). 

A potem głowa: „następnie append([X|L1],L2,[X|L3]) ”

W prostym języku angielskim oznacza to po prostu:

Zakładając, że L3 jest konkatenacją L1 i L2, wtedy [X, a następnie L3] jest także konkatenacją [X, a następnie L1] i L2.

W praktycznym przykładzie:

„Zakładając, że [1,2,3] jest konkatenacją [1] i [2,3], wówczas [a, 1,2,3] jest także konkatenacją [a, 1] i [2,3]. ”

Teraz spójrzmy na kilka zapytań:

Zawsze dobrze jest najpierw przetestować predykat przy użyciu najbardziej ogólnego zapytania, zamiast podawać mu konkretny przypadek testowy scenariusza. Pomyśl o tym: z powodu unifikacji Prologa nie jesteśmy zobowiązani do dostarczania danych testowych, po prostu przekazujemy je wolnym zmiennym!

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_G1162],
L3 = [_G1162|L2] ;                          % Answer #2
L1 = [_G1162, _G1168],
L3 = [_G1162, _G1168|L2] ;                  % Answer #3
L1 = [_G1162, _G1168, _G1174],
L3 = [_G1162, _G1168, _G1174|L2] ;          % Answer #4
...

Zastąpmy wolny _G1162 zmiennej _G1162 do _G1162 literami alfabetycznymi, aby uzyskać lepszy przegląd:

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_A],
L3 = [_A|L2] ;                              % Answer #2
L1 = [_A, _B],
L3 = [_A, _B|L2] ;                          % Answer #3
L1 = [_A, _B, _C],
L3 = [_A, _B, _C|L2] ;                      % Answer #4
...

W pierwszej odpowiedzi przypadek podstawowy został dopasowany do wzorca i Prolog utworzył L1 na pustej liście i ujednolicił L2 i L3 udowadniając, że L3 jest konkatenacją pustej listy i L2.

W odpowiedzi nr 2, poprzez chronologiczne cofanie, w grę wchodzi klauzula rekurencyjna, a Prolog próbuje udowodnić, że jakiś element w głowie L1 połączonej z L2 to L3 z tym samym elementem w nagłówku listy. Aby to zrobić, nowa wolna zmienna _A jest zunifikowana z _A L1, a L3 okazuje się teraz [_A|L2] .

Zostanie wykonane nowe wywołanie rekurencyjne, teraz z L1 = [_A] . Raz jeszcze Prolog próbuje udowodnić, że jakiś element umieszczony w głowie L1 , połączony z L2 to L3 z tym samym elementem w głowie. Zauważ, że _A jest już głową L1 , która idealnie pasuje do reguły, więc teraz, poprzez rekurencję, Prolog stawia _A przed nową wolną zmienną i otrzymujemy L1 = [_A,_B] i L3 = [_A,_B|L2]

Wyraźnie widzimy powtarzający się wzorzec rekurencyjny i łatwo możemy zauważyć, że na przykład wynik 100. etapu rekurencji wyglądałby następująco:

L1 = [X1,X2,..,X99],
L3 = [X1,X2,..,X99|L2]

Uwaga: jak to jest typowe dla dobrego kodu Prolog, rekurencyjna definicja append/3 daje nam nie tylko możliwość sprawdzenia, czy lista jest konkatenacją dwóch innych list, ale także generuje wszystkie możliwe odpowiedzi spełniające logiczne relacje z jednym lub drugim lub częściowo utworzonych list.

Dostęp do list

Członek

member/2 ma podpis member(?Elem, ?List) i oznacza true jeśli Elem jest członkiem List . Ten predykat może być użyty do uzyskania dostępu do zmiennych na liście, gdzie różne rozwiązania są pobierane poprzez powrót.

Przykładowe zapytania:

?- member(X, [1,2,3]).
X = 1 ;
X = 2 ;
X = 3.

?- member(X,[Y]).
X = Y.

?- member(X,Y).
Y = [X|_G969] ;
Y = [_G968, X|_G972] ;
Y = [_G968, _G971, X|_G975] ;
Y = [_G968, _G971, _G974, X|_G978]
...

Dopasowywanie wzorów

Gdy indeksy, do których potrzebujesz dostępu, są małe, dobrym rozwiązaniem może być dopasowanie wzorca, np .:

third([_,_,X|_], X).
fourth([_,_,_,X|_], X).