Соберите все "минимальные" решения из предиката

Question

Учитывая следующие факты в базе данных:

foo(a, 3).
foo(b, 2).
foo(c, 4).
foo(d, 3).
foo(e, 2).
foo(f, 6).
foo(g, 3).
foo(h, 2).

Я хочу собрать все первые аргументы, которые имеют наименьший второй аргумент, плюс значение второго аргумента. Первая попытка:

find_min_1(Min, As) :-
    setof(B-A, foo(A, B), [Min-_|_]),
    findall(A, foo(A, Min), As).

?- find_min_1(Min, As).
Min = 2,
As = [b, e, h].

Вместо setof/3 Я мог бы использовать aggregate/3:

find_min_2(Min, As) :-
    aggregate(min(B), A^foo(A, B), Min),
    findall(A, foo(A, Min), As).

?- find_min_2(Min, As).
Min = 2,
As = [b, e, h].

NB

Это дает те же результаты, только если я ищу минимум числа. Если задействовано арифметическое выражение, результаты могут отличаться. Если задействован не номер, aggregate(min(...), ...) выдаст ошибку!

Или вместо этого я могу использовать полный список отсортированных ключей:

find_min_3(Min, As) :-
    setof(B-A, foo(A, B), [Min-First|Rest]),
    min_prefix([Min-First|Rest], Min, As).

min_prefix([Min-First|Rest], Min, [First|As]) :-
    !,
    min_prefix(Rest, Min, As).
min_prefix(_, _, []).

?- find_min_3(Min, As).
Min = 2,
As = [b, e, h].

Наконец, на вопрос (ы):

• Могу ли я сделать это напрямую с библиотекой (агрегат)? Такое ощущение, что это должно быть возможно....

• Или есть предикат как std::partition_point из стандартной библиотеки C++?

• Или есть какой-то более простой способ сделать это?

РЕДАКТИРОВАТЬ:

Чтобы быть более наглядным. Скажем, был предикат (библиотека) partition_point/4:

partition_point(Pred_1, List, Before, After) :-
    partition_point_1(List, Pred_1, Before, After).

partition_point_1([], _, [], []).
partition_point_1([H|T], Pred_1, Before, After) :-
    (   call(Pred_1, H)
    ->  Before = [H|B],
        partition_point_1(T, Pred_1, B, After)
    ;   Before = [],
        After = [H|T]
    ).

(Мне не нравится название, но мы можем жить с ним сейчас)

Затем:

find_min_4(Min, As) :-
    setof(B-A, foo(A, B), [Min-X|Rest]),
    partition_point(is_min(Min), [Min-X|Rest], Min_pairs, _),
    pairs_values(Min_pairs, As).

is_min(Min, Min-_).

?- find_min_4(Min, As).
Min = 2,
As = [b, e, h].

Answer 1

С помощью library(pairs) а также [ sort/4 ], это можно записать так:

?- bagof(B-A, foo(A, B), Ps),
   sort(1, @=<, Ps, Ss), % or keysort(Ps, Ss)
   group_pairs_by_key(Ss, [Min-As|_]).
Min = 2,
As = [b, e, h].

Этот призыв к sort/4 можно заменить на keysort/2, но с sort/4 например, можно найти первые аргументы, связанные с наибольшим вторым аргументом: просто используйте @>= как второй аргумент.

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

Но есть и другой способ сделать это:

?- bagof(A, ( foo(A, Min), \+ ( foo(_, Y), Y @< Min ) ), As).
Min = 2,
As = [b, e, h].

Answer 2

Каков идиоматический подход к этому классу проблем?

Есть ли способ упростить проблему?

Многие из следующих замечаний могут быть добавлены во многие программы здесь, на SO.

Императивные имена

Каждый раз, когда вы пишете императивное имя для чего-то, что является отношением, вы уменьшаете свое понимание отношений. Не много, только немного. Многие распространенные идиомы Prolog, такие как append/3 Не подайте хороший пример. Думать о append(As,As,AsAs), Первый аргумент find_min(Min, As) это минимум. Так minimum_with_nodes/2 может быть лучшим именем

findall/3

Не использовать findall/3 если использование строго не проверено, по существу все должно быть измельчено. В вашем случае это работает. Но как только вы обобщите foo/2 немного, ты проиграешь. И это часто проблема: вы пишете крошечную программу; и это похоже на работу. Как только вы перейдете к более крупным, тот же подход больше не работает. findall/3 есть (по сравнению с setof/3) как бык в магазине фарфора, разбивающий тонкую ткань общих переменных и количественного определения. Другая проблема заключается в том, что случайный сбой не приводит к отказу findall/3 что часто приводит к странным, трудно представить себе угловые случаи.

Нестабильная, слишком конкретная программа

Другая проблема в некоторой степени связана с findall/3, тоже. Ваша программа настолько специфична, что маловероятно, что вы когда-нибудь ее протестируете. И незначительные изменения сделают ваши тесты недействительными. Так что вы скоро сдадитесь для проведения тестирования. Давайте посмотрим, что конкретно: в первую очередь foo/2 связь. Да, только пример. Подумайте, как настроить тестовую конфигурацию, где foo/2 может поменяться. После каждого изменения (записи нового файла) вам придется перезагрузить программу. Это так сложно, скорее всего, вы никогда этого не сделаете. Я полагаю, у вас нет тестовой оснастки для этого. Плунит за одного, не распространяется на такое тестирование. Практическое правило. Если вы не можете проверить предикат на верхнем уровне, вы никогда этого не сделаете. Рассмотрим вместо

minimum_with(Rel_2, Min, Els)

С таким отношением вы можете теперь иметь обобщенный xfoo/3 с дополнительным параметром, скажем:

xfoo(o, A,B) :-
   foo(A,B).
xfoo(n, A,B) :-
   newfoo(A,B).

и вы, естественно, получите два ответа на minimum_with(xfoo(X), Min, Els), Вы бы использовали findall/3 вместо setof/3 у вас уже будут серьезные проблемы. Или просто в общем minmum_with(\A^B^member(A-B, [x-10,y-20]), Min, Els), Таким образом, вы можете поиграть на верхнем уровне и создать множество интересных тестовых случаев.

Неограниченные пограничные случаи

Ваша версия 3 - это мой предпочтительный подход, однако есть некоторые детали, которые можно улучшить. В частности, если есть ответы, которые содержат переменные как минимум. Это должно быть проверено.

И, конечно же, также setof/3 имеет свои пределы. И в идеале вы бы их протестировали. Ответы не должны содержать ограничений, в частности, не в соответствующих переменных. Это показывает, как setof/3 само по себе имеет определенные ограничения. После начального этапа SICStus выдавал много ошибок для ограничений в таких случаях (середина 1990-х годов), которые впоследствии были изменены, чтобы впоследствии игнорировать ограничения во встроенных модулях, которые не могут их обработать. SWI, с другой стороны, делает здесь совершенно неопределенные вещи. Иногда вещи копируются, иногда нет. В качестве примера возьмем:setof(A, ( A in 1..3 ; A in 3..5 ), _) а также setof(t, ( A in 1..3 ; A in 3.. 5 ), _),

Оборачивая цель, этого можно избежать.

call_unconstrained(Goal_0) :-
   call_residue_vars(Goal_0, Vs),
   ( Vs = [] -> true ; throw(error(representation_error(constraint),_)) ).

Остерегайтесь, однако, что у SWI есть ложные ограничения:

?- call_residue_vars(all_different([]), Xs).
Xs = [_G1130].

Не ясно, если это особенность в то же время. Это было там с момента введения call_residue_vars/2 около 5 лет назад.

Answer 3

Я не думаю, что библиотека (агрегат) покрывает ваш вариант использования. агрегат (мин) учитывает одного свидетеля:

min (Expr, Witness) Термин min(Min, Witness), где Min - минимальная версия Expr для всех решений, а Witness - любой другой шаблон, применяемый к решениям, которые дали Min. Если несколько решений обеспечивают одинаковый минимум, Witness соответствует первому решению.

Некоторое время назад я написал небольшую "библиотеку", lag.pl, с предикатами для агрегирования с низкими издержками - отсюда и название (LAG = Linear AGgregate). Я добавил фрагмент, который обрабатывает ваш вариант использования:

integrate(min_list_associated, Goal, Min-Ws) :-
    State = term(_, [], _),
    forall(call(Goal, V, W),    % W stands for witness
        (    arg(1, State, C),  % C is current min
             arg(2, State, CW), % CW are current min witnesses
             (   ( var(C) ; V @< C )
             ->  U = V, Ws = [W]
             ;   U = C,
                 (   C == V
                 ->  Ws = [W|CW]
                 ;   Ws = CW
                 )
             ),
             nb_setarg(1, State, U),
             nb_setarg(2, State, Ws)
        )),
    arg(1, State, Min), arg(2, State, Ws).

Это простое расширенное интегрирование (min)... Метод сравнения, который, несомненно, сомнителен (он использует менее общий оператор для равенства), может стоить принять вместо обычного вызова, подобного тому, который принят для predsort/ 3. По эффективности, еще лучше было бы закодировать метод сравнения в качестве опции в "селекторе функций" (в этом случае min_list_associated)

edit Спасибо @false и @Boris за исправление ошибки, связанной с представлением состояния. призвание nb_setarg(2, State, Ws) на самом деле меняет форму термина, когда State = (_,[],_) использовался. Будем обновлять репозиторий github соответственно...