Prolog:谓词最大，无累加器 [英] Prolog: predicate for maximum without accumulator

问题描述

是否有可能在没有累加器的情况下创建谓词max/2 ，所以当且仅当Max是List的最大值(整数列表)时，max(List, Max)为true )?

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屋！