4
\$\begingroup\$

I was wondering... In the standard library of some Prolog systems, there are meta-predicates like maplist and foldl.

In general, when using meta-predicates (like the ones above) with we always need the "foldl" variants. What about the following mapfoldl/5 (mapfoldl//3)?

mapfoldl(P_4,Xs,Zs,S0,S) :-
   list_mapfoldl_(Xs,Zs,S0,S,P_4).

list_mapfoldl_([],[],S,S,_).
list_mapfoldl_([X|Xs],[Y|Ys],S0,S,P_4) :-
   call(P_4,X,Y,S0,S1),
   list_mapfoldl_(Xs,Ys,S1,S,P_4).

What's your take on this code? They isn't this (or something very similar) already in the stdlibs?

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't see folding, only mapping ?.. \$\endgroup\$ – Will Ness Dec 13 '15 at 1:54
  • \$\begingroup\$ @WillNess. call(P_4,X,Y,S0,S1) does both. At this particular level there is no "fold", only "map". "fold" comes into play by how S0, S1, ..., S are threaded through. \$\endgroup\$ – repeat Dec 13 '15 at 7:47
3
\$\begingroup\$

In the Logtalk library, you have a map_reduce/5 predicate:

:- public(map_reduce/5).
:- meta_predicate(map_reduce(2, 3, *, *, *)).
:- mode(map_reduce(+callable, +callable, +term, ?list, ?term), zero_or_more).
:- info(map/5, [
    comment is 'Map a list and apply a fold left (reduce) to the resulting list.',
    argnames is ['Map', 'Reduce', 'Accumulator', 'List', 'Result']
]).

map_reduce(Map, Reduce, Acc, List, Result) :-
    map_reduce_(List, Map, Reduce, Acc, Result).

:- meta_predicate(map_reduce_(*, 2, 3, *, *)).
map_reduce_([], _, _, Result, Result).
map_reduce_([Arg| Args], Map, Reduce, Acc, Result) :-
    call(Map, Arg, Arg2),
    call(Reduce, Acc, Arg2, Acc2),
    map_reduce_(Args, Map, Reduce, Acc2, Result).

A main difference to your code is that you assume a single closure combining both the map and reduce operations in the Logtalk version. You also return the map result in addition to the final fold result.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you! Actually, I see "fold left" and "reduce" as two quite distinct operations. "fold" as a chain, "reduce" as a trees; "fold" as "sequential", "reduce" as parallel. Look at codereview.stackexchange.com/questions/88446/… and the performance differences I observed when calculating an integer product with many multiplicands. Something similar can be seen with "bottom-up merge sort", and presumably many other operations that lean more towards "balanced binary tree" than "linear single-linked list". What's your take on this? \$\endgroup\$ – repeat May 20 '15 at 11:17
  • 1
    \$\begingroup\$ W.r.t. performance, Logtalk includes a meta-compiler that eliminates the meta-call overhead when using map_reduce/5 and other library meta-predicates. \$\endgroup\$ – Paulo Moura May 20 '15 at 11:26
  • 1
    \$\begingroup\$ In the experiment with "reduce" vs "fold", meta-predicate invocation costs are negligible. Taking the amount of actual work into account, big integer multiplication is most efficient when the multiplicands have similar sizes (at least with GMP). The situation is similar with bottom-up merge sort. Still I see that there are many other occasions when meta-compilation shines, particularly when portability comes into play. Thank you. \$\endgroup\$ – repeat May 20 '15 at 14:32
  • 2
    \$\begingroup\$ Please don't get me wrong: I'm very much in favor of meta-compilation! But the speedup depends on the concrete operation being done. It is greatest for cases where there is little work is done per step. In the case of the big-integer product, "reduce" enables using O(N log N) algorithms when "fold" is stuck with O(N^2) algorithms. \$\endgroup\$ – repeat May 20 '15 at 14:46
  • 1
    \$\begingroup\$ Particularly, the idea of compiling the lambdas away (in a portable way) is very appealing! \$\endgroup\$ – repeat May 20 '15 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.