2

I am trying to find the max number in a list. I know there are several solutions available online but I feel the best way to learn is to implement on my own.

I wrote the following code:

max([X],X).
max([H|T],Res):-
    (  H >= Res
    -> max(T,Res1), Res1 = H
    ;  max(T,Res)
    ).

Can someone point out my mistake? I am not able to figure it out.

4
  • 2
    One issue is that Res isn't instantiated on a query to max.
    – lurker
    Dec 13, 2014 at 4:48
  • 1
    Try to "think different (Prolog)" ! What is the max of a list ? It's a member E of this list, and there is no other element of this list greater than E.
    – joel76
    Dec 13, 2014 at 13:07
  • 1
    You'll need to introduce another variable to max and you can do this with an auxiliary predicate (which can just be max/3 versus max/2). Here's a starter: max([H|T], Max) :- max(T, H, Max). This says, Max is the maximum value of list [H|T] if Max is the maximum of the highest value in list T and the value H (last max value seen). Now, you need to define max(List, MaxSeenSoFar, Max) and now you have MaxSeenSoFar instantiated, so you can use your logical which compares H from [H|T] with MaxSeenSoFar.
    – lurker
    Dec 13, 2014 at 14:03
  • 1
    possible duplicate of Finding the max in a list - Prolog
    – repeat
    May 25, 2015 at 11:45

2 Answers 2

2

Consider the code presented in my answer to related question "Finding the max in a list - Prolog".

The code in mentioned answer is based on the foldl/4.

Here, I show how to do it with the meta-predicates combine/3 and reduce/3. First, combine/3:

:- meta_predicate combine(3,?,?).
combine( _ ,[]    ,[]).
combine(P_3,[X|Xs],Ys) :-
   list_prev_combined_(Xs,X,Ys,P_3).

:- meta_predicate list_combined_(?,?,3).
list_combined_([]    ,[], _ ).
list_combined_([X|Xs],Ys,P_3) :-
   list_prev_combined_(Xs,X,Ys,P_3).

:- meta_predicate list_prev_combined_(?,?,?,3).    
list_prev_combined_([]     ,X ,[X]   , _ ).
list_prev_combined_([X1|Xs],X0,[Y|Ys],P_3) :-
   call(P_3,X0,X1,Y),
   list_combined_(Xs,Ys,P_3).

Building on combine/3 we can define reduce/3 as follows:

:- meta_predicate reduce(3,?,?).
reduce(P_3,[X|Xs],V) :- 
   list_aka_prev_reduced_(Xs,Xs,X,V,P_3).

:- meta_predicate list_aka_prev_reduced_(?,?,?,?,3).
list_aka_prev_reduced_([]   ,_ ,V ,V, _ ).
list_aka_prev_reduced_([_|_],Xs,X0,V,P_3) :-
   list_prev_combined_(Xs,X0,Ys,P_3),
   reduce(P_3,Ys,V).

Regarding the shape of their respective proof trees, foldl/4 is similar to lists, while combine/3 and reduce/3 are similar to balanced binary trees.

Consider the following queries:

:- use_module(library(lambda)).

?- foldl(\X^Y^f(X,Y)^true, [1,2,3,4,5,6,7], 0,S).
S = f(7,f(6,f(5,f(4,f(3,f(2,f(1,0))))))).

?- combine(\X^Y^f(X,Y)^true, [1,2,3,4,5,6,7], S).
S = [f(1,2),f(3,4),f(5,6),7].

?- reduce(\X^Y^f(X,Y)^true, [1,2,3,4,5,6,7], S).
S = f(f(f(1,2),f(3,4)),f(f(5,6),7)).

reduce/3 is based on combine/3 and applies it until all items have been combined to one:

?- combine(\X^Y^f(X,Y)^true, [1,2,3,4,5,6,7], S).
S = [f(1,2),f(3,4),f(5,6),7].

?- combine(\X^Y^f(X,Y)^true, [f(1,2),f(3,4),f(5,6),7], S).
S = [f(f(1,2),f(3,4)),f(f(5,6),7)].

?- combine(\X^Y^f(X,Y)^true, [f(f(1,2),f(3,4)),f(f(5,6),7)], S).
S = [f(f(f(1,2),f(3,4)),f(f(5,6),7))].

?- reduce(\X^Y^f(X,Y)^true, [1,2,3,4,5,6,7], S).
S =  f(f(f(1,2),f(3,4)),f(f(5,6),7)).

Let's use it for getting the maximum integer Max in list [1,5,2,4,3,8,7,2]:

:- use_module(library(clpfd)).

?- reduce(\X^Y^XY^(XY #= max(X,Y)), [1,5,2,4,3,8,7,2], Max).
Max = 8.

℅ If you can't use clpfd, simply use is/2 instead of (#=)/2:
?- reduce(\X^Y^XY^(XY is max(X,Y)), [1,5,2,4,3,8,7,2], Max).
Max = 8.
1

You aren't ensuring that Res is instantiated. You don't neccesary need a helper predicate to do that. You could make the recursive call before the check if Res is bigger than H where Res is the biggest integer of T.

You can use ->, but you don't have to. But if you don't, a little bit more backtracking would be involved.

If you try to stay more on your route with recursion after the check, you'll need a helper predicate, as lurker has suggested.

Edit: Since the answer is accepted now, here are the three suggestions implemented:

max1([H|T], Y):-  % with the -> operator, call first
    max1(T,X),
    (H > X ->
     H = Y;
     Y = X).
max1([X],X).


max2([H|T], Y):-  % without the -> operator, call first (this might be very inefficient)
    max2(T,Y),
    H < Y.
max2([H|T], H):-
    max2(T,Y),
    H >= Y.
max2([X],X).


max3([H|T], Y) :- max_(T,H,Y).            % with helper predicate
max_([H|T],HighestNow,Highest):-          % call after the test
    (H > HighestNow -> max_(T,H, Highest)
     ;
     max_(T,HighestNow,Highest)).
max_([],X,X).
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.