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?