Работа со списками. Списки являются одной из основных структур данных Пролога

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

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

Для удобства обработки списков в Прологе введены два понятия: голова и хвост. Первый элемент списка (или несколько первых элементов) являются головой списка, а оставшиеся – его хвостом. Тогда список – это структура данных, определяемая следующим образом:

– список является либо пустым,

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

Для обозначения списка используются квадратные скобки, а для отделения головы списка от его хвоста – символ "|". Например, для списка [1|2,3] элемент 1 является головой, а список [2, 3] хвостом. Пустой список обозначается [ ]. Если список не разделяется на голову и хвост, квадратные скобки можно опустить.

Рассмотрим некоторые предикаты для обработки списков.

11. Добавление элемента в список. Этот предикат должен иметь три аргумента: добавляемый элемент, список и результирующий список. Наиболее простой способ добавить элемент в список – это вставить его в самое начало так, чтобы он стал новой головой. Если X – это новый элемент, который добавляют в список L, то предикат добавления элемента в список можно записать таким образом:

add(X,L, [X|L]).

12. Удаление элемента. Удаление элемента X из списка L можно определить в виде отношения

away(X,L,L1),

где L1 – это список L, из которого удален элемент X.

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

away(X, [X|T],T).

away(X, [Y|T], [Y|T1]):– away(X,T,T1).

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

member(X,L).

Здесь L – некоторый список, Х – объект того же типа, что и элементы списка L. Составление предиката может быть основано на следующих соображениях: X есть либо голова списка L, либо X принадлежит хвосту. Это может быть записано в виде двух предложений, первое из которых есть простой факт, ограничивающий вычисления, а второй – рекурсивное правило:

member(X, [X| _ ]).

member(X, [ _ | T ]):– member(X,T).

Напомним, что знаком подчерка здесь обозначена анонимная переменная, значение которой в данном предложении неважно.

Если окажется пустой список, тогда предикат завершается ложно, так как для пустого списка нет своего правила.

14. Сцепление (конкатенация) списков.

conc(L1,L2,L3).

Объединяемые списки задаются первыми двумя аргументами L1 и L2. Список L3 представляет собой конкатенацию этих списков.

Для определения отношения конкатенация отделим два случая:

(1) Если первый список пуст, то второй и третий представляют собой один и тот же список:

ñonc([ ],L,L).

(2) Если первый аргумент не пуст, то он имеет голову и хвост, т.е. [X|L1]. Его сцепление со списком L2 – список [X|L3], где список L3 получен после сцепления списков L1 и L2, т.е.

conc([X|L1],L2,[X|L3]):–conc(L1,L2,L3).

15. Удаление из списка повторяющихся элементов. Аргументами предиката unik являются два списка: исходный и результирующий. Смысл алгоритма прост: если элемент присутствует в списке (проверяется предикатом member), то он не записывается в результирующий список, иначе добавляется в качестве головного элемента.

unik([ ],[ ]).

unik([H|T], L):– member(H,T), unik(T,L).

unik([H|T], [H|L]):– unik(T,L).

16. Обращение списка. Определим предикат

reverse(L1,L2).

Аргументы L1 и L2 – два списка, из которых список L2 содержит элементы списка L1, записанные в обратном порядке.

reverse(L1,L2):–reverse1(L1,[],L2).

reverse1([],L,L).

reverse1([H|T],L1,L2):–reverse1(T,[H|L1],L2).

Предикат reverse в данном случае является интерфейсным, он запускает в работу основной рабочий предикат reverse1, имеющий дополнительный второй аргумент – список, который вначале пуст, и используется собственно для обращения списка. На каждом шаге рекурсии один элемент исходного списка становится головой промежуточного списка. Третий аргумент передается от шага к шагу и конкретизируется в момент достижения базового состояния предиката reverse1. Когда первый список исчерпан, второй уже содержит элементы, записанные в обратном порядке. Отметим, что наличие третьего аргумента, фиксирующего результат, обязательно, т.к. после обратного прохождения рекурсии все конкретизированные переменные принимают свои первоначальные значения.

17. Вычисление суммы элементов списка. Можно выполнить предикатом

sum(L,S).

Здесь S – сумма элементов списка L. Запрограммировать этот предикат можно двумя способами. Рассмотрим сначала более очевидный:

sum([ ],0).

sum([H|T], S1):–

sum(T,S2),S1=S2+H.

Декларативный смысл этого алгоритма: если список пуст, то сумма его элементов равна нулю, иначе список можно разделить на голову H и хвост T; сумма элементов такого списка S1, при этом сумма элементов хвоста T есть S2 и S1=S2+H. Обратим внимание, что это рекурсия нехвостовая: в рекурсивном правиле предиката sum рекурсивное условие записано не последним. Нехвостовая рекурсия при последовательных вызовах генерирует промежуточные переменные, которые конкретизируются при обратном прохождении рекурсии.

Рассмотрим работу этого предиката на примере. Пусть требуется найти сумму элементов списка [3,6,1]. Последовательность вызовов следующая:

sum([3|6,1],S) âûçûâàåò sum([6,1],S1) è S=S1

sum([6|1],S1) âûçûâàåò sum([1],S11) è S1=S11+6.

sum([1],S11) âûçûâàåò sum([],S111) è S11=S111+1.

sum([ ],S111) удовлетворяется, если S111 конкретизируется 0.

sum([1],S11) удовлетворяется, если S11 конкретизируется 1.

sum([6,1],S1) удовлетворяется, если S1 конкретизируется 7.

sum([3,6,1],S) удовлетворяется, если S конкретизируется 10.

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

sum(L,S):–sum1(L,0,S).

sum1([ ],S,S). % базовое правило, список пуст, сумма накоплена

sum1([H|T],S1,S):–

S2=S1+H,

sum1(T,S2,S).

Здесь используем тот же прием, что и в предикате обращения списка: используем более общий предикат sum1, имеющий дополнительный аргумент S, в котором зафиксируется результат. Декларативный смысл базового правила: если список исчерпан, то сумма накоплена, при этом конкретизируется третий аргумент.

Тот же пример:

sum1([3|6,1], 0, S) âûçûâàåò sum1([6,1], 3, S).

sum1([6|1], 3, S) âûçûâàåò sum1([1], 9, S).

sum1([1],9, S) âûçûâàåò sum1([], 10, S).

sum([ ], 10, S) удовлетворяется, если S конкретизируется 10.

Последовательность возвратов следующая:

sum1([1], 9,1 0)

sum1([6,1], 3,1 0)

sum1([3,6,1], 0, 10)

18. Нахождение максимального элемента списка Здесь нам понадобится вспомогательный предикат max, выбирающий максимальное значение из двух элементов:

max(X,Y,X):– X>=Y.

max(X,Y,Y):– X<Y.

Результативный предикат maxlist(LIST,MAX), где MAX – наибольший элемент списка LIST, выглядит следующим образом:

maxlist([X],X).

maxlist([X,Y|TAIL],MAX):–

maxlist([Y|TAIL],MAXTAIL),

max(X,MAXTAIL,MAX).

Смысл базового правила: максимальный элемент одноэлементного списка равен самому этому элементу. Иначе, если в списке есть хотя бы два элемента X и Y, выбирается максимальный элемент хвоста MAXTAIL и при этом MAX равен наибольшему из X и MAXTAIL. Рекурсия здесь нехвостовая, чтобы обеспечить конкретизацию переменных X и MAXTAIL.