Prolog:通过回溯获得最大/最小值？

Question

我想知道通过这样的回溯获得某些事实的最大值(最年长的人)是否是个好主意:

data(MaxID, MaxName, MaxAge),
\+ (data(ID, Name, Age), ID \= MaxID, MaxAge < Age).

对于最小值(最年轻的人)，反之亦然:

data(MinID, MinName, MinAge),
\+ (data(ID, Name, Age), ID \= MinID, MinAge > Age).

这在空间或时间复杂度方面是否有效？

实现风格是否简单/直接？是否存在“更好”的实现？

Answer 1

Is this efficient in terms of space or time complexity?

您的实现的时间复杂度为 O(N^2)，因为对于每个候选谓词，所有其他谓词都被“要求”进行比较。空间复杂度为 O(1)。

Do "nicer" implementations exist?

是的，存在更好、更高效的实现。很长一段时间以来，SWI-Prolog 提供了库(aggregate)，这是对 setof/bagof/findall 经典内置函数的直接增强:

?- aggregate(max(Age,data(ID,Name,Age)), ID^Name^data(ID,Name,Age), max(_,X)).

注意ID^Name^...表示的量化控制的风格。这与 setof/3 和 bagof/3 的要求完全相同。基于不可回溯的分配，实现更加高效。

最新添加的可以被认为是库(solution_sequences)。在深入研究最后一个之前，请考虑练习 library(aggregate)。

编辑

基于@false 对问题的评论和@boris 的回答，我会尝试提供一个“更好”(当然是主观评价)的实现:

min(P,A) :-
    copy_term(P,Q),
    arg(A,P,V), arg(A,Q,U),
    call(P), \+ ( call(Q), U@<V ).

现在，您可以将谓词作为第一个参数传递，并指定 P 的参数用于与第二个参数进行比较。