Программирование на языке пролог

empty-line />

исключ1(А,[А|L],L):-!.

исключ1(А,[В|L],[В|М]):- исключ1(А,L,М).

Легко добавить утверждение, которое обеспечит доказательство предиката, когда второй аргумент сократится до пустого списка. Это утверждение, реализующее новое граничное условие, есть исключ1(_,[],[])-

Исключение всех вхождений некоторого элемента;Цель исключить(Х, L1, L2)создает список L2путем удаления всех элементов Xиз списка L1. Граничное условие выполняется тогда, когда L1является пустым списком. Это означает, что мы рекурсивно исчерпали весь список. Если Xнаходится в голове списка, то результатом является хвост этого списка, из которого Xтоже удаляется. Последний случай возникает, если во втором аргументе обнаружено, что-то отличное от X. Тогда мы просто входим в новую рекурсию.

исключить(_, [],[]).

исключить(Х,[Х|L],М):-!, исключить(Х,L,М).

исключить(Х,[Y|L1],[Y|L2]):- исключить(Х,L1,L2).

Замещение:Этот предикат очень напоминает исключить,с той лишь разницей, что вместо удаления искомого элемента мы заменяем его некоторым другим элементом. Цель заменить(Х, L,A,M)строит новый список Миз элементов списка L, при этом все элементы Xзаменяются на элементы А. Здесь возможны 3 случая. Первый, связанный с граничным условием, в точности совпадает с тем, что было в исключить.Второй случай – когда в голове второго аргумента содержится элемент X, а третий – когда там содержится нечто отличное от X:

заменить(_,[],_,[]).

заменить(Х,[Х|L],А,[А|М]):-!, заменить(Х,L,А,М).

заменить(Х,[Y|L],А,[Y|М]):- заменить(Х,L,А,М).

Подсписки:Список Xявляется подсписком списка Y, если каждый элемент Xсодержится и в Yс сохранением порядка следования и без разрывов. Например, доказуемо следующее:

подсписок[[собрание, членов, клуба],[общее, собрание, членов, клуба, будет, созвано, позже]).

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

подсписок([Х|L],[Х|М]):- совпало(L,M),!.

подсписок(L,[_|М]):- подсписок(L,M).

совпало([],_).

совпало([Х|L],[Х|М]):- совпало(L,М).

Отображение:Это мощный метод, заключающийся в преобразовании одного списка в другой с применением к каждому элементу первого списка некоторой функции и использованием ее результата в качестве очередного элемента второго списка. Программа преобразования одного предложения в другое, которая рассматривалась в гл. 3, является одним из примеров отображения. Мы говорим, что «отображаем одно предложение в другое».

Отображение настолько полезно, что заслуживает отдельного раздела. Кроме того, поскольку списки в Прологе – это просто частные случаи структур, мы отложим обсуждение отображения списков до разд. 7.12. Отображение многолико. В разд. 7.11, посвященном символическому дифференцированию, описывается способ отображения одного арифметического выражения в другие.

7.6. Представление и обработка множеств

Множество– одна из наиболее важных структур данных, используемых как в математике, так и в программировании. Множество – это набор элементов, напоминающий список, но отличающийся тем, что вопрос о том, сколько раз и в каком месте что-либо входит в множество в качестве его элемента, не имеет смысла. Так, множество (1, 2, 3) – это то же самое множество, что и (1, 2, 3, 1), поскольку значение имеет только сам факт, принадлежит данный элемент множеству или нет. Элементами множеств могут также быть другие множества. Самой фундаментальной операцией над множествами является определение того, принадлежитнекоторый элемент данному множеству или нет.

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

Над множествами обычно определяется следующий набор операций (мы будем применять и общепринятые математические обозначения для тех читателей, кто к ним привык):

Принадлежность множеству: XY

Xпринадлежит некоторому множеству Y, если Xявляется одним из элементов Y.

Пример: а{с,а,t}.

Включение: X Y

Множество Yвключает в себя множество X, если каждый элемент множества Xявляется также элементом Y. Множество Yможет содержать некоторые элементы, которых нет в X.

Пример: {x,r,u} {p,q,r,f,t,u,v,w,x,y,z}.

Пересечение: XY

Пересечением множеств Xи Yявляется множество, содержащее те элементы, которые одновременно принадлежат Xи Y.

Пример: {r,a,p,i,d} {p,i,c,t,u,r,e}= {r,i,p}.

Объединение: X Y

Объединением множеств Xи Yявляется множество, содержащее все элементы, принадлежащие Xили Yили одновременно им обоим.

Пример: {a,b,c} {с,d,е} = {a,b,c,d,e}.

Это – основные операции, которые обычно используются при работе с множествами. Теперь мы можем приступить к написанию Пролог-программ, реализующих каждую из них. Первая основная операция 'принадлежность' реализуется тем же самым предикатом принадлежит, с которым мы уже встречались несколько раз. Однако в нашем определении принадлежитв граничном случае нет символа «отсечения», поэтому мы можем создавать последовательные элементы списка, используя возвратный ход:

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

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

Следующая операция 'включение' реализуется предикатом включает, причем включает(Х, Y)завершается успешно, если Xявляется подмножеством Y, т. е. Yвключает X. Второе утверждение в его определении опирается на математическое соглашение о том, что пустое множество является подмножеством любого множества. В Прологе это соглашение дает способ проверки граничного условия для первого аргумента, поскольку запрограммирована рекурсивная обработка его хвоста:

включает([А|Х],Y):- принадлежит(А,Y), включает(Х,Y).

включает([],Y).

Следом идет самый сложный случай, реализация пересечения. Целевое утверждение пересечение(Х, Y,Z) доказуемо, если пересечением Xи Yявляется Z. Это как раз тот случай, когда используется предположение, что данные списки не содержат повторяющихся элементов:

пересечение([], X, []).

пересечение([X|R],Y,[X|Z]):-принадлежит(Х, Y),!,пересечение(R, Y,Z).