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