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

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 2

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 3

Blockquote @Stephan your answer is correct. you can improve this by the following Idea: Just scan through the list and store the largest number you have seen.

I upvoted your answer , but couldnt add a comment on your answer.

Answer 4

Nice Solutions...