收集所有“最低"的谓词的解决方案

本文介绍了收集所有“最低"的谓词的解决方案的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

Given the following facts in a database:

foo(a, 3). foo(b, 2). foo(c, 4). foo(d, 3). foo(e, 2). foo(f, 6). foo(g, 3). foo(h, 2).

我想收集第二个参数最小的所有第一个参数，加上第二个参数的值.第一次尝试:

I want to collect all first arguments that have the smallest second argument, plus the value of the second argument. First try:

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:

Instead of setof/3, I could use 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(...), ...) 会抛出错误！

This only gives the same results if I am looking for the minimum of a number. If an arithmetic expression in involved, the results might be different. If a non-number is involved, aggregate(min(...), ...) will throw an error!

或者，我可以使用完整的键排序列表:

Or, instead, I can use the full key-sorted list:

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

最后，问题:

• 我可以直接使用库(聚合)吗?感觉应该是可以的....

• Can I do this directly with library(aggregate)? It feels like it should be possible....

或者有没有像 std::partition_point 来自 C++ 标准库?

Or is there a predicate like std::partition_point from the C++ standard library?

或者有更简单的方法吗?

Or is there some easier way to do this?

为了更具描述性.假设有一个(库)谓词 partition_point/4:

To be more descriptive. Say there was a (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] ).

(我不喜欢这个名字，但我们现在可以忍受)

(I don't like the name but we can live with it for now)

然后:

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

推荐答案

使用 library(pairs) 和 [sort/4]，可以简单写成:

Using library(pairs) and [sort/4], this can be simply written as:

?- 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 也可以找到例如第一个参数与最大的第二个参数相关联:只需使用 @>= 作为第二个参数.

This call to sort/4 can be replaced with keysort/2, but with sort/4 one can also find for example the first arguments associated with the largest second argument: just use @>= as the second argument.

这个解决方案可能不像其他解决方案那样节省时间和空间，但可能更容易理解.

This solution is probably not as time and space efficient as the other ones, but may be easier to grok.

但还有另一种方法可以完全做到这一点:

But there is another way to do it altogether:

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