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

Предикат setofработает аналогично предикату bagof. Цель

setof( X, P, L)

как и раньше, порождает список L объектов X, удовлетворяющих P. Только на этот раз список L будет упорядочен, а из всех повторяющихся элементов, если таковые есть, в него попадет только один. Упорядочение происходит по алфавиту или по отношению ' <', если элементы списка — числа. Если элементы списка — структуры, то они упорядочиваются по своим главным функторам. Если же главные функторы совпадают, то решение о порядке таких термов принимается по их первым несовпадающим функторам, расположенным выше и левее других (по дереву). На вид объектов, собираемых в список, ограничения нет. Поэтому можно, например, составить список пар вида

Класс / Буква

при этом гласные будут расположены в списке первыми ("глас" по алфавиту раньше "согл"):

?- setof( Класс/Буква, класс( Буква, Класс), Спис).

Спис = [глас/а, глас/e, согл/b, согл/с, согл/d, согл/f]

Еще одним предикатом этого семейства, аналогичным bagof, является findall.

findall( X, P, L)

тоже порождает список объектов, удовлетворяющих P. Он отличается от bagofтем, что собирает в список все объекты 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, определите отношение

копия( Терм, Копия)

чтобы Копияпредставляла собой Терм, в котором все переменные переименованы.

• В любой реализации Пролога обычно предусматривается набор встроенных процедур для выполнения различных полезных операций, несуществующих в чистом Прологе. В данной главе мы рассмотрели подобное множество предикатов, имеющееся во многих реализациях.

• Тип терма можно установить при помощи следующих предикатов:

var( X) X — (неконкретизированная) переменная

nonvar( X) X — не переменная

atom( X) X — атом

integer( X) X — целое

atomic( X) X — или атом, или целое

• Термы можно синтезировать или разбирать на части:

Терм =.. [Функтор [ СписокАргументов]

functor( Терм, Функтор, Арность)

arg( N, Терм, Аргумент)

name( атом, КодыСимволов)

• Программу на Прологе можно рассматривать как реляционную базу данных, которую можно изменять при помощи следующих процедур:

аssert( Предл) добавляет предложение Предлк программе

аssеrtа( Предл) добавляет в начало

assertz( Предл) добавляет в конец