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 的谓词通常不会出现堆栈溢出异常。

与一样，is仅在列表完全接地的情况下有效：它是一个有限列表并且所有元素都接地。但是，您可以使用 Prolog 的 constraint logic programming 包 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.

Answer 2

标准谓词 is/2 和 CLP(FD) 谓词 (#=)/2 都不能在这里做数学运算。所以最终，对于某些应用程序，例如精确几何，它们可能不适合。

为了说明一点，让我们考虑一个示例和计算机代数系统 (CAS) 的替代方案。我正在使用新的 Jekejeke Minlog 0.9.2 原型进行演示，它在 Prolog 中提供 CAS。

作为初步我们有两个谓词eval_keys/2和min_key/2，它们的代码可以在post的附录中找到。让我们先用整数来说明这个谓词的作用。第一个谓词只是计算对列表的键：

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.25-3-gc3a87c2)
Copyright (c) 1990-2016 University of Amsterdam, VU Amsterdam

?- eval_keys([(1+3)-foo,2-bar],L).
L = [4-foo,2-bar]

第二个谓词选择键最小的第一个值：

?- min_key([4-foo,2-bar],X).
X = bar

现在让我们看看其他键值，我们将使用平方根，它属于代数数域。代数数是无理数，因此永远不适合浮点数。因此，对于新示例，我们得到结果 foo:

?- eval_keys([(sqrt(98428513)+sqrt(101596577))-foo,sqrt(400025090)-bar],L).
L = [20000.62724016424-foo, 20000.627240164245-bar].

?- min_key([20000.62724016424-foo, 20000.627240164245-bar], X).
X = foo.

CLP(FD) 只有整数，没有直接表示代数数的方法。另一方面，许多 CAS 系统支持部首。我们的 Prototype 甚至支持对它们进行比较，以便我们可以获得准确的结果 bar:

Jekejeke Prolog 2, Runtime Library 1.2.2
(c) 1985-2017, XLOG Technologies GmbH, Switzerland

?- eval_keys([(sqrt(98428513)+sqrt(101596577))-foo,sqrt(400025090)-bar],L).
L = [radical(0,[98428513-1,101596577-1])-foo,
   radical(0,[400025090-1])-bar]

?- min_key([radical(0,[98428513-1,101596577-1])-foo,
   radical(0,[400025090-1])-bar],X).
X = bar

那个条是精确的结果，例如可以使用多精度计算器看到。如果我们将精度加倍，我们确实会看到最后一个平方根较小，而不是平方根之和：

?- use_module(library(decimal/multi)).
% 7 consults and 0 unloads in 319 ms.
Yes

?- X is mp(sqrt(98428513)+sqrt(101596577), 32).
X = 0d20000.627240164244658958331341095

?- X is mp(sqrt(400025090), 32).
X = 0d20000.627240164244408966171597261

但是 CAS 不需要这样处理。例如，我们的 Prolog implementation 使用受 Swinnerton-Dyer 多项式启发的方法来比较激进表达式，这纯粹是象征性的。

附录测试代码：

% :- use_module(library(groebner/generic)). /* to enable CAS */

eval_keys([X-A|L], [Y-A|R]) :- Y is X, eval_keys(L, R).
eval_keys([], []).

min_key([X-A|L], B) :- min_key(L, X, A, B).

min_key([X-A|L], Y, _, B) :- X < Y, !, min_key(L, X, A, B).
min_key([_|L], X, A, B) :- min_key(L, X, A, B).
min_key([], _, A, A).

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

Prolog: predicate for maximum without accumulator

list

prolog

integer-arithmetic