Search code examples
prologhigher-order-functionsmeta-predicate

Prolog Higher-order reduce predicate


We can define a higher-order map predicate as:

map([], [], F).
map([A|As], [B|Bs], F) :-
   call(F, A, B),
   map(As, Bs, F).

Similarly, we can define fold (left) as:

fold([], Acc, Acc, _F).
fold([A|As], B, Acc1, F) :-
   call(F, Acc1, A, Acc2),
   fold(As, B, Acc2, F).

What is the correct definition for reduce (left)? Can we define it as follows?

reduce([A|As], Bs, F) :-   
   fold(As, Bs, A, F).

And reduceback (right) as follows?

reduceback([], Ident, F) :-
   identity(F, Ident).
reduceback([A|As], B, F) :-
   reduceback(As, C, F),
   call(F, C, A, B).

Are these correct?


Solution

  • fold/4 and reduce/3 perform correctly, while without identity/1 reduceback/3 is incomplete. But the control flow seems correct, though

    1 ?- fold([1,2,3],S,0,[X,Y,Z]>>(Z is X+Y)).
    S = 6.
    
    2 ?- reduce([1,2,3],S,[X,Y,Z]>>(Z is X+Y)).
    S = 6.
    

    I've added the declarations

    :- meta_predicate fold(+,?,+,3).
    :- meta_predicate reduce(+,?,3).
    

    that qualify arguments as closures, and used library(yall) for lambdas...

    In Prolog, a common convention is to place output arguments as last, so your definitions are rather unreadable to me....

    edit

    for symmetry with reduce/3, identity/1 seems useless, the last element could be used instead: so it could be

    :- meta_predicate reduceback(+,?,3).
    
    reduceback([Last],Last,_F).
    reduceback([A|As],B,F):-
      reduceback(As,C,F),
      call(F,C,A,B).
    

    test:

    ?- reduceback([1,2,3],S,[X,Y,Z]>>(Z is X+Y)).
    S = 6 ;
    false.
    
    ?- reduceback([1,2,3],S,[X,Y,Z]>>(Z is X-Y)).
    S = 0 ;
    false.