Finding the max in a list - Prolog

问题:

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?

回答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.

回答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)).

回答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.

回答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

回答5:

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!

回答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

回答7:

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