Интересно сравнить между собой эти две реализации отношения принадлежности.
Принадлежит
имеет довольно очевидный процедурный смысл:
Для проверки, является ли 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) без использования этого отношения.
3.2.3. Добавление элемента
Наиболее простой способ добавить элемент в список — это вставить его в самое начало так, чтобы он стал его новой головой. Если X — это новый элемент, а список, в который X добавляется — L, тогда результирующий список — это просто
[X | L]
Таким образом, для того, чтобы добавить новый элемент в начало списка, не надо использовать никакой процедуры. Тем не менее, если мы хотим определить такую процедуру в явном виде, то ее можно представить в форме такого факта:
добавить( X, L, [X | L] ).
3.2.4. Удаление элемента
Удаление элемента 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, Список, _ ).
3.2.5. Подсписок
Рассмотрим теперь отношение
подсписок
. Это отношение имеет два аргумента — список L и список S, такой, что S содержится в L в качестве подсписка. Так отношение
подсписок( [c, d, e], [a, b, c, d, e, f] )
имеет место, а отношение
подсписок( [c, e], [a, b, c, d, e, f] )
нет. Пролог-программа для отношения
подсписок
может основываться на той же идее, что и
принадлежит1
, только на этот раз отношение более общо (см. рис. 3.4).