# Fun exercise: Transform foldr into pseudo-foldl using CLP(FD) (only for integer arithmetic of course)

To my great amusement and increase in stress levels and back pain, I have written a linear foldl and foldr (nothing surprising here), applied them to a list of integers using a simple function foldy “take accumulator to the power of 2 and add list item” (okay), then got the idea that I can “emulate” foldr(foldy) by using a slightly different foldl, foldy and CLP(FD). The result looks like something amenable to tail-call optimization but the network of arithmetic constraints needs to be built and evaluated, so I’m sure one doesn’t win neither cycles nor memory.

``````% ===
% "foldx" is able to simulate "foldr" as "foldl" (at least syntactically)
% for arithmetic computation over integers
% It uses CLP(FD) to set up a constraint network for the final result as
% the (tail-call-optimizable) recursion progresses. Once the end of the
% list has been reached, the starter value is fed into the network and
% all values, including the result, can be evaluated by the Prolog Processor.
% ===

:- use_module(library(clpfd)). % We are using #= instead of the raw "is".

% ===
% Standard foldl
% ===

foo_foldl(Foldy,[Item|Items],AccDown,Result) :-
!,
call(Foldy,Item,AccDown,AccDownNext),
foo_foldl(Foldy,Items,AccDownNext,Result).

foo_foldl(_,[],AccDown,Result) :-
AccDown=Result.

% ===
% Standard foldr
% ===

foo_foldr(Foldy,[Item|Items],Starter,AccUp) :-
!,
foo_foldr(Foldy,Items,Starter,AccUpPrev),
call(Foldy,Item,AccUpPrev,AccUp).

foo_foldr(_,[],Starter,AccUp) :-
AccUp=Starter.

% ===
% Mutant foldx. Really only works for (arithmetic) constraints.
% ===

foo_foldx(Foldy,[Item|Items],AccDown,AccUp)  :-
!,
call(Foldy,Item,AccDown,AccDownNext,AccUpPrev,AccUp),
foo_foldx(Foldy,Items,AccDownNext,AccUpPrev).

foo_foldx(_,[],AccDown,AccUp) :-
AccDown=AccUp.

% ===
% Functions to be applied during folding
% ===

% ---
% Standard "squadd" (square and add) to be applied by standard "foldl" and "foldr"
% ---

Out #= Item+(In^2).

% ---
% Special "squadd" replacement to be used by "foldlx"
% ---

% When emulating "foldl with squadd"

AccDownNext #= Item+AccDown^2, AccUpPrev = AccUp.

% When emulating "foldr with squadd"

AccDownNext = AccDown, AccUp #= Item+AccUpPrev^2.

% ===
% Tests
% ===

:- begin_tests(foldx).

% ---
% The usual foldl,foldr
% ---

% "foldl" with "squadd", nothing special

% "foldr" with "squadd", nothing special

% ---
% Using "foldx"
% ---

% -> Straightforward evaluation inside "squaddxl", nothing special.