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

A very simple approach (which starts from the beginning) is the following:

maxlist([],0).

maxlist([Head|Tail],Max) :-
    maxlist(Tail,TailMax),
    Head > TailMax,
    Max is Head.

maxlist([Head|Tail],Max) :-
    maxlist(Tail,TailMax),
    Head =< TailMax,
    Max is TailMax.

As you said, you must have the variables instantiated if you want to evaluate an arithmetic expression. To solve this, first you have to make the recursive call, and then you compare.

Hope it helps!

Answer 4

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 5

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

Answer 6

list_max([L|Ls], Max) :- foldl(num_num_max, Ls, L, Max).

num_num_max(X, Y, Max) :- Max is max(X, Y).

%Query will be

?-list_max([4,12,5,3,8,90,10,11],Max).
Max=90

Answer 7

Right now I was working with recursion in Prolog, so if it is useful for someone I will leave 'my two cents' solving it in the two ways that I have thought:

% Start
start :- max_trad([2, 4, 6, 0, 5], MaxNumber1),
         max_tail([2, 4, 6, 0, 5], 0, MaxNumber2),
         show_results(MaxNumber1, MaxNumber2).

% Traditional Recursion (Method 1)
max_trad([Head|Tail], Max) :- max_trad(Tail, Value), Head > Value, Max is Head.
max_trad([Head|Tail], Max) :- max_trad(Tail, Value), Head =< Value, Max is Value.
max_trad([], 0).

% Tail Recursion (Method 2)
max_tail([], PartialMax, PartialMax).
max_tail([Head|Tail], PartialMax, FinalMax) :- Head > PartialMax, max_tail(Tail, Head, FinalMax).
max_tail([_|Tail], PartialMax, FinalMax) :- max_tail(Tail, PartialMax, FinalMax).

% Show both of the results
show_results(MaxNumber1, MaxNumber2) :-
    write("The max value (obtained with traditional recursion) is: "), writeln(MaxNumber1),
    write("The max value (obtained with tail recursion) is: "), writeln(MaxNumber2).

The output of the above code is:

Both methods are similar, the difference is that in the second an auxiliary variable is used in the recursion to pass values forward, while in the first method, although we have one less variable, we are filling the Stack with instructions to be executed later, so if it were an exaggeratedly large list, the second method is appropriate.

Answer 8

 maximum_no([],Max):-

    write("Maximum No From the List is:: ",Max).
maximum_no([H|T],Max):-
    H>Max,
    N = H,
    maximum_no(T,N).
maximum_no(L,Max):-
    maximum_no(L,Max).

Answer 9

The maximum number in a list in Prolog ?

max([],A):-print(A),!.

max([Head | Tail] , A):-A =< Head ,A1 is Head , max(Tail,A1) ; max(Tail,A).

Answer 10

max(L,M):- member(M,L), findall(X,(member(X,L),X>M),NL), length(NL,0).