Лекция: ОБРАБОТКА СПИСКОВ

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

Список можно задать перечислением элементов. Например, имена учеников класса:

[саша, петя, дима, ксюша, лена].

Элементами списка могут быть не только атомы, но и функции, и вообще любые элементы, даже списки. Заранее длина списка не задается, и в ходе выполнения программы она может меняться.

Альтернативный способ задания списка использует понятия головы и хвоста списка.

Например, в списке [X | Y] Х — это голова списка. Y — его хвост.

Хвост списка по определению также является списком.

Теперь список может быть определен рекурсивно:

1) пустой список [] — список:

2) [X | Y] — список, если Y — список.

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

1) из факта, ограничивающего рекурсию и описывающего операцию для пустого списка;

2) из рекурсивного правила, определяющего операцию над списком, состоящим из головы и хвоста ( в голове правила), через операцию над хвостом (в подцели).

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

Программа 122

сколько ([], 0).

сколько ([А|В], N) :- сколько (В, М), N is M+1.

?- сколько ([саша, игорь, лена]), X).

Ответ: Х=3.

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

Программа 123

принадлежит (X, [X | Y]).

принадлежит (X, [A |Y ]): — принадлежит (X,Y).

?-принадлежит (4,(1,3,4,9]).

Ответ: да.

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

Пример 3: соединение двух списков.

Эту задачу можно описать с помощью следующих предикатов:

а) ограничение рекурсии состоит в том, что если к пустому списку [ ] добавить список Р, то в результате получится Р;

б) рекурсия состоит в том, что можно список Р добавить к концу списка [X|Y], если Р будет добавлен к хвосту Y и затем присоединен к голове Х (при этом получается список [Х|Т]).

Программа 124

присоединить([ ], Р, Р).

присоединить([XIY], Р, [X | Т]):-присоединить(Y, Р, Т).

? присоединить(L,[джим.R],(джек, бил, джим, тим, джим, боб]).

Ответ:

L=[джек, бил]. К=[тим джим, боб]. L=[джек, бил, джим, тим]. R=[бoб].

Существует традиция использовать для обозначения предикатаслияния двух списков предикативный символ append (по-английски -добавить).

В некоторых случаях постановки вопросов к такого рода программам приходится использовать отсечение (!).

Программа 125

append([ ], L, L).

append([A I B], C, [A | D]):- append(B, C, D).

?-append(X,Y,[1,2]).

Ответ:

X=[]

Y=[l,2]

X=[l]

Y=[2]

X=[l,2]

Y=[].

Если же заменить первое предложение на append([ ], 1,1):-!.. и задать тот же вопрос, то получится правильный ответ:

Х=[]

Y=[l,2].

Пример 4. удаление элементов из списка.

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

Программа 126

удал (X. [X I Y], Y): — !.

удал (X. [Z I Y], [Z I W]): — удал (X, Y, W) .

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

Данная программа удаляет первое вхождение в список элемента, связанного с переменной X. Знак отсечения "!«в конце правила предотвращает последующий поиск и вывод лишних вариантов ответов после выполнения ограничительного факта.

Для удаления всех вхождений элемента Х программу надо дополнить:

удал (Х,[ ],[]).

удал (X, [X | Y], W) :- удал (X, Y, W).

удал (X, [Z I Y], W):- удал (X, Y, W).

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

Пример 5: индексация элементов списка.

Смысл программы 127 состоит в том, чтобы получить элемент под номером N или узнать номер элемента X.

Программа 127

получить ([X | Y], 1, X).

получить ([W | Y], N, X) :- N is M+l, получить (Y, M, X).

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

Программа 128

max ([X], X).

max ([X | Y], X) :- шах (Y, W), X>W, !.

max ([X | Y], W) :-max (Y, W).

Декларативный смысл программы: если в списке один элемент — он и является максимальным, если более одного, то это голова списка, если она больше максимального элемента хвоста, или максимальный элемент хвоста.

Пример 7: обращение списка.

Данная задача — самая сложная из рассмотренных. Для ее решения важно сообразить, что обратить список из одного элемента — означает оставить список без изменения. Обратить более длинный список — обратить его хвост, а потом сзади приставить к нему голову исходного списка.

Программа 129

обр ([X], [X]) .

обр ([X I Y], Z) :- обр (Y, W), присоединить (W, [X], Z).

В этой программе используется процедура слияния списков, описанная выше.

Arity-Prolog располагает значительным числом встроенных предикатов для обработки списков, так что приведенные программы имеют, в основном, учебный характер.