Prolog:不带累加器的最大值谓词 [英] Prolog: predicate for maximum without accumulator

问题描述

是否有可能创建一个谓词 max/2 没有一个累加器，以便 max(List, Max) 当且仅是 true如果 Max 是 List(整数列表)的最大值?

Is it possible to create a predicate max/2 without an accumulator so that max(List, Max) is true if and only if Max is the maximum value of List (a list of integers)?

推荐答案

是的，你可以计算递归步骤之后之后的最大值.喜欢:

Yes, you can calculate the maximum after the recursive step. Like:

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

This predicate will work on floating points for instance. Nevertheless it is better to use an accumulator since most Prolog interpreters use tail call optimization (TCO) and predicates with accumulators tend to work with tail calls. As a result predicates with TCO will usually not get a stack overflow exception if you want to process huge lists.

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

As @Lurker says, is only works in case that the list is fully grounded: it is a finite list and all elements grounded. You can however use Prolog's constraint logic programming package 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.

So after the max/2 call, by grounding A, B and C, we obtain M=3.

这篇关于Prolog:不带累加器的最大值谓词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！