Paradygmaty programowania/Ćwiczenia 14: Programowanie w logice w Prologu II

Zadanie 1

Rozważmy następujący program:

 p(X, Y) :- q(X, Y).
 p(X, Y) :- q(X, Z), p(Z, Y).
 q(a, b).
 q(b, a).

Jaki będzie rezultat po wpisaniu celu p(a, X)?

Wskazówka:

Zauważmy, że choć możliwe odpowiedzi są tylko dwie (X = a oraz X = b), to istnieje nieskończenie wiele drzew dowodu.

Zadanie 2

Rozważmy program:

 pocz(X, Y) :- p(X, Y).
 pocz(X, X) :- s(X).
 p(X, Y) :- sukces(1), q(X), sukces(2), r(Y).
 p(X, Y) :- s(X), r(Y).
 q(a).
 q(b).
 r(c).
 r(d).
 s(e).
 sukces(_).

Jaki będzie rezultat po wpisaniu celu pocz(X, Y)? Co się zmieni, gdy wywołanie sukces(1) zastąpimy odcięciem? Co, gdy zastąpimy sukces(2)?

Wskazówka:

Zastąpienie sukces(1) odcięciem eliminuje odpowiedzi X = e, Y = c oraz X = e, Y = d. Zastąpienie sukces(2) eliminuje dwie wymienione wcześniej, a ponadto X = b, Y = c oraz X = b, Y = d (niezależnie do tego, czy sukces(1) zostawiliśmy, czy zastąpiliśmy odcięciem).

Zadanie 3

Napisać program łączący listy. Czy można go użyć do wytworzenia wszystkich par list, które po złączeniu dają wskazaną listę? Sprawdź.

Wskazówka:

Jest to jeden z klasycznych programów dydaktycznych, wyglądających w Prologu bardzo efektownie; np.

 połącz([], X, X).
 połącz([X | Y1], Z, [X | Y2]) :- połącz(Y1, Z, Y2).

Zadanie 4

Napisać program wyliczający ostatni element listy.

Wskazówka:

Prosta definicja rekurencyjna...

 ostatni([X], X).
 ostatni([_ | Og], X) :- ostatni(Og, X).

Zadanie 5*

Napisać program sprawdzający, czy jedna lista jest permutacją drugiej.

Wskazówka:

Jak zwykle, rekurencyjnie... Lista pusta jest permutacją listy pustej. Następnie, jeśli X jest permutacją listy Y, to po wstawieniu elementu Z (gdzieś) do X jest to permutacja listy [Z | Y]. A zatem:

 perm([], []).
 perm([Z | Y], W) :- perm(Y, X), wstaw(Z, X, W).
 
 wstaw(Z, X, W) :- połącz(X1, X2, X), połącz(X1, [Z | X2], W).

Zadanie 6

Napisać (jak najprostszy) program sortujący listę liczb całkowitych.

Wskazówka:

Ten, kto rozwiązał poprzednie zadanie, z tym nie powinien mieć kłopotów. Poniższe rozwiązanie, choć bardzo nieefektywne, jest w bardzo prologowym stylu...

 uporządkowana([]).
 uporządkowana([_]).
 uporządkowana([X, Y | Z]) :- X =< Y, uporządkowana([Y | Z]).
 
 sortuj(X, Y) :- perm(X, Y), uporządkowana(Y).

Zadanie 7*

Napisać efektywny program sortujący listę liczb całkowitych „przez złączanie” (mergesort).

Wskazówka:

Tworzymy najpierw funktory do dzielenia i do złączania list. Sortowanie jest wówczas proste.

 podziel([], [], []).
 podziel([X], [], [X]).
 podziel([X, Y | Z], [X | V], [Y | W]) :- podziel(Z, V, W).
 
 złącz(X, [], X).
 złącz([], Y, Y).
 złącz([X | A], [Y | B], [X | C]) :- X <  Y, złącz(A, [Y | B], C).
 złącz([X | A], [Y | B], [Y | C]) :- X >= Y, złącz([X | A], B, C).
 
 sortujz([], []).
 sortujz([X], [X]).
 sortujz([X1, X2 | Xo], Y) :-
   podziel([X1, X2 | Xo], D1, D2),
   sortujz(D1, S1),
   sortujz(D2, S2),
   złącz(S1, S2, Y).

Zadanie 8

Dlaczego w rozwiązaniu poprzedniego zadania pierwszy parametr ostatniej klauzuli sortujz jest zapisany jako [X1, X2 | Xo]? Co by się stało, gdyby zamienić go (wraz z pierwszym parametrem podziel) po prostu na X? Jak zaradzić tej niedogodności?

Wskazówka:

Chodzi o jednoznaczność wyboru klauzuli do rezolucji. Jeśli napiszemy po prostu X, to dla list pustych i jednoelementowych będziemy mieli dwie pasujące klauzule; to z kolei spowoduje „pętlenie się” interpretera. Można temu zaradzić, umieszczając odcięcie w dwóch pierwszych klauzulach sortujz:

 sortujz([], []) :- !.
 sortujz([X], [X]) :- !.