18. Понятие списка. Обработка списков. Принадлежность элемента списку, выбор n-го элемента списка, соединение списков.

Список в Прологе представляется множеством элемен­тов, разделенных запятой и ограниченных квадратными скоб­ками.

Так, X = [a,b,c,d] является списком из четырех элементов.

Для разделения списка на части используется предикат "|" (вертикальная черта). Этот предикат разделяет список на голову и хвост. Головой списка может быть его первый эле­мент, тогда хвост списка есть подсписок, состоящий из всего списка за исключением его первого элемента. Так, если X=[a,b,c,d] и X=[Y|Z], то Y=a и Z=[b,c,d]. Заметим, что в слу­чае списка, состоящего из одного элемента, Х=[а] и X=[Y|Z], тогда Y=a и Z=[]-пустой список, который обозначают откры­вающей и закрывающей квадратными скобками. Поскольку список делится на части, то его можно составлять из отдель­ных частей. Так, например, из одного элемента и списка мож­но получить новый список.

Пусть: 1) Х=а, Y=[b,c,d] и Z=[X|Y], тогда Z=[a,b,c,d] и 2) Х=а, Y=b, тогда Z=[a|b], а не Z=[a,b]. В первом случае Y - спи­сок, а во втором Y - элемент. Таким образом, соединение двух элементов дает список, состоящий из элемента и подсписка, а не из двух элементов.

Далее в этом параграфе рассмотрим процедуры работы со списками. Во многих случаях, чтобы упростить изложение, будем приводить только часть clauses Пролог-программ.

Пример: Принадлежность элемента списку.

принадлежит(Х,[Х|_]). /* любой элемент списка всегда является головой какого-нибудь подсписка */

принадпежит(Х,[_|Z) :- принадлежит(Х,Z).

?- принадлежит(седло,[руль,рама,колесо,седло])

Yes

Пример: Выбор n-го элемента списка.

n(1, E, [E|_]).

n(N,E,[_|L]) :- C is N - 1, n(C, E, L).

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

X = 3

1 solution

Пример: Функция присоединения.

append([ ], L, L).

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

Функция append позволяет составлять и расчленять список.

?- append([a,b,c], [d,e,f], L)

L = [a,b,c,d,e,f].

?- append(L, [d,e,f|, [a,b,c,d,e,f])

L = [a,b,c].

?- append([a,b,c], L, [a,b,c,d,e,f])

L = [d,e,f].

?- append(Ll, L2, [a,b,c,d])

L1= [], L2= [a,b,c,d]

L1= [a], L2= [b,c,d]

L1= [a,b], L2= [c,d]

L1= [a,b,c], L2= [d]

L1= [a,b,c,d], L2= []

19. Выбор наименьшего и наибольшего элементов спи­ска, подсчёт количества и суммы элементов списка.

Подсчитаем количество элементов произвольного списка.

/* кол-во элементов пустого списка равно 0 */

колво_элементов([],0).

колво_элементов([_|T],S):- колво_элементов (T,S1), S is S1+1.

?- колво_элементов([a,d,[d,t,[t]],s],X).

X = 4

Yes

Пример: Поиск наименьшего элемента списка.

меньший([X], X).

меньший([X, Y|Z], R) :- X =< Y, меньший([X|Z], R);

X > Y, меньший([Y|Z], R).

?- меньший([6,5,7,3,2,0],X)

X = 0

Следующий предикат подсчитывает сумму всех элементов списка чисел.

сумма_списка([],0).

сумма_списка([H|T],S):- number(H), сумма_списка(T,S1), S is S1+H.

?- сумма_списка([0,1,7,2,456],X).

X = 466

Yes

20. Перевод одного списка термов в другой, Удаление заданного элемента из списка. Сортировка элементов списка.

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

удалить(E, [E | Y], Y).

удалить(E, [X | Y], [X | Z]) :- удалить(E, Y, Z).

?- удалить(7,[1,2,3,7,4,5],Y)

Y= [1,2,3,4,5]

Пример: Сортировка элементов списка.

сортировать([], []).

сортировать(L, [M|R]) :- меньший(L, M), удалить(M, L, Q),

сортировать(Q, R), !.

меньший([X], X).

меньший([X, Y|Z], R) :- X =< Y, меньший([X|Z], R);

X > Y, меньший([Y|Z], R).

удалить(E, [E | Y], Y).

удалить(E, [X | Y], [X | Z]) :- удалить(E, Y, Z).

?- сортировать([1,5,2,7,3,4,2,9],X)

X= [1,2,2,3,4,5,7,9]

Пример: Перевод одного списка в другой, согласно словарю.

словарь("I";"я").

словарь("study","изучаю").

словарь("language","язык").

словарь("PROLOG","Пролог").

словарь("in","в").

словарь("the university","университете").

перевести ([], []).

перевести ([С_А|Ф_А], [С_Р|Ф_Р]):- словарь (С_А, С_Р),

перевести (Ф_А, Ф_Р).

?- перевести(["I","study","language","PROLOG","in","the university"],P)

Р = ["Я", "изучаю", "язык", "Пролог", "в", "университете"]

?- перевести(Р, ["Я", "изучаю", "язык", "Пролог", "в", "университете”]).

P = ["I", "study", "language", "PROLOG", "in", "the university"]