Предикаты bagof, setof и findall

Выше было показано, что в программе можно сформировать по одному все объек­ты, соответствующие некоторой цели, с помощью перебора с возвратами. Но после выработки каждого следующего решения предыдущее удаляется и становится недос­тупным. Тем не менее иногда возникает необходимость иметь доступ сразу ко всем выработанным решениям, например, собранным в виде списка. Для этого применя­ются встроенные предикаты bagof, setof и findall.

Цель bagof ( X, Р, 1)

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

age( peter, 1) . agel ana, Ъ) . age( pat, 8). age ( torn, 5) .

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

Глава 7. Дополнительные встроенные предикаты

?- bagofI Child, age ( Child, 5), List). List = [ ana, torn)

Если в приведенной выше цели значение возраста не указано, то с помощью пере­бора с возвратами будут сформированы три списка детей, соответствующие трем зна­чениям возраста:

?- ba1oft Child, age f Child, Age!-, List).

Age = /

List = [ peter];

Age = 5

List = [ ann, torn];

Age = S

List = [ pat];

No

Может также потребоваться включить всех детей в один список, независимо от их возраста. Такую задачу можно решить, явно указав в вызове предиката bagof с по­мощью оператора "^Л", что нас не интересует значение параметра Аде; важно лишь то, что такое значение существует. Соответствующий вопрос может быть сформули­рован таким образом:

?- bagof ( Child, Age ^Л аде ( Child, Age),List). List = [ peter, ann, pat, torn]

По своей синтаксической форме знак операции "*■" представляет собой заранее определенный инфиксный оператор типа xfy.

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

Предикат setof аналогичен bagof. Цель setof{X, ?, L)

также вырабатывает список I, объектов X, которые соответствуют предикату Р. Но в данном случае список L упорядочивается, а дубликаты элементов, если они имеются, удаляются. Упорядочение объектов соответствует встроенному предикату @<, кото­рый определяет правила предшествования термов, например, следующим образом:

_s?-toiriChct'ild^ aChild,^r Ag<^.^£t)' AgeList =* [ ChTspat, peter,^t£ml

На типы объектов, собираемых в списки, не налагаются ограничения. Поэтому можно, например, сформировать список детей, отсортированный по их возрасту, со­ставив пары в форме Age/Child таким образом:

?- setof ( Age/Child, age ( Child, Age}, List! List = [ 8/arm, 5/tcm, 7/peter, 8/pat;

Еще одним предикатом из этого семейства, аналогичным bagof, является findall. Предикат findall< х, Р, L)

также вырабатывает список объектов, которые соответствуют предикату Р. Предикат findall отличается от bagof тем, что в список собираются все объекты X, независи­мо от наличия (возможно) различных решений для переменных в предикате Р, кото­рые не являются общими с объектом X. Это различие демонстрируется на следующем примере:

?- findall: Child, agef Child, Age), List). List = [ p> : ;, ann, pat, tern]

Если не существует ни один объект X, который соответствует предикату ?, то цель, заданная предикатом findall, достигается, создавая пустой список L - [ ].

Часть I. Язык Prolog

Если в используемой реализации отсутствует f indall как встроенный предикат, то его можно легко запрограммировать, как показано ниже. Все решения, соответст­вующие предикату , вырабатываются с помощью принудительного перебора с воз­вратами. Каждое решение после его выработки немедленно вносится в базу данных, чтобы оно не было потеряно после обнаружения следующего решения. Вслед за тем, как будут выработаны и внесены все решения, их необходимо собрать в список и из­влечь из базы данных. Весь этот процесс можно представить себе, как если бы все вырабатываемые решения формировали очередь. Каждое вновь выработанное реше­ние с помощью предиката внесения = = зег: добавляется к концу этой очереди, а по­сле сбора всех решений очередь ликвидируется. Следует отметить, что конец этой очереди должен быть дополнительно обозначен атомом, позволяющим узнать, где на­ходится конец очереди, например "bottom" (этот атом, безусловно, должен отличать­ся от любых решений, которые могут быть выработаны). Пример реализации findall в соответствии с этими рекомендациями приведен в листинге 7.3.