• проверка, является ли некоторый объект элементом списка, что соответствует проверке объекта на принадлежность множеству;
• конкатенация (сцепление) двух списков, что соответствует объединению множеств;
• добавление нового объекта в список или удаление некоторого объекта из него.
В оставшейся части раздела мы покажем программы, реализующие эти и некоторые другие операции над списками.
3.2.1. Принадлежность к списку
Мы представим отношение принадлежности как
принадлежит( X, L)
где X — объект, а L — список. Цель
принадлежит( X, L)
истинна, если элемент X встречается в L. Например, верно что
принадлежит( b, [а, b, с] )
и, наоборот, не верно, что
принадлежит b, [а, [b, с] ] )
но
принадлежит [b, с], [а, [b, с]] )
истинно. Составление программы для отношения принадлежности может быть основано на следующих соображениях:
(1) X есть голова L, либо
(2) X принадлежит хвосту L.
Это можно записать в виде двух предложений, первое из которых есть простой факт, а второе — правило:
принадлежит( X, [X | Хвост ] ).
принадлежит ( X, [Голова | Хвост ] ) :-
принадлежит( X, Хвост).
3.2.2. Сцепление (конкатенация)
Для сцепления списков мы определим отношение
конк( L1, L2, L3)
Здесь L1 и L2 — два списка, a L3 — список, получаемый при их сцеплении. Например,
конк( [а, b], [c, d], [a, b, c, d] )
истинно, а
конк( [а, b], [c, d], [a, b, a, c, d] )
ложно. Определение отношения
конк
, как и раньше, содержит два случая в зависимости от вида первого аргумента L1:
(1) Если первый аргумент пуст, тогда второй и третий аргументы представляют собой один и тот же список (назовем его L), что выражается в виде следующего прологовского факта:
конк( [], L, L ).
(2) Если первый аргумент отношения
конк
не пуст, то он имеет голову и хвост в выглядит так:
[X | L1]
На рис. 3.2 показано, как производится сцепление списка
[X | L1]
с произвольным списком L2. Результат сцепления — список
[X | L3]
, где L3 получен после сцепления списков L1 и L2. На прологе это можно записать следующим образом:
конк( [X | L1, L2, [X | L3]):-
конк( L1, L2, L3).
Рис. 3.2. Конкатенация списков.
Составленную программу можно теперь использовать для сцепления заданных списков, например:
?- конк( [a, b, с], [1, 2, 3], L ).
L = [a, b, c, 1, 2, 3]
?- конк( [а, [b, с], d], [а, [], b], L ).
L = [a, [b, c], d, а, [], b]
Хотя программа для
конк
выглядит довольно просто, она обладает большой гибкостью и ее можно использовать многими другими способами. Например, ее можно применять как бы в обратном направлении для разбиения заданного списка на две части:
?- конк( L1, L2, [а, b,
с] ).
L1 = []
L2 = [а, b, c];
L1 = [а]
L2 = [b, с];
L1 = [а, b]
L2 = [c];
L1 = [а, b, с]
L2 = [];
no
(нет)
Список
[а, b, с]
разбивается на два списка четырьмя способами, и все они были обнаружены нашей программой при помощи механизма автоматического перебора.
Нашу программу можно также применить для поиска в списке комбинации элементов, отвечающей некоторому условию, задаваемому в виде шаблона или образца. Например, можно найти все месяцы, предшествующие данному, и все месяцы, следующие за ним, сформулировав такую цель:
?- конк( До, [май | После ],
[янв, фев, март, апр, май, июнь,
июль, авг, сент, окт, ноябрь, дек]).
До = [янв, фев, март, апр]
После = [июнь, июль, авг, сент, окт, ноябрь, дек].
Далее мы сможем найти месяц, непосредственно предшествующий маю, и месяц, непосредственно следующий за ним, задав вопрос:
?- конк( _, [Месяц1, май, Месяц2 | _ ],
[янв, февр, март, апр, май, июнь,
июль, авг, сент, окт, ноябрь, дек]).
Месяц1 = апр
Месяц2 = июнь
Более того, мы сможем, например, удалить из некоторого списка L1 все, что следует за тремя последовательными вхождениями элемента z в L1 вместе с этими тремя z. Например, это можно сделать так:
?- L1 = [a, b, z, z, c, z, z, z, d, e],
конк( L2, [z, z, z | _ ], L1).
L1 = [a, b, z, z, c, z, z, z, d, e]
L2 = [a, b, z, z, c]
Мы уже запрограммировали отношение принадлежности. Однако, используя
конк
, можно было бы определить это отношение следующим эквивалентным способом:
принадлежит1( X, L) :-
конк( L1, [X | L2], L).
Рис. 3.3. Процедура
принадлежит1
находит элемент в заданном списке, производя по нему последовательный поиск.
В этом предложении сказано: "X принадлежит L, если список L можно разбить на два списка таким образом, чтобы элемент X являлся головой второго из них. Разумеется,
принадлежит1
определяет то же самое отношение, что и
принадлежит
. Мы использовали другое имя только для того, чтобы различать таким образом две разные реализации этого отношения, Заметим, что, используя анонимную переменную, можно записать вышеприведенное предложение так: