7

鉴于数据库中的以下事实：

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

3 回答 3

4

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

有没有办法简化问题？

以下许多评论可以添加到这里的许多程序中。

命令式名称

每次，你为某种关系写一个命令式的名字，你会减少你对关系的理解。不多，就一点点。许多常见的 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 年前推出以来，它就一直存在。

于 2014-12-14T14:53:25.670 回答
1

我不认为 library(aggregate) 涵盖了您的用例。aggregate(min) 允许一个见证人：

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

它是integral(min) 的一个简单的扩展......它的比较方法肯定是有问题的（它使用较少的通用运算符来表示相等），可能值得采用传统的调用，例如predsort / 3 采用的调用。效率方面，最好将比较方法编码为“函数选择器”中的选项（在这种情况下为 min_list_associated）

编辑感谢 @false 和 @Boris 纠正与状态表示相关的错误。在使用时，调用nb_setarg(2, State, Ws)实际上会改变术语的形状State = (_,[],_)。将相应地更新 github 存储库...

于 2014-12-08T11:26:22.380 回答
0

使用library(pairs)and [ 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].
于 2015-10-01T06:42:48.897 回答