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]) :- !.
