При помощи механизма автоматического перебора можно получить одни за другим все объекты, удовлетворяющие некоторой цели. Всякий раз, как порождается новое решение, предыдущее пропадает и становится с этого момента недоступным. Однако у нас может возникнуть желание получить доступ ко всем порожденным объектам сразу, например собрав их в список. Встроенные предикаты
bagof
(набор) и
setof
(множество) обеспечивают такую возможность; вместо них иногда используют предикат
findall
(найти
все).
Цель
bagof( X, P, L)
порождает список L всех объектов X, удовлетворяющих цели P. Обычно
bagof
имеет смысл применять только тогда, когда X и P содержат общие переменные. Например, допустим, что мы включили в программу следующую группу предложений для разбиения букв (из некоторого множества) на два класса — гласные и согласные:
класс( а, глас).
класс( b, согл).
класс( с, согл).
класс( d, согл).
класс( e, глас).
класс( f, согл).
Тогда мы можем получить список всех согласных, упомянутых в этих предложениях, при помощи цели:
?- bagof( Буква, класс( Буква, согл), Буквы).
Буквы = [d, c, d, f]
Если же мы в указанной цели оставим класс букв неопределенным, то, используя автоматический перебор, получим два списка букв, каждый из которых соответствует одному из классов:
?- bagof( Буква, класс( Буква, Класс), Буквы).
Класс = глас
Буквы = [а,e]
Класс = согл
Буквы = [b, c, d, f]
Если
bagof( X, P, L)
не находит ни одного решения для
P
, то цель
bagof
просто терпит неуспех. Если один и тот же X найден многократно, то все его экземпляры будут занесены в
L
, что приведет к появлению в
L
повторяющихся элементов.
Предикат
setof
работает аналогично предикату
bagof
. Цель
setof( X, P, L)
как и раньше, порождает список L объектов X, удовлетворяющих P. Только на этот раз список L будет упорядочен, а из всех повторяющихся элементов, если таковые есть, в него попадет только один. Упорядочение происходит по алфавиту или по отношению '
<
', если элементы списка — числа. Если элементы списка — структуры, то они упорядочиваются по своим главным функторам. Если же главные функторы совпадают, то решение о порядке таких термов принимается по их первым несовпадающим функторам, расположенным выше и левее других (по дереву). На вид объектов, собираемых в список, ограничения нет. Поэтому можно, например, составить список пар вида
Класс / Буква
при этом гласные будут расположены в списке первыми ("глас" по алфавиту раньше "согл"):
тем, что собирает в список все объекты X, не обращая внимание на (возможно) отличающиеся для них конкретизации тех переменных из P, которых нет в X. Это различие видно из следующего примера:
?- findall( Буква, класс( Буква, Класс), Буквы).
Буквы = [a, b, c, d, e, f]
Если не существует ни одного объекта X, удовлетворяющего P, то
findall
все равно имеет успех и выдает
L = []
.
Если в используемой реализации Пролога отсутствует встроенный предикат
findall
, то его легко запрограммировать следующим образом. Все решения для P порождаются искусственно вызываемыми возвратами. Каждое решение, как только оно получено, немедленно добавляется к базе данных, чтобы не потерять его после нахождения следующего решения. После того, как будут получены и сохранены все решения, их нужно собрать в список, а затем удалить из базы данных при помощи
retract
. Весь процесс можно представлять себе как построение очереди из порождаемых решений. Каждое вновь порождаемое решение добавляется в конец этой очереди при помощи
assert
. Когда все решения собраны, очередь расформировывается. Заметим также, что конец очереди надо пометить, например, атомом "дно" (который, конечно, должен отличаться от любого ожидаемого решения). Реализация
findall
в соответствии с описанным методом показана на рис. 7.4.
findall( X, Цель, ХСпис) :-
саll( Цель), % Найти решение
assert( очередь( X) ), % Добавить егo
fail; % Попытаться найти еще решения
assertz( очередь( дно) ),
% Пометить конец решений
собрать( ХСпис). % Собрать решения в список
собрать( L) :-
retract( очередь(X) ), !,
% Удалить следующее решение
( X == дно, !, L = [];
% Конец решений?
L = [X | Остальные], собрать( Остальные) ).
% Иначе собрать остальные
Рис. 7.4. Реализация отношения findall.
Упражнения
7.8. Используя
bagof
, определите отношение
множподмножеств( Мн, Подмн)
для вычисления множества всех подмножеств данного множества (все множества представлены списками).
7.9. Используя
bagof
, определите отношение
копия( Терм, Копия)
чтобы
Копия
представляла собой
Терм
, в котором все переменные переименованы.
Резюме
• В любой реализации Пролога обычно предусматривается набор встроенных процедур для выполнения различных полезных операций, несуществующих в чистом Прологе. В данной главе мы рассмотрели подобное множество предикатов, имеющееся во многих реализациях.