Назад | Содержание| Вперёд 7. 6. findall...

Назад | Содержание| Вперёд

7. 6. bagof , setof и findall

При помощи механизма автоматического перебораможно получить одни за другим все объекты,удовлетворяющие некоторой цели. Всякий раз, какпорождается новое решение, предыдущеепропадает и становится с этого моментанедоступным. Однако у нас может возникнуть желание получить доступ ко всемпорожденным объектам сразу, например собравих в список. Встроенные предикаты bagof(набор) и setof (множество) обеспечиваюттакую возможность; вместо них иногда используютпредикат findall (найти все).

Цель

bagof( X, P, L)

порождает список L всех объектов X,удовлетворяющих цели Р. Обычно bagof имеетсмысл применять только тогда, когда Х и Рсодержат общие переменные. Например, допустим,что мы включили в программу следующую группупредложений для разбиения букв (из некоторогомножества) на два класса - гласные и согласные:

класс( а, глас).

класс( b, согл).

класс( с, согл).

класс( d, согл).

класс( е, глас).

класс( f, согл).

Тогда мы можем получить список всех согласных,упомянутых в этих предложениях, при помощи цели:

?- bagof( Буква,класс( Буква, согл), Буквы).

Буквы = [d, c, d, f]

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

?- bagof( Буква,класс( Буква, Класс), Буквы).

Класс = глас

Буквы = [а,е]

Класс = согл

Буквы = [b, c, d, f]

Если bagof( X, Р, L) не находит ни одногорешения для Р, то цель bagofпросто терпит неуспех. Если один и тот же Х найденмногократно, то все его экземпляры будутзанесены в L, что приведет к появлению в Lповторяющихся элементов.

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

setof( X, P, L)

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

Класс / Буква

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

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

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

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

findall( X, P, L)

тоже порождает список объектов,удовлетворяющих Р. Он отличается от bagofтем, что собирает в список все объекты X, необращая внимание на (возможно) отличающиеся дляних конкретизации тех переменных из P, которыхнет в X. Это различие видно из следующего примера:

?- findall( Буква,класс( Буква, Класс), Буквы).

Буквы= [a, b, c, d, e, f]

Если не существует ни одного объекта X,удовлетворяющего P, то findall все равноимеет успех и выдает L = [ ].

Если в используемой реализации Прологаотсутствует встроенный предикат findall,то его легко запрограммировать следующимобразом. Все решения для Р порождаютсяискусственно вызываемыми возвратами. Каждоерешение, как только оно получено, немедленнодобавляется к базе данных, чтобы не потерять егопосле нахождения следующего решения. После того,как будут получены и сохранены все решения, ихнужно собрать в список, а затем удалить из базыданных при помощи retract. Весь процессможно представлять себе как построение очередииз порождаемых решений. Каждое вновь порождаемоерешение добавляется в конец этой очереди припомощи assert. Когда все решения собраны,очередь расформировывается. Заметим также, чтоконец очереди надо пометить, например, атомом"дно" (который, конечно, должен отличаться отлюбого ожидаемого решения). Реализация findallв соответствии с описанным методом показана нарис. 7.4.

findall( X, Цель, ХСпис) :-

саll( Цель), % Найти решение

assert( очередь( X) ), %Добавить егo

fail; % Попытаться найти еще решения

assertz( очередь( дно) ),

% Пометить конец решений

собрать( ХСпис). % Собрать решения в список

собрать( L) :-

retract( очередь(Х) ), !,

% Удалить следующее решение

( Х == дно, !, L = [ ];

% Конец решений?

L = [X | Остальные], собрать(Остальные) ).

% Иначе собрать остальные

Рис. 7. 4. Реализацияотношения findall.

Упражнения

7. 8. Используя bagof,определите отношение

множподмножеств(Мн, Подмн)

для вычисления множества всех подмножествданного множества (все множества представленысписками).

7. 9. Используя bagof,определите отношение

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

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

Резюме

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

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

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

nonvar( X) Х - не переменная

atom( X) Х - атом

integer( X) Х - целое

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

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

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

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

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

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

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

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

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

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

rеtrасt( Предл) удаляет предложение,

сопоставимое с предложением Предл

Все объекты, отвечающие некоторому заданному условию, можно собрать в список при помощи предикатов:

bagof( X, Р, L) L - список всех X, удовлетворяющих условию Р

setof( X, Р, L) L - отсортированный список всех X,

удовлетворяющих условию Р

findall( X, Р, L) аналогичен bagof

repeat - средство управления, позволяющее порождать неограниченное число альтернатив для автоматического перебора.

Назад | Содержание| Вперёд

Оглавление