Re: [boost] [mpl]iter_fold_if Forward Backward rationale?

Subject: Re: [boost] [mpl]iter_fold_if Forward Backward rationale?
From: Larry Evans (cppljevans_at_[hidden])
Date: 2009-04-04 13:41:50

On 04/04/09 02:05, Larry Evans wrote:
 > On 04/03/09 21:31, David Abrahams wrote:
[snip]

 >> You apply the forward function "on the way in" and the reverse one
 >> "on the way out" of the recursion.
 >
 > I thought it would be interesting to compare the mpl folds with the
 > haskell folds.
 >
 >  From pp. 116-117 of:
 >
 >   http://haskell.org/defxnxtxon/haskell98-report.pdf
 >
 > the following is a trace of the execution of foldl
 > and foldr where the argument order is modified to reflect that of mpl
 > fold argument order. IOW:
 >
 >   [x1,x2,x3] represents an mpl sequence
 >   z represents the initial state, e.g. list<>.
 >   F represents the binary operation, e.g.push_front.
 >
 > Now, the foldl trace:
 >
 >     foldl([x1,x2,x3],z,F)
 >   = foldl([x2,x3],F(z,x1),F)
 >   = foldl([x3],F(F(z,x1),x2),F)
 >   = F(F(F(z,x1),x2),x3)
 >
 > which looks like mpl::fold since, when F == push_front, the resulting
 > sequence is reversed, which is what happens with mpl::fold.
 >
 > Then, the foldr trace:
 >
 >     foldr([x1,x2,x3],z,F)
 >   = F(x1,foldr([x2,x3],z,F))
 >   = F(x1,F(x2,foldr([x3],z,F)))
 >   = F(x1,F(x2,F(x3,z)))
 >
 > which looks like mpl::fold_reverse since, when F == push_front, the
 > resulting sequence is the same is the start sequence, which is what
 > happens with mpl::fold_reverse.  OOPS, push_front takes the sequence
 > as 1st arg, but F(x3,z) has the sequence (e.g. list<> ) as the 2nd
 > argument.
 >
 > Now, is the F in the foldr applied "on the way out" and the F in the
 > foldl applied " on the way in"?

So now I'm wondering what's the haskell counterpart to iter_fold_if.
Assuming ForwardPredicate and BackwardPredicate are always<true_>,
then AFAICT, it would be foldlr defined partially by cases as:

     foldlr([],z,F,B)
   = z

     foldlr([x1],z,F,B)
   = B(x1,F(z,x1))

     foldlr([x1,x2],z,F,B)
   = B(x1,B(x2,F(F(z,x1),x2)))

     foldlr([x1,x2,x3],z,F,B)
   = B(x1,B(x2,B(x3,F(F(F(z,x1),x2),x3))))

Where F is the iter_fold_if ForwardOp and B is the iter_fold_if
BackwardOp.

Now, if B==F==push_front, this would produce a palindrome:

   [x1,x2,x3,x3,x2,x1]

This is demonstrated by the attached program which produces on cout:

***test_iter_fold_if<1> numbers=:
    value:0
***test_iter_fold_if<1> result::state=:
    r_iter:0
    r_iter:1
    r_iter:1
    r_iter:1
    r_iter:0
***test_iter_fold_if<2> numbers=:
    value:0
    value:1
***test_iter_fold_if<2> result::state=:
    r_iter:0
    r_iter:1
    r_iter:2
    r_iter:2
    r_iter:1
    r_iter:0

However, I 've not figured out where the extra number (1 in case of
iter_fold_if<1> and 2 in case of iter_fold_if<2>) is coming from.
OTOH, I haven't tried very hard to figure it out.

-regards,
Larry