从谓词中收集所有“最小”的解决方案

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

我可以使用aggregate/3代替setof/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].

最后，关于问题：

• 我能否直接使用library(aggregate)完成这个操作？感觉应该是可能的...

• 还是有类似于C++标准库中std::partition_point这样的谓词吗？

• 还是有更简单的方法来完成这个操作吗？

编辑：

为了更加详细，假设有一个(library) predicate 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].

- user1812457

---

“do this directly” 是什么意思，C++ 又如何发挥作用？ - Scott Hunter

@ScottHunter “直接”意味着有一种方法可以调用库(aggregate)中的一个谓词来完成这个任务，但我太笨了，无法想出来。提到C++是因为链接的算法与我的min_prefix/3非常相似，但更加通用。 - user1812457

@ScottHunter 请看我的编辑，了解提及“partition_point”的原因。 - user1812457

@DanielLyons：看到相应的SQL查询语句会非常有趣。毕竟，SQL查询通常不是紧凑的，但至少没有不必要的概念。我将为此设置赏金。 - false

@Boris：谢谢！顺便说一下，我有两个开放的赏金任务是可以实现的（还有一个只是为了感谢某人）。特别是那个明天结束的！ - false

Answer 1

什么是这类问题的惯用方法？

有没有简化问题的方法？

以下许多评论都可以添加到SO上的许多程序中。

命令式名称

每次使用关系时编写一个命令式名称会降低您对关系的理解。不多，只是一点点。许多常见的Prolog习语，如append/3，并不能提供很好的示例。考虑append（As，As，AsAs）。 find_min（Min，As）的第一个参数是最小值。因此，minimum_with_nodes/2可能是更好的名称。 findall/3 除非经过严格检查，否则不要使用findall/3，基本上必须使所有内容都成为ground。在您的情况下它碰巧起作用。但是，一旦你将foo/2泛化一点，你就会失去。这经常是个问题：你写了一个微小的程序;它似乎可行。 一旦你转向更大的程序，同样的方法就不再起作用了。与setof/3相比，findall/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 = [_A].

目前还不清楚这是否是一个功能。自从大约5年前引入call_residue_vars/2以来，该功能一直存在。

- false

Answer 2

我认为库(aggregate)不适用于您的用例。 aggregate(min)仅允许一个证人:

min(Expr, Witness) 一个术语min(Min,Witness),其中Min是Expr在所有解决方案中的最小版本，而Witness是应用于生成Min的解决方案的任何其他模板。如果多个解决方案提供相同的最小值，则Witness对应于第一个解决方案。

一段时间以前，我写了一个小的“库”lag.pl，其中包含使用低开销聚合的谓词-因此得名（LAG =线性聚合）。我添加了一个片段，可处理您的用例：

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

这是一个将integrate(min)简单扩展的方法... 它使用了较少通用的等式运算符，比较方法可疑，可能值得采用predsort/3采用的传统调用。从效率上讲，更好的方法是将比较方法编码为“函数选择器”中的选项（在本例中为min_list_associated）。 编辑感谢@false和@Boris纠正了与状态表示相关的错误。当使用State = (_,[],_)时，调用nb_setarg(2, State, Ws)会实际改变术语形状。将相应地更新github repo...

- CapelliC

---

我不确定我是否能够准确地告诉 integrate/3 我的表达式和证明，还是我错过了什么？（我需要交换 call(Goal, V, W) 中 V 和 W 的顺序，否则它不会实现我最初想要的功能？此外，它无意中颠倒了解决方案的顺序。）否则，是的，这是我尝试实现的直接方法。我曾经私下希望有一个基于现有工具的解决方案。 - user1812457

是的，实际上我已经意识到了这些问题：但是如何克服它们并不清楚。目前为止，lambda库是最好的选择，但它会带来一些效率问题。相反，我会采取实用但有点愚蠢的路线来专门化“函数选择器”。 - CapelliC

它现在已经很好了；如果我想要的话，我可以将这个谓词的专门版本插入到我的程序中。但你说得对，它还不完全是一个“库”谓词。 - user1812457

State 只有两个参数，这是有原因的吗？它应该有三个参数，最后一个参数是一个始终未实例化的变量。 - false

Answer 3

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

可以用keysort/2替换对sort/4的调用，但是使用sort/4也可以找到例如与最大第二个参数相关联的第一个参数：只需将@>=用作第二个参数。

这种解决方案可能不如其他方案时间和空间效率高，但更容易理解。

但是还有另一种完全不同的方法：

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

- user1812457