prolog - 从谓词中收集所有 "minimum"解决方案

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

备注

如果我正在寻找 的最小值，这只会给出相同的结果号码 .如果涉及算术表达式，结果可能会有所不同。如果涉及非数字， 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) 做这个吗？感觉应该是可以的....

或者是否有像 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

What is the idiomatic approach to this class of problems?

Is there a way to simplify the problem?

以下许多评论可以添加到 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可能会改变。每次更改(写入新文件)后，您都必须重新加载程序。这太复杂了，您可能永远不会这样做。我想你没有一个测试工具。 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 年前。