# Higher-order Prolog predicates combine/3 and reduce/3

I'm trying to find useful versatile meta-predicates that are different from the vanilla ones offered currently by library(apply).

How about the following two: combine/3 and reduce/3? First, combine/3:

combine(_,[],[]).
combine(Pred_3,[X|Xs],Ys) :-
list_prev_combined_(Xs,X,Ys,Pred_3).

list_combined_([],[],_).
list_combined_([X|Xs],Ys,Pred_3) :-
list_prev_combined_(Xs,X,Ys,Pred_3).

list_prev_combined_([],X,[X],_).
list_prev_combined_([X1|Xs],X0,[Y|Ys],Pred_3) :-
call(Pred_3,X0,X1,Y),
list_combined_(Xs,Ys,Pred_3).


Building on combine/3 we define reduce/3:

reduce(Pred_3,[X|Xs],V) :-
list_prev_reduced_(Xs,X,V,Pred_3).

list_prev_reduced_([],V,V,_).
list_prev_reduced_([X1|Xs],X0,V,Pred_3) :-
list_prev_combined_([X1|Xs],X0,Ys,Pred_3),
reduce(Pred_3,Ys,V).


So... what does combine/3 do?

:- use_module(library(lambda)).

?- length(_,N),numlist(1,N,Xs),combine(\X^Y^f(X,Y)^true,Xs,Ys).
N = 1, Xs = Ys,                  Ys = [1] ;
N = 2, Xs = [1,2],               Ys = [f(1,2)] ;
N = 3, Xs = [1,2,3],             Ys = [f(1,2),3] ;
N = 4, Xs = [1,2,3,4],           Ys = [f(1,2),f(3,4)] ;
N = 5, Xs = [1,2,3,4,5],         Ys = [f(1,2),f(3,4),5] ;
N = 6, Xs = [1,2,3,4,5,6],       Ys = [f(1,2),f(3,4),f(5,6)] ;
N = 7, Xs = [1,2,3,4,5,6,7],     Ys = [f(1,2),f(3,4),f(5,6),7] ;
N = 8, Xs = [1,2,3,4,5,6,7,8],   Ys = [f(1,2),f(3,4),f(5,6),f(7,8)] ;
N = 9, Xs = [1,2,3,4,5,6,7,8,9], Ys = [f(1,2),f(3,4),f(5,6),f(7,8),9] ...


Same question for reduce/3:

?- length(_,N),numlist(1,N,Xs),reduce(\X^Y^f(X,Y)^true,Xs,V).
N = V, Xs = [1],                 V = 1 ;
N = 2, Xs = [1,2],               V = f(1,2) ;
N = 3, Xs = [1,2,3],             V = f(f(1,2),3) ;
N = 4, Xs = [1,2,3,4],           V = f(f(1,2),f(3,4)) ;
N = 5, Xs = [1,2,3,4,5],         V = f(f(f(1,2),f(3,4)),5) ;
N = 6, Xs = [1,2,3,4,5,6],       V = f(f(f(1,2),f(3,4)),f(5,6)) ;
N = 7, Xs = [1,2,3,4,5,6,7],     V = f(f(f(1,2),f(3,4)),f(f(5,6),7)) ;
N = 8, Xs = [1,2,3,4,5,6,7,8],   V = f(f(f(1,2),f(3,4)),f(f(5,6),f(7,8))) ...


Before we do some "real" tests we need to code the following auxiliary predicates first:

:- use_module(library(clpfd)).

int_int_product(A,B,AB) :-
AB #= A*B.

n_log2factorialA(N,LdFac) :-
numlist(1,N,Factors),
foldl(int_int_product,Factors,1,V),
LdFac is msb(V).

n_log2factorialB(N,LdFac) :-
numlist(1,N,Factors),
reduce(int_int_product,Factors,V),
LdFac is msb(V).


Now let's do some queries:

?- time(n_log2factorialA(100000,L)).
% 800,013 inferences, 5.847 CPU in 5.845 seconds (100% CPU, 136834 Lips)
L = 1516704.

?- time(n_log2factorialB(100000,L)).
% 900,046 inferences, 0.094 CPU in 0.094 seconds (100% CPU, 9558102 Lips)
L = 1516704.


Are combine/3 and reduce/3 useful idioms?

Yes, they are. Speaking Haskell, combine is pairwise,

pairwise f (x:y:r) = f x y : pairwise f r
pairwise _ xs      = xs   -- covers both [x] and [] cases


and reduce looks like the tree-shape folding

foldt f [x] = x
foldt f xs = foldt f (pairwise f xs)


Of course tree-shaped folding is algorithmically advantageous over the linear one. It's even possible to tree-fold infinite lists as well. Switching from linear to tree-like folding shape e.g. in primes production brings down the empirical orders of growth from about n1.5 to about n1.2.

See more at

I must admit, your predicates written for speed and efficiency, taking into account indexing (right?) are hard-ish to read (compared to Haskell definitions). Maybe keep the simple and inefficient variants nearby, commented out, as a documentation?

% pairwise(F, [A,B|C], [R|T]):- call(F,A,B,R), ... .
% ...


etc. (?)

To your question elsewhere in the comments (which brought me to this question), both foldl (or foldr) and foldt (or foldi) could be called reduce; better indicate the linear/tree structure of the fold explicitly in the name of a predicate/function, I think.

• s(X) for your answer. Yes, the code is a bit ackward as I want to use indexing. Maybe I should try to find out how these could be used in "other directions", too. cf. stackoverflow.com/a/6683502/4609915 – repeat Dec 13 '15 at 7:31

This has gone unanswered for a long time, and even though I haven't done any serious prolog coding, I would like to come with some general remarks which might be useful for you.

Style wise I would add spaces after commas, to increase readability. Other than that it looks clean enough, but some comments on what the different parts does, wouldn't hurt.

But my main point in this review is this: Device code structures after you have a need for it, and don't create structure first and then ask for a need of it.

You've done it the other way around, which is kind of strange, but could be a good learning experience for you. Could it be useful for some cases? Who knows. In general, most likely not, as normally you have the use case first, and then code a solution to it.