Сбор всех решений: findall, bagof, setof

Бэктрекинг выдаёт решения по одному — а что, если они нужны все сразу в виде списка?

findall(Шаблон, Цель, Список) — предикат, который перебирает все доказательства Цель и собирает соответствующие значения Шаблон в один список Список.

В предыдущих разделах мы привыкли получать ответы интерактивно: задаём вопрос, видим первое решение, нажимаем ; — Prolog откатывается и ищет следующее. Это удобно для исследования, но бесполезно, когда решения нужно посчитать, отсортировать, сложить или передать другому предикату. Бэктрекинг живёт «снаружи», в цикле взаимодействия, а внутри программы у вас на руках всегда лишь одно текущее решение. Группа предикатов findall/3, bagof/3, setof/3 и aggregate_all/3 закрывает этот разрыв: они материализуют весь набор решений в обычную структуру данных — список, с которым дальше можно работать привычными средствами.

findall/3 — самый простой и предсказуемый

Возьмём базу фактов о возрасте учеников и соберём всех в список.

age(anna, 14).
age(boris, 15).
age(vera, 14).
age(grigoriy, 16).

?- findall(Name, age(Name, _), Names).
Names = [anna, boris, vera, grigoriy].

Шаблон не обязан быть просто переменной — это любой терм. Хотите пары «имя-возраст»? Поставьте в шаблон структуру:

?- findall(Name-Age, age(Name, Age), Pairs).
Pairs = [anna-14, boris-15, vera-14, grigoriy-16].

Ключевое свойство findall/3: если у цели нет ни одного решения, результатом будет пустой список [], а сам предикат успешно завершится. Это делает его самым безопасным выбором по умолчанию.

?- findall(N, age(N, 99), L).
L = [].

bagof/3 — то же, но с группировкой

bagof/3 внешне похож на findall/3, но ведёт себя иначе в двух местах. Во-первых, на пустом наборе решений он не возвращает [], а просто терпит неудачу (fail). Во-вторых, свободные переменные в цели, не упомянутые в шаблоне, он трактует как параметры группировки и перебирает их по бэктрекингу.

likes(anna, math).
likes(anna, music).
likes(boris, math).
likes(boris, sport).

?- bagof(What, likes(Who, What), List).
Who = anna, List = [math, music] ;
Who = boris, List = [math, sport].

Видите? Вместо одного длинного списка bagof выдал по группе на каждое значение Who. Если такая группировка не нужна и переменную Who хочется «забыть», её экранируют оператором ^:

?- bagof(What, Who^likes(Who, What), List).
List = [math, music, math, sport].

Конструкция Who^Цель читается как «существует такой Who, что выполняется Цель» — нам всё равно, кто именно, важен лишь сам факт.

setof/3 — отсортировано и без дубликатов

setof/3 — это bagof/3, к результату которого применили сортировку по стандартному порядку термов и удаление повторов. Сравните: в примере выше math встречался дважды. С setof он будет один раз, а список отсортирован.

?- setof(What, Who^likes(Who, What), List).
List = [math, music, sport].

Как и bagof, на пустом наборе setof терпит неудачу. Это удобно, когда «нет решений» должно означать провал ветки, а не пустой список.

aggregate_all — посчитать, не собирая список вручную

Часто список как таковой не нужен — нужно лишь количество или сумма. Тогда вместо findall + length пишут aggregate_all/3.

?- aggregate_all(count, age(_, _), N).
N = 4.

?- aggregate_all(sum(A), age(_, A), Total).
Total = 59.

?- aggregate_all(max(A), age(_, A), Max).
Max = 16.

Это и лаконичнее, и эффективнее по памяти: накопитель обновляется на лету, без построения промежуточного списка.

Как работает под капотом

Все эти предикаты используют один и тот же трюк — управляемый бэктрекинг с побочной фиксацией результатов. Концептуально findall(T, G, L) делает следующее: заводит пустой буфер, запускает цель G, при каждом успехе берёт копию текущего значения T (с переименованными переменными, чтобы они не «утекли») и дописывает в буфер, затем принудительно вызывает откат, словно пользователь нажал ;. Когда решения исчерпаны и цель окончательно проваливается, перебор останавливается, а буфер превращается в список L. Принципиально, что после findall переменные самой цели остаются несвязанными — наружу выходит только готовый список. Именно поэтому findall «всеяден»: ему безразлично, сколько решений и какие переменные внутри.

findall(T, Goal, L) :-
    собрать_в_буфер(T, Goal),   % Goal с откатами, копии T в скрытый буфер
    извлечь_буфер(L).            % буфер -> готовый список

bagof/3 и setof/3 устроены сложнее: они сначала находят свободные переменные шаблона и цели (не зачёркнутые через ^), затем фактически вызывают findall по парам «набор-свободных-переменных + значение» и группируют результат. Поэтому они и перебирают группы, и проваливаются на пустоте — пустых групп просто не возникает.

Частые ошибки

• Ждать [] от bagof/setof. На пустом наборе они проваливаются. Если нужен гарантированный список (возможно пустой) — берите findall/3.
• Забыть экранировать свободную переменную через ^. Тогда bagof/setof неожиданно разбивают результат на группы по этой переменной вместо одного списка.
• Слишком общий шаблон. Если в шаблон попала переменная, не связанная целью, вы соберёте список несвязанных переменных [_G1, _G2, ...] — почти всегда не то, что хотелось.
• findall + length вместо aggregate_all. Для подсчёта это лишний промежуточный список; aggregate_all(count, ...) и яснее, и экономнее.

Итоги

• findall(Шаблон, Цель, Список) собирает все решения; на пустом наборе даёт [] и успешно завершается.
• bagof/3 похож, но проваливается на пустоте и группирует по свободным переменным; ^ экранирует переменную.
• setof/3 — как bagof, но сортирует результат и убирает дубликаты.
• aggregate_all/3 считает count/sum/max и т.п. без построения списка вручную.
• Под капотом все они — это перебор с откатами, фиксирующий копии решений в скрытый буфер.