Рекурсивные правила

Мы рассмотрим правила, определяющие отношения в уже существующих. Важное дополнение – рекурсивные правила. Отношение определяется в самих терминах отношений.

ПРЕДОК(Х,У):-РОДИТЕЛЬ(Х,У).

ПРЕДОК(Х,У):-ПРЕДОК(Х,Z), РОДИТЕЛЬ(Z,У).

Логические программы

«Реляционные базы данных» - на базе отношений.

Представление данных с помощью таблицы.

Логические программы можно рассматривать как мощное усиление реляционных БД за счет применения правил. Программы, построенные исключительно из фактов, совпадают с отношениями. Операции реляционной алгебры легко описываются в терминах Пролога.

Списки

Аналогично Лиспу в Прологе активно используются списки в качестве структуры данных.

Список – рекурсивная структура из 2 частей; 1) – элемент (голова списка),

2) – остаток (хвост списка).

[X|Y], X – голова (CAR), Y – хвост (CDR).

[ ] – пустой (NIL).

[a,b]

[X,Y|Ys]

СПИСОК([ ])

СПИСОК([X|Xs]):-СПИСОК(Xs).

Предикат члена:

ЧЛЕН(X,[X|Xs]).

ЧЛЕН(X,[Y|Ys]):-ЧЛЕН(X,Ys). – предикат принадлежности

PREFIX([a,b],[a,b,d,c]). – Да, если задать вопрос.

PREFIX([ ], Ys).

PREFIX([X,Xs]):-PREFIX(Xs,Ys).

SUFFIX(Xs,Xs).

SUFFIX(Xs,[Y|Ys]):-SUFFIX(Xs,Ys).

Подсписок:

SUBLIST(Xs,Ys):-PREFIX(Xs,Ys).

SUBLIST(Xs,[Y|Ys]):-SUBLIST(Xs,Ys).

SUBLIST(Xs, As Xs Bs):-APPEND(As, Xs Bs, As Xs Bs), APPEND(Xs, Bs, Xs Bs).

SUBLIST(Xs, As Xs Bs):-APPEND(As Xs, Bs, As Xs Bs), APPEND(As, Xs, As Xs).

ADJACENT(X,Y,Zs):-APPEND(As,[X,Y|Ys],Zs).

Обращение списка:

reverse (List, Tsil).

reverse ([ ],[ ]).

reverse ([X|Xs],Zs):-reverse (Xs,Ys), append(Ys,[X],Zs).

reverse (Xs,Ys):-reverse (Xs,[ ],Ys).

reverse ([X|Xs],As,Ys):-reverse(Xs,[X|As],Ys).

reverse ([ ],Ys,Ys).

Подсчет длины списка:

length([ ],0).

length([X|Xs],N1):-length(Xs,N), N1:=N+1.

Удаление элемента из списка:

udal([X|Xs],X,Ys):-udal(Xs,X,Ys).

udal([X|Xs],Z,[X|Ys]):-X≠Z, udal(Xs,Z,Ys).

udal([ ],X,[ ]).

vyrez(X,[X|Xs],Xs).

vyrez(X,[X|Ys],[Y|Zs]):-vyrez(X,Ys,Zs).

Легенда о Ханойской долине:

hanoi(1,A,B,D,[A на B]).

hanoi(N1,A,B,D,Xody):-hanoi(N,A,D,B,X1), hanoi(N,D,B,A,X2), append(X1,[A на B|Xs],Xody), N1:=N+1.

Сумма нечетных:

nech(X):-X чет 2 =:=1.

chet(X):-X чет 2 =:=0.

sumnech([ ],0).

sumnech([X|Xs],S):-chet(X), sumnech(Xs,S).

sumnech([X|Xs],S):-nech(X), sumnech(X1,S1), S is S1+X. (is - равенство)

Сумма нечетных (2 вариант):

sumn([ ],0).

sumn([X|Xs],S):-D is (X чет 2)*X, sumn(Xs,S1), S is S1+D.

Сортировка:

1 вариант:

SORT(Xs,Ys):-PEREST(Xs,Ys), UPOR(Ys).

UPOR([X]).

UPOR([X,Y|Ys]):-X<=Y,UPOR([Y|Ys]).

PEREST([],[]).

PEREST(Xs,[Z|Zs]):-VYREZ(Z,Xs,Ys),PEREST(Ys,Zs).

2 вариант:

SORT(Xs,Ys):-PEREST(Xs,Ys),UPOR(Ys).

UPOR([X]).

UPOR(X,Y|Xs):-X<=Y,UPOR([Y|Ys]).

PEREST([],[]).

PEREST([X|Xs],Zs]):-PEREST(Xs,Ys),VSTAV(X,Ys,Zs).

VSTAV(X,Ys,Zs):-VYREZ(X,Zs,Ys).

3 вариант:

SORT([],[]).

SORT([X|Xs],Ys):-SORT(Xs,Zs),VSTAVKA(X,Zs,Ys).

VSTAVKA(X,[],[X]).

VSTAVKA(X,[Y|Ys],[Y|Zs]):-X>Y,VSTABKA(X,Ys,Zs).

VSTAVKA(X,[Y|Ys],[X,Y|Ys]):-X<=Y.