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