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.
Res
isn't instantiated on a query tomax
.max
and you can do this with an auxiliary predicate (which can just bemax/3
versusmax/2
). Here's a starter:max([H|T], Max) :- max(T, H, Max).
This says,Max
is the maximum value of list[H|T]
ifMax
is the maximum of the highest value in listT
and the valueH
(last max value seen). Now, you need to definemax(List, MaxSeenSoFar, Max)
and now you haveMaxSeenSoFar
instantiated, so you can use your logical which comparesH
from[H|T]
withMaxSeenSoFar
.