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

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

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].

Примечание

Это дает те же результаты только в том случае, если я ищу минимум числа. Если задействовано арифметическое выражение, результаты могут быть другими. Если задействовано не число, 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].

backtracking prolog meta-predicate aggregates prolog-setof
person Community    schedule 05.12.2014    source источник
comment
что это прямо означает, и как C++ вступает в игру?   -  person Scott Hunter    schedule 05.12.2014
comment
@ScottHunter Напрямую означает, что есть способ вызвать один из библиотечных предикатов в библиотеке (агрегат), чтобы сделать это, но я слишком туп, чтобы понять это. Упомянут C++, потому что связанный алгоритм делает что-то очень похожее на мой min_prefix/3, но в более общем виде.   -  person    schedule 05.12.2014
comment
@ScottHunter См. мое редактирование для обоснования упоминания partition_point.   -  person    schedule 05.12.2014
comment
@DanielLyons: Было бы очень интересно увидеть соответствующий SQL-запрос. Ведь SQL-запросы часто бывают пусть и не компактными, но, по крайней мере, свободными от ненужных понятий. Я дам награду за это.   -  person false    schedule 08.12.2014
comment
@Борис: Спасибо! Кстати, у меня открыты 2 награды, которые реально получить (и третью просто поблагодарить кого-то). В частности тот, который заканчивается завтра!!   -  person false    schedule 15.12.2014

Ответы (3)


arrow_upward
4
arrow_downward

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

Есть ли способ упростить задачу?

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

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

Каждый раз, когда вы пишете императивное имя для чего-то, что является отношением, вы уменьшаете свое понимание отношений. Не много, совсем чуть-чуть. Многие распространенные идиомы Пролога, такие как 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 может измениться. После каждого изменения (записи нового файла) вам придется перезагружать программу. Это настолько сложно, что, скорее всего, вы никогда этого не сделаете. Я предполагаю, что у вас нет тестового жгута для этого. Во-первых, Plunit не распространяется на такое тестирование. Эмпирическое правило: если вы не можете протестировать предикат на верхнем уровне, вы никогда этого не сделаете. Вместо этого рассмотрим

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 лет назад.

person false    schedule 14.12.2014

arrow_upward
1
arrow_downward

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

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).

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

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

person CapelliC    schedule 08.12.2014
comment
Я не уверен, что действительно могу сказать integrate/3, что такое мое Выражение и Свидетель, или я что-то упускаю? (Мне нужно поменять порядок V и W в call(Goal, V, W), иначе это не сделает то, к чему я изначально стремился? Кроме того, это непреднамеренно меняет порядок решений.) В противном случае да, это прямая реализация чего я пытаюсь достичь. Я тайно надеялся на решение, основанное на существующих инструментах. - person ; 08.12.2014
comment
да, на самом деле я знал об этих проблемах: но не ясно, как их преодолеть. библиотека (лямбда) на данный момент является лучшей, но она создает некоторые проблемы с эффективностью. Вместо этого я бы следовал практичному, по общему признанию, глупому пути, чтобы специализировать «селектор функций». - person CapelliC; 08.12.2014
comment
Это прекрасно, как есть; Я могу в значительной степени включить специализированную версию этого предиката в свою программу, если захочу. Однако вы правы в том, что это еще не совсем библиотечный предикат. - person ; 08.12.2014
comment
Есть ли причина, по которой State имеет только два аргумента? Должно быть три. Последняя переменная всегда не конкретизируется - person false; 09.12.2014

arrow_upward
0
arrow_downward

Используя 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].
person Community    schedule 01.10.2015