Two clause definition to find the maximum number on a list

Question

How would I write a two clause recursive definition to find the maximum value in a list. So far I have written this:

 max(L,M):-  

 max([H|T],M):-

max(T,H,M).
max([],M,M).
max([H|T],Y,M):-
   H =< Y,
   max(T,Y,M).
max([H|T],Y,M):-
   H > Y,
   max(T,H,M).

This doesn't work, it says there is a syntax error which I can't quite see, and I know it isn't two clause either. Anyone know how I could simplify it to make it two clause?

Answer 1

As you, I use the 'max' name for the predicate. This implementation don't rely in any built-in predicate:

max([X],X).
max([X|Xs],X):- max(Xs,Y), X >=Y.
max([X|Xs],N):- max(Xs,N), N > X.

Answer 2

The syntax error results from the fact that the first two clauses have no body.

To answer your question, observe that the maximum of a list can be defined inductively as follows:

• The maximum of a list with one element is that element.
• The maximum of a list with multiple elements is the largest of the head and the maximum of the tail.

Thus,

max_list([H], H).
max_list([H|T], M2) :- 
  max_list(T, M),
  M2 is max(H, M).

This code uses max/2 (SWI-Prolog, GNU-Prolog). Note that most or all Prolog implementations will have a built-in function max_list/2 (S, G), so there is actually no need to define it yourself.

Edit: Bakore notes that a tail recursive implementation may be more efficient. You can do this by defining a predicate max_list/3 which takes an additional argument C, namely the largest value seen so far.

max_list([H|T], M) :- max_list(T, H, M). 

max_list([], C, C).
max_list([H|T], C, M) :- C2 is max(C, H), max_list(T, C2, M).

Answer 3

Here is a solution for max in lists of lists

max_list([], C, C).
max_list([H|T], C, M) :- C2 is max(C, H), max_list(T, C2, M).

max_list([], []).
max_list([[H|HB]|B],[RH|RB]) :- max_list(HB, H, RH), max_list(B, RB).

ex: max_list([[1,3,6], [6,3,8,2],[2,1,0]]).