7.12.1. Использование списка.

Для использования списка нужно описать предикат списка. Предикатам списка обычно присваивают имена, которые характеризуют либо тип элемента, либо сами данные. Введение списка отражается в трех разделах. Домен списка должен быть определен в разделе domains, работающий со списком предикат должен быть в разделе predicates, сам список задается либо в фактах, либо в цели.

Отличительной особенностью списка является наличие знака * после имени домена элементов. Используем операцию разделения списка на голову и хвост для вывода на печать всех элементов списка.

Пример.

domains

number_list=integer

predicates

print_list(numbes_list) – предикат печатает список

clauses

print_list([ ]).

print_list([H|T]):-write(H), nl, print_list([T]).

goal

number_list=[1, 2, 3, 4, 5], print_list(number_list)

Или просто:

Print_list([1, 2, 3, 4, 5, 6, 7])

7.12.2. Поиск элементов в списке.

Введем предикат «Принадлежит» (member)

1. Принадлежит (X, L):– L=[H|T], Х=H

или короче:

Принадлежит(X, [Y|_]):–X=Y

В первом случае X является элементом списка L, если X совпадает с головой списка L. Во втором случае X принадлежит списку, если он содержится в хвосте списка:

2. Принадлежит (X, L):–L= [Y|T], принадлежит (Х, Т)

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

3. Пролог рассматривает рекурсивное обращение предиката «Принадлежит» как попытку найти соответствие для некоторой новой его копии, что предотвращает путаницу переменных.

Имеется три различных варианта использования предиката «Принадлежит»:

А) memder (X, [a, b, c]) – искать, является ли Х элементом a, b, c.

В) memder (b, X) – искать списки, в которых находятся элементы b.

С) memder (a, [a, b, c]) – проверить истину.

7.12.3. Создание нового списка путем слияния двух списков

Для создания нового списка путем слияния двух списков используется предикат add.

присоединить (A, B, C), C – результат, А, В – исходные списки.

Исходный список В присоединяется списком в конец списка А; и таким образом образуется список С.

1) Граничное условие-присоединение пустого списка к списку дает сам список

Присоединить ([ ], L, L)

2) Рекурсивное условие: присоединение списка В к концу списка А выполняется так: список В присоединяется к хвосту списка А, а затем спереди добавляется голова списка А.

Присоединить([X|L1], L2, [X, L3]):– присоединить(L1, L2, L3).

Опишем процесс создания объединенного.

1. Первый элемент первого списка (Х) всегда будет и первым элементом третьего списка.

2. Хвост третьего аргумента (L3) всегда будет представлять результат присоединения второго аргумента (L2) к хвосту первого списка (L1).

3. Для присоединения одного списка к другому используем предикат присоединить.

4. Так как при каждом обращении к правилу удаляется голова списка, являющегося первым аргументом, то постепенно этот список будет исчерпан и станет пустым, так что произойдет выход на граничное условие.

Пример.

Присоединить([1, 2, 3], [4, 5], [ ]).

Сравнивает его с первым правилом – неудача.

Сравнивает его со вторым правилом

Х=1

Присоединить ([1|2, 3], [4, 5], [ ]):– присоединить ([2, 3], [4, 5], [ ])

X=2

Присоединить([2|3], [4, 5], [ ]):–присоединить([3], [4, 5], [ ])

головы списка помещаются в стек

Х=3

Присоединить([3| [ ]], [4, 5], [ ]):–присоединить([ ], [4, 5], [ ]

он сравнивается с первым предикатом

Присоединить([ ], [4, 5], [ ]):-присоединить([ ], [4, 5], [4, 5]).

Правило 1 удовлетворено и Turbo Prolog начинает сворачивать рекурсивные вызовы второго правила. Извлекаемые при этом из стека элементы помещаются в качестве головы к первому и третьему списку. Элементы извлекаются в обратном порядке, и значение извлеченного из стека элемента присваивается переменной N одновременно в [N|L1] и [N|L3]. Шаги данного процесса можно представить следующим образом:

присоединить ([ ], [4, 5], [4, 5]),

присоединить([3], [4, 5], [3, 4, 5]),

присоединить([2, 3], [4, 5], [2, 3, 4, 5]),

присоединить([1, 2, 3], [4, 5], [1, 2, 3, 4, 5]).

Присвоение идет рекурсивно до тех пор, пока стек не будет полностью исчерпан.

В английской транскрипции

Append([ ], Q, Q).

Append([X|Xs], Ys, {X|Zs]):–append(Xs, Ys, Zs).

В зависимости от вопроса будут совершаться разные операции, например:

• Append([a, b, c], [d, e], Xs) приведет к списку Xs=[a, b, c, d, e].

• Append(Xs, [c, d], [a, b, c, d]) дает разность Xs=[a, b].

• Предикат member может быть выражен через предикат append в виде: Member(X, Ys):–append(As, [X|Xs], Ys). X является элементом списка Ys, если Ys может быть расщеплен на два списка, причем X является головой второго списка.