prolog - 对 Prolog 中的事实进行排序

Question

假设 f(X)是一个动态事实，可以是 assert ed 和 retract ed，并假设 X永远是数字。现在，假设执行次数最多的查询是关于查找 f(X)这样是最低限度的。在 SWI-Prolog 中，我可以这样写:

min_f(R) :- aggregate(min(X), f(X), R).

但是，显然，这总是导致 Prolog 对所有事实执行线性搜索。现在，假设将有大量(例如 1,000,000)这样的事实。因为我事先知道我会经常执行 min_f/1 :

我可以对 f/1 下订单吗？ ，以便引擎可以在 O(1) 中找到最小值？

我可以明确assert一个包含所有事实的最小堆，然后查看头部；可以将事实隐式存储在最小堆中吗？

我对 Prolog 方言没有限制，所以任何替代的 Prolog 实现都可以。

Answer 1

可以快速提供最小值或最大值的数据结构的替代方案是使用模式定向制表。在模式定向表中，可以指定所需的聚合函数:

f(5).
f(4).
f(6).

:- table min_f(min).
min_f(X) :- f(X).

最小值将只计算一次，这是一个示例查询。在 SWI-Prolog 中工作，从 1.4.0 版开始也在 Jekejeke Prolog 中工作:

?- min_f(X).
X = 4.

从理论上讲，它是由制表实现决定的，它如何计算最小值。目前还有一些开发正在进行中，增量表，这将允许使 f/1 动态，然后跟踪更改。