Prolog:没有累加器的谓词最大值

Question

是否有可能在max/2 没有累加器的情况下创建谓词,因此max(List, Max)当且仅当Max是List(整数列表)的最大值时才是真的？

Answer 1

是的，您可以在递归步骤之后计算最大值。喜欢：

max([M],M).          % the maximum of a list with one element is that element.
max([H|T],M) :-
    max(T,M1),       % first calculate the maximum of the tail.
    M is max(H,M1).  % then calculate the real maximum as the max of
                     % head an the maximum of the tail.

例如，该谓词适用于浮点。尽管如此，最好使用累加器，因为大多数 Prolog 解释器都使用尾调用优化 (TCO)，并且带有累加器的谓词往往与尾调用一起使用。因此，如果您想要处理巨大的列表，带有 TCO 的谓词通常不会出现堆栈溢出异常。

正如@Lurker所说，is只有在列表完全接地的情况下才有效：它是一个有限列表，并且所有元素都接地。但是，您可以使用 Prolog 的约束逻辑编程包clp(fd)：

:- use_module(library(clpfd)).

max([M],M).          % the maximum of a list with one element is that element.
max([H|T],M) :-
    max(T,M1),       % first calculate the maximum of the tail.
    M #= max(H,M1).  % then calculate the real maximum as the max of
                     % head an the maximum of the tail.

然后您可以例如调用：

?- max([A,B,C],M),A=2,B=3,C=1.
A = 2,
B = M, M = 3,
C = 1 ;
false.

因此，在调用之后max/2，通过接地A、B和C，我们得到M=3。