У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

следомза(Х,Y,[_|Z]):- следомза(Х,Y,Z).

Объединение списков: С приводимым примером мы уже встречались ранее в разд. 3.6. Цель присоединить(X, Y, Z)согласуется с базой данных в том случае, если Z– это список, построенный путем добавления Yв конец X. Например,

?- присоединить([a,b,с],[d,e,f],Q).

Q=[a,b,c,d,e,f]

Определение предиката присоединитьвыглядит следующим образом:

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

присоединить([Х|L1],L2,[Х|LЗ]):- присоединить(L1,L2,LЗ).

Граничное условие выполняется тогда, когда первый аргумент является пустым списком. Действительно, пополнение какого-либо списка пустым списком не изменяет его. В дальнейшем мы постепенно приближаемся к граничному условию, поскольку каждое рекурсивное обращение к присоединитьудаляет один элемент из головы первого аргумента.

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

последний(Е1,Список):- присоединить(_,[Е1],Список).

следомза(Е11,Е12,Список):-

присоединить(_,[Е11,Е12|_], Список).

принадлежит(Е1,Список):- присоединить(_,[Е1|_],Список).

Обращение списка: Цель обр(L,M)согласуется с базой данных, если результат перестановки в обратном порядке элементов списка Lесть список М. В программе используется стандартный прием, когда обращенный список получается присоединением его головы к обращенному хвосту. Лучший способ обратить хвост – это использовать сам обр.Граничное условие выполняется тогда, когда первый аргумент сократился до пустого списка, в этом случае результатом также является пустой список:

обр([],[]).

обр([Н|Т],L):- обр(T,Z), присоединить(Z,[Н],L).

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

o6p2(L1,L2):- обрдоп(L1,[],L2).

обрдоп([X|L],L2 fL3):- обрдоп(L,[Х|L2],LЗ).

обрдоп([],L,L).

Второй аргумент обрдописпользуется для хранения «текущего результата». Каждый раз, когда выявляется новый фрагмент результата (X), передаваемый в остальную часть программы, «текущий результат» представляет из себя старый «текущий результат», дополненный новым фрагментом X. В самом конце последний «текущий результат» возвращается в качестве результата исходного целевого утверждения. Аналогичный прием используется в разд. 7.8 при определении предиката имя_целого.

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

исключ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: