Prolog

Question

我有一个这样的事实列表：

set(h, 3).
set(h, 6).
set(h, 12).
set(h, 1).
set(h, 7).

我需要找到集合 h 的最大值，查询需要如下所示：

?- maximum(h, Max).
Max = 12.

显然，现在有很多方法可以做到这一点。但目前我正在寻找一种方法来使用动态谓词和失败谓词来做到这一点。我猜我可能不得不使用 repeat ？不幸的是，重复谓词和动态谓词都让我感到困惑。

我在想这样的事情：

set(h, 3).
set(h, 6).
set(h, 12).
set(h, 1).
set(h, 7).

:- dynamic current_max/1.

assert(current_max(0)).

maximum(Set, Element):-
    repeat,
    set(Set,Element),
    current_max(Max),
    (Max > Element,
        fail);
     (Element > Max,
     retract(current_max(Max)),
     assert(current_max(Element)),
     fail).

maximum(_, Max):-
    current_max(Max).

我自己看到的一个问题是重复循环不会停止。如果我能以某种方式知道它是集合的最后一个元素，我可能会使用 cut，但我不确定如何使用。

Answer 1

失败驱动的循环如下所示：

(   Generator,
    Side_effect,
    fail
;   true
)

在你的例子中 set/2 是生成器，更新当前最大值是副作用。在这种情况下您不需要 repeat：调用 set/2 将生成选择点。当您必须在没有生成器的情况下创建选择点时，您需要 repeat。

再次，我不得不说这是一个非常奇怪的问题（你有）。如果你想做这样的事情，至少不要使用动态谓词来保持当前最大值：这只是在自找麻烦。

以 SWI-Prolog 的 library(aggregate) there are examples of doing this. Taking aggregate_all/3 作为起点，只留下寻找最大数的代码，你有：

set(h, 3).
set(h, 6).
set(h, 12).
set(h, 1).
set(h, 7).

maximum(Set, Max) :-
        State = state(Max),
        (       set(Set, Max),
                arg(1, State, M0),
                M is max(M0, Max),
                nb_setarg(1, State, M),
                fail
        ;       arg(1, State, Max),
                nonvar(Max)
        ).

这使用一个术语来保存当前最大值，因此您要保持的状态是 maximum/2 谓词的局部状态。它也不假定初始值（如果您从 0 开始，就像您所做的那样，并且所有值恰好都是负数，您将得到不正确的结果！）。使用此定义：

?- maximum(h, M).
M = 12.

?- maximum(x, M).
false.

几条评论：

如果在析取开始时调用 set/2 失败，则最后需要 nonvar(Max)。但请注意，就目前而言，您仍然会得到错误的结果：

?- maximum(x, 42).
true.

你应该能想出如何处理这个问题。

目前，这使用算术函数 max 来获取两个数字中较大的一个。如果你有其他任何东西，这将不起作用，比如原子（即使原子有一个定义的总排序）。您可以定义一个谓词来查找任意两项中的最大值：

term_max(X, Y, Max) :-
    (   X @> Y
    ->  Max = X
    ;   Max = Y
    ).

那么，你只需更换

M is Max(M0, Max)

与：

term_max(M0, Max, M)

Answer 2

好的。几天来我一直在研究这个。我想我明白为什么我们不需要重复。我尝试将我的（糟糕的）方法与您的一些想法结合起来。

这是我想出的：

maximum(Set, Element):-
    ((set(Set,Element),
        current_max(Max),
        (Max > Element,
            fail);
         (Element > Max,
         retract(current_max(Max)),
         assert(current_max(Element)),
         fail))
     ;
     true
     ).

maximum(_, Max):-
    current_max(Max).)

不幸的是现在它给了我 "Arguments are not sufficiently instantiated"。

这就是我的想法：set/2 生成你的值（可以给它设置，元素从事实中获取第一个值）。然后它从 current_max/1 中取一个值（一开始是 0）。如果 max 大于它失败并从集合中获取另一个值。如果 Element 大于 Max，我们删除之前的 current_max 事实并创建新的。然后我们也失败并返回。一旦所有值都通过它 returns true。然后我希望它也能通过第二条规则给出最大答案。

Answer 3

一个低效但可能在教学上有用的解决方案是使用 forall/2 为您找到正确的值：

maximum(Set, Max) :-
  set(Set, Max),
  forall(set(Set, Other), 
           Max >= Other).

Prolog 将（低效地）选择每个元素作为候选 Max，直到满足 forall/2 步骤，因此这绝对是一个二次时间解决方案，但它说明了 "Prolog thinking" 在我看来，比失败驱动的循环更好。

repeat/0 实际上是 Prolog 中的一种低级机器。大多数时候，通过逻辑思考问题并围绕该逻辑构建解决方案，而不是预先担心 Prolog 的解析系统将如何得出结果，您可以获得更好的结果。在前一种方法中，您仍然需要了解回溯以及 Prolog 将如何重试，但您使用它，而不是对抗它或试图直接利用它。

Prolog - 在最后一个事实时停止重复

Prolog - stop repeat when last fact

max

prolog-assert