Prolog: predicate for maximum without accumulator

Question

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)?

Answer 1

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.

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.

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.

You can then for instance call:

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

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