Finding the max in a list - Prolog

Question

I was just introduced to Prolog and am trying to write a predicate that finds the Max value of a list of integers. I need to write one that compares from the beginning and the other that compares from the end. So far, I have:

max2([],R).
max2([X|Xs], R):- X > R, max2(Xs, X).
max2([X|Xs], R):- X <= R, max2(Xs, R).

I realize that R hasn't been initiated yet, so it's unable to make the comparison. Do i need 3 arguments in order to complete this?

Answer 1

my_max([], R, R). %end
my_max([X|Xs], WK, R):- X >  WK, my_max(Xs, X, R). %WK is Carry about
my_max([X|Xs], WK, R):- X =< WK, my_max(Xs, WK, R).
my_max([X|Xs], R):- my_max(Xs, X, R). %start

other way

%max of list
max_l([X],X) :- !, true.
%max_l([X],X). %unuse cut
%max_l([X],X):- false.
max_l([X|Xs], M):- max_l(Xs, M), M >= X.
max_l([X|Xs], X):- max_l(Xs, M), X >  M.

Answer 2

Ignoring the homework constraints about starting from the beginning or the end, the proper way to implement a predicate that gets the numeric maximum is as follows:

list_max([P|T], O) :- list_max(T, P, O).

list_max([], P, P).
list_max([H|T], P, O) :-
    (    H > P
    ->   list_max(T, H, O)
    ;    list_max(T, P, O)).

Answer 3

As an alternative to BLUEPIXY' answer, SWI-Prolog has a builtin predicate, max_list/2, that does the search for you. You could also consider a slower method, IMO useful to gain familiarity with more builtins and nondeterminism (and then backtracking):

slow_max(L, Max) :-
   select(Max, L, Rest), \+ (member(E, Rest), E > Max).

yields

2 ?- slow_max([1,2,3,4,5,6,10,7,8],X).
X = 10 ;
false.

3 ?- slow_max([1,2,10,3,4,5,6,10,7,8],X).
X = 10 ;
X = 10 ;
false.

edit

Note you don't strictly need three arguments, but just to have properly instantiated variables to carry out the comparison. Then you can 'reverse' the flow of values:

max2([R], R).
max2([X|Xs], R):- max2(Xs, T), (X > T -> R = X ; R = T).

again, this is slower than the three arguments loops, suggested in other answers, because it will defeat 'tail recursion optimization'. Also, it does just find one of the maxima:

2 ?- max2([1,2,3,10,5,10,6],X).
X = 10 ;
false.

Answer 4

Here's how to do it with lambda expressions and meta-predicate foldl/4, and, optionally, clpfd:

:- use_module([library(lambda),library(apply),library(clpfd)]).

numbers_max([Z|Zs],Max) :- foldl(\X^S^M^(M is max(X,S)),Zs,Z,Max).
fdvars_max( [Z|Zs],Max) :- foldl(\X^S^M^(M #= max(X,S)),Zs,Z,Max).

Let's run some queries!

?- numbers_max([1,4,2,3],M).              % integers: all are distinct
M = 4.                                    % succeeds deterministically
?- fdvars_max( [1,4,2,3],M).
M = 4.                                    % succeeds deterministically

?- numbers_max([1,4,2,3,4],M).            % integers: M occurs twice 
M = 4.                                    % succeeds deterministically
?- fdvars_max( [1,4,2,3,4],M).
M = 4.                                    % succeeds deterministically

What if the list is empty?

?- numbers_max([],M).
false.
?- fdvars_max( [],M).
false.

At last, some queries showing differences between numbers_max/2 and fdvars_max/2:

?- numbers_max([1,2,3,10.0],M).           % ints + float
M = 10.0.
?- fdvars_max( [1,2,3,10.0],M).           % ints + float
ERROR: Domain error: `clpfd_expression' expected, found `10.0'

?- numbers_max([A,B,C],M).                % more general use  
ERROR: is/2: Arguments are not sufficiently instantiated
?- fdvars_max( [A,B,C],M).
M#>=_X, M#>=C, M#=max(C,_X), _X#>=A, _X#>=B, _X#=max(B,A). % residual goals