Иван Братко - Программирование на языке Пролог для искусственного интеллекта

L2 = [a, b, z, z, c]

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

принадлежит1( X, L) :-

конк( L1, [X | L2], L).

Рис. 3.3. Процедура принадлежит1находит элемент в заданном списке, производя по нему последовательный поиск.

В этом предложении сказано: "X принадлежит L, если список L можно разбить на два списка таким образом, чтобы элемент X являлся головой второго из них. Разумеется, принадлежит1определяет то же самое отношение, что и принадлежит. Мы использовали другое имя только для того, чтобы различать таким образом две разные реализации этого отношения, Заметим, что, используя анонимную переменную, можно записать вышеприведенное предложение так:

принадлежит1( X, L) :-

конк( _, [X | _ ], L).

Интересно сравнить между собой эти две реализации отношения принадлежности. Принадлежитимеет довольно очевидный процедурный смысл:

Для проверки, является ли X элементом списка L, нужно

(1) сначала проверить, не совпадает ли голова списка L с X, а затем

(2) проверить, не принадлежит ли X хвосту списка L.

С другой стороны, принадлежит1, наоборот, имеет очевидный декларативный смысл, но его процедурный смысл не столь очевиден.

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

?- принадлежит1( b, [а, b, с] ).

На рис. 3.3 приведена эта запись. Из нее можно заключить, что принадлежит1ведет себя точно так же, как и принадлежит. Он просматривает список элемент за элементом до тех пор, пока не найдет нужный или пока не кончится список.

3.1. (а) Используя отношение конк, напишите цель, соответствующую вычеркиванию трех последних элементов списка L, результат — новый список L1. Указание: L — конкатенация L1 и трехэлементного списка.

(b) Напишите последовательность целей для порождения списка L2, получающегося из списка L вычеркиванием его трех первых и трех последних элементов.

3.2. Определите отношение

последний( Элемент, Список)

так, чтобы Элементявлялся последним элементом списка Список. Напишите два варианта определения: (а) с использованием отношения конк, (b) без использования этого отношения.

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

[X | L]

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

добавить( X, L, [X | L] ).

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

удалить( X, L, L1)

где L1 совпадает со списком L, у которого удален элемент X. Отношение удалитьможно определить аналогично отношению принадлежности. Имеем снова два случая:

(1) Если X является головой списка, тогда результатом удаления будет хвост этого списка.

(2) Если X находится в хвосте списка, тогда его нужно удалить оттуда.

удалить( X, [X | Хвост], Хвост).

удалить( X, [Y | Хвост], [Y | Хвост1] ) :-

удалить( X, Хвост, Хвост1).

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

?- удалить( а, [а, b, а, а], L].

L = [b, а, а];

L = [а, b, а];

L = [а, b, а];

no (нет)

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

Отношение удалитьможно использовать в обратном направлении для того, чтобы добавлять элементы в список, вставляя их в произвольные места. Например, если мы хотим во все возможные места списка [1, 2, 3] вставить атом а, то мы можем это сделать, задав вопрос: "Каким должен быть список L, чтобы после удаления из него элемента а получился список [1, 2, 3]?"

?- удалить( а, L, [1, 2, 3] ).

L = [а, 1, 2, 3];

L = [1, а, 2, 3];

L = [1, 2, а, 3];

L = [1, 2, 3, а];

nо (нет)

Вообще операция по внесению X в произвольное место некоторого списка Список, дающее в результате БольшийСписок, может быть определена предложением:

внести( X, Список, БольшийСписок) :-

удалить( X, БольшийСписок, Список).

В принадлежит1мы изящно реализовали отношение принадлежности через конк. Для проверки на принадлежность можно также использовать и удалить. Идея простая: некоторый X принадлежит списку Список, если X можно из него удалить:

принадлежит2( X, Список) :-

удалить( X, Список, _ ).

Рассмотрим теперь отношение подсписок. Это отношение имеет два аргумента — список L и список S, такой, что S содержится в L в качестве подсписка. Так отношение

подсписок( [c, d, e], [a, b, c, d, e, f] )

имеет место, а отношение

подсписок( [c, e], [a, b, c, d, e, f] )

нет. Пролог-программа для отношения подсписокможет основываться на той же идее, что и принадлежит1, только на этот раз отношение более общо (см. рис. 3.4).

Рис. 3.4. Отношения принадлежити подсписок.

Его можно сформулировать так:

S является подсписком L, если

(1) L можно разбить на два списка L1 и L2 и

(2) L2 можно разбить на два списка S и L3.

Как мы видели раньше, отношение конкможно использовать для разбиения списков. Поэтому вышеприведенную формулировку можно выразить на Прологе так:

подсписок( S, L) :-

конк( L1, L2, L),

конк( S, L3, L2).

Ясно, что процедуру подсписокможно гибко использовать различными способами. Хотя она предназначалась для проверки, является ли какой-либо список подсписком другого, ее можно использовать, например, для нахождения всех подсписков данного списка: