Листе¶

Као и други програмски језици, и програмски језик Prolog пружа подршку за рад са листама података. Слично као што смо видели у програмском језику Haskell, листа је или празна ([]) или се разлаже на главу и реп ([X|XS]). Листе се задају навођењем елемената између угластих заграда (нпр. [3, 8, 4, 2]).

Кренимо од предиката myMember, који проверава да ли елемент E припада листи (то ради уграђени предикат member, тако да ову имплементацију приказујемо само ради илустрације). Елемент не припада празној листи, тако да случај празне листе не треба да буде обрађен (ако нешто не постоји у бази знања, оно се аутоматски сматра нетачним). Елемент припада непразној листи ако и само ако је једнак глави или припада репу. Подсетимо се, дисјункцију можемо записати оператором ;.

myMember(X, [H|T]) :- X = H ; myMember(X, T).

Наравно, ово правило је могуће разбити на два.

myMember(X, [X|_]).
myMember(X, [_|T]) :- myMember(X, T).

Јасно је да коришћењем овог предиката можемо проверити да ли дати број припада датој листи, тј. да наредни упити враћају исправне резултате.

?- myMember(3, [1, 2, 3, 4]).   % true
?- myMember(5, [1, 2, 3, 4]).   % false

Међутим, можда мало неочекивано, овај предикат се може употребити и да се наброји један по један елемент листе. Наредни упит

?- myMember(X, [1, 2, 3, 4]).

даје резултат X=1, затим X=2, X=3 и на крају X=4.

Ако је елемент једнак глави листе, он је члан листе и нема више потребе да се проверава да ли припада репу. Зато на крај првог правила можемо поставити рез.

myMember(X, [X|_]) :- !.
myMember(X, [_|T]) :- myMember(X, T).

Међутим, ова измена спречава употребу предиката myMember за набрајање свих елемената листе, јер се након пријављивања првог елемента спречава бектрекинг преко реза. Зато се верзија без реза ипак сматра бољом, ако се планира употреба за набрајање свих елемената листе (што је, видећемо, доста чест случај).

Илуструјмо рад са листама кроз још неколико предиката.

Дефинисати предикат који одређује дужину листе.

Дужина празне листе је нула, а непразне листе је за један већа од дужине репа.

myLength([], 0).
myLength([_|T], N) :- myLength(T, N1), N is N1 + 1.

Пошто је употребљен оператор is, овај се предикат не може употребљавати да се наброје све листе дате дужине.

Дефинисати предикат који спаја (надовезује) две листе.

Решење тече рекурзијом по првој листи. Ако је она празна, резултат је друга листа. Ако је она облика глава-реп, тада резултат добијамо тако што рекурзивно спојимо реп R и другу листу L добијајући међурезултат R1. Коначан резултат добијамо додајући главу H на почетак међурезултата.

myAppend([], L, L).
myAppend([H|T], L, [H|R1]) :- myAppend(T, L, R1).

Друго правило можемо изразити и коришћењем оператора унификације на десној страни (тада имамо експлицитну променљиву уз резултат којој „додељујемо вредност“ на крају, када су познате вредности од којих се она гради):

myAppend([], L, L).
myAppend([H|T], L, R) :- myAppend(T, L, R1), R = [H, R1].

У зависности од личног стила неком ће прва а неком друга имплементација бити јаснија и разумљивија.

Овај предикат исправно надовезује две дате листе. На упит

?- myAppend([1, 2, 3], [4, 5, 6], R).

добијамо исправан одговор X=[1, 2, 3, 4, 5, 6]. Међутим, прилично неочекивано, овај предикат успева и да одговори на питање надовезивањем које две листе се може добити дата листа.

?- myAppend(L1, L2, [1, 2, 3, 4]).

Добијају се одговори L1=[], L2=[1,2,3,4], затим L1=[1], L2=[2,3,4], затим L1=[1,2], L2=[3,4], затим L1=[1,2,3], L2=[4] и на крају L1=[1,2,3,4], L2=[].

Дефинисати предикат који одређује последњи елемент листе.

Овај предикат није дефинисан за празне листе. Базу (излаз из рекурзије) ће зато представљати случај једночлане листе где је једини елемент листе уједно и последњи. Ако је листа непразна, тада је последњи елемент репа листе последњи елемент листе.

myLast([X], X).
myLast([_|T], Res) :- myLast(T, Res).

Овај предикат исправно одређује последњи елемент било које непразне листе, а за празну листу враћа одговор false. Остаје можда мало нејасно да ли је након првог правила додати рез, тј. зашто се једночлана листа не обрађује и на основу првог и на основу другог правила, пошто је она такође непразна. Једночлана листа се може унификовати са листом [_|T], тако што је T празна листа. Након тога се, због десне стране правила, тражи последњи елемент празне листе, и пошто то не успева, не налази се додатно решење. Дакле, друго правило се примењује на једночлану листу, али не доводи до решења. Ако не ставимо рез након првог правила, овај предикат се може искористити и да наброји све листе којима је дати елемент последњи. На упит

myLast(L, 0).

Добијамо одговоре L=[0], L=[_1412, 0], L = [_1412, _1418, 0] итд. при чему су _1412, _1418 итд. називи аутоматски генерисаних променљивих.

Дефинисати предикат који одређује елемент листе на датој позицији.

Елемент на позицији 0 празне листе је њена глава. За K > 0 елемент на позицији K непразне листе је елемент на позицији K-1 њеног репа.

kth([H|_], 0, H).
kth([_|T], K, R) :- К > 0, K1 is K-1, kth(T, K1, R).

Променљива R означава резултат.

У решењу можемо употребити и сечење.

kth([H|_], 0, H) :- !.
kth([_|T], K, R) :- K1 is K-1, kth(T, K1, R).

Дефинисати предикат који обрће листу.

Наивно решење добијамо тако што приметимо да се обртањем празне листе добија празна листа, а да се резултат обртања непразне листе, која има главу и реп, добија тако што се глава те листе добија на резултат обртања репа те листе.

myReverse([], []).
myReverse([H|T], R) :- myReverse(T, R1), myAppend(R1, H, R).

Потребно је и да дефинишемо предикат којим се елемент додаје на крај листе. Додавањем елемента на крај празне листе добија се једночлана листа. Ако је листа непразна, додавање елемента на њен крај се добија тако што јој се задржи глава, а реп јој се замени додавањем елемента на крај њеног репа.

myAppend([], X, [X]).
myAppend([H|T], X, [H|T1]) :- myAppend(T, X, T1).

Уместо да директно наведемо облик резултата на левој страни правила, можемо употребити и оператор унификације на десној страни правила.

myAppend([], X, R) :- R = [X].
myAppend([H|T], X, R) :- myAppend(T, X, T1), R = [H|T1].

Ова имплементација обртања је неефикасна и ефикасније решење се добија ако се користи акумулатор (опис овог алгоритма приказан је у поглављу о функционалном програмирању). Узима се један по један елемент полазне листе и додаје се на почетак помоћне листе (акумулатора) све док се полазна листа не испразни и тада је коначан резултат оно што се нагомилало у акумулатору. На почетку се креће од празног акумулатора.

myReverse([], A, A).
myReverse([H|T], A, R) :- myReverse(T, [H|A], R).
myReverse(L, R) :- myReverse(L, [], R).

Променљива L означава листу која се обрће, R резултат обртања, а A акумулатор.

Обртање можемо употребити да проверимо, на пример, да ли је ниска палиндром.

proveriPalindrom(XS) :- obrni(XS, XS).

Дефинисати предикат који прима угнежђене листе бројева и „пегла” их, тј. издваја листу свих бројева који се у њима јављају. На пример, треба да важи myFlatten [[1, 2, 3], [4, [5, 6]], 7] [1, 2, 3, 4, 5, 6, 7].

„Пеглањем“ празне листе добија се празна листа. Код непразних листа, „пегла“ се реп листе, а затим се анализира глава. Постоје два могућа случаја. Ако је глава листа, тада се резултат добије тако што се та глава „пегла“ и резултат се спаја са „испегланим“ репом. Ако глава није листа, она се таква каква јесте додаје на почетак „испегланог“ репа. Проверу да ли је дата променљива листа можемо извршити библиотечким предикатом is_list.

myFlatten([], []).
myFlatten([H|T], X) :- is_list(H), myFlatten(H, H1), myFlatten(T, T1), append(H1, T1, X), !.
myFlatten([H|T], [H|T1]) :- myFlatten(T, T1).

Приметимо да ову функционалност није могуће постићи у језику Haskell, јер тип полазне листе није могуће дефинисати (тамо сви елементи листе морају да имају исти тип, а овде радимо са листама које садрже елементе различитих типова).

Дефинисати предикат који обједињава две сортиране листе у трећу сортирану. Дефинисати затим предикат који дели листу на две једнаке половине. Дефинисати на крају предикат који применом претходна два предиката сортира листу.

Ако је било која од две листе које се обједињавају празна, резултат је она друга. Ако су обе листе непразне, мању од њихове две главе смештамо на почетак резултата, а реп резултата добијамо рекурзивним обједињавањем репа листе чија је глава била мања и целе друге листе.

merge([], L2, L2).
merge(L1, [], L1).
merge([H1|T1], [H2|T2], R) :- H1 < H2, merge(T1, [H2|T2], R1), R = [H1|R1], !.
merge([H1|T1], [H2|T2], R) :- merge([H1|T1], T2, R1), R = [H2|R1].

Поделу листе на два једнака дела можемо постићи тако што наизменично елементе са почетка листе која се дели смештамо у једну и другу резултујућу листу. Празна листа се дели на две празне. Једночлана се дели тако што ће једна од резултујућих листа бити једночлана, а друга празна. Листу која има бар два елемента делимо тако што реп без та два елемента делимо на два дела, а онда први елемент стављамо на почетак првог од та два дела, а други на почетак другог.

split([], [], []).
split([X], [X], []).
split([H1,H2|T], [H1|L], [H2|R]) :- split(T, L, R).

На крају дефинишемо сортирање обједињавањем. Празна и једночлана листа се не мењају приликом сортирања. Листа која има бар два елемента се дели на две подлисте, оне се независно сортирају и на крају обједињавају.

mergeSort([], []).
mergeSort([X], [X]) :- !.
mergeSort(L, R) :- split(L, L1, L2), mergeSort(L1, L1S), mergeSort(L2, L2S), merge(L1S, L2S, R).

Дефинисати предикат који одређује листу свих простих бројева који су мањи од датог броја. Претпости да на располагању имамо предикат prost за проверу да ли је број прост и користити га у решењу.

У неким случајевима би предикати који се не ограниче резом теоријски враћали бесконачна решења, тј. упадали би у бесконачну рекурзију. На пример, наредни предикат би тражио све просте бројеве.

prosti(N, [N|T]) :- prost(N), N1 is N + 1, prosti(N1, T).
prosti(N, T) :- not(prost(N)), N1 is N + 1, prosti(N1, T).

Ако наметнемо горње ограничење на величину бројева које тражимо, можемо употребити рез да зауставимо ову бесконачну претрагу, али и да избегнемо скупу проверу да ли је број прост у оба правила.

prosti(N, Max, []) :- N > Max, !.
prosti(N, Max, [N|T]) :- prost(N), N1 is N + 1, prosti(N1, T), !.
prosti(N, Max, T) :- N1 is N + 1, prosti(N1, T).

prosti(Max, P) :- prosti(2, Max, P).

Покушајте да за вежбу имплементирате решење које користи Ератостеново сито. Као помоћни предикат можете дефинисати предикат који из дате листе избацује све умношке датог броја.