Нахождение максимального элемента списка.

ОПЕРАЦИИ НАД СПИСКАМИ И АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ

Имеем два случая:

- если X - голова списка, то результат удаления - хвост списка;

- если X - в хвосте списка, то его нужно удалить оттуда.

В результате отношение remove (удаления) определяется так:

remove(X,[X|Tail],Tail).

remove(X,[Y|Tail],[Y|Tail1]) :- remove(X,Tail,Tail1).

Если в списке встречается несколько вхождений элемента X, то remove сможет исключить их все при помощи возвратов.

Также удаление элемента 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).

Выборка упорядоченных пар из двух списков.

Определим отношение much с четырьмя аргументами:

much(X1,X2,L1,L2).

Аргументы X1,X2 - это элементы соответственно списков L1 и L2. Списки L1 и L2 одинаковой длины.

Это отношение также можно определить аналогично отношению принадлежности: либо X1 есть голова списка L1 и X2 - голова списка L2, либо продолжить выборку пары X1 и X2 из хвостовой части списков L1 и L2 соответственно, т.е.

much(X1,X2, [X1|_], [X2|_]).

much(X1,X2, [_|T1], [_|T2]):- much(X1,X2,T1,T2).

Предикат используют для возможных сочетаний конкретизации переменных X1 и X2, при этом списки L1 и L2 обычно конкретизированы. Если X1 и X2 неконкретизированы, предикат отвечает своему названию и выбирает пары посредством механизма возвратов. Если X1 конкретизирована, а X2 нет, предикат выбирает из списка L2 элемент, соответствующий X1 в L1 по порядку.

Удаление из списка повторяющихся элементов.

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

unik([],[]).

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

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

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

Определим предикат

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 становится уже достаточно общим, чтобы его можно было определить рекурсивно. На каждом шаге рекурсии один элемент исходного списка становится головой промежуточного списка. Третий аргумент передается от шага к шагу и конкретизируется в момент достижения базового состояния предиката reverse1. Когда первый список исчерпан, второй уже содержит элементы, записанные в обратном порядке. Отметим, что наличие третьего аргумента, фиксирующего результат, обязательно, т.к. после обратного прохождения рекурсии все конкретизированные переменные принимают свои первоначальные значения.

Вычисление суммы элементов списка.

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

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 рекурсивное условие записано не последним.

Расcмотрим работу этого предиката на примере:

sum([3|6,1],S) вызывает sum([6,1],S1) и S=S1+3.

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)

Нахождение максимального элемента списка.

Здесь нам понадобится вспомогательный предикат 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.