
Boost : 
Subject: Re: [boost] [mpl]iter_fold_if Forward Backward rationale?
From: Larry Evans (cppljevans_at_[hidden])
Date: 20090404 03:05:45
On 04/03/09 21:31, David Abrahams wrote:
> on Thu Apr 02 2009, Larry Evans <cppljevansATsuddenlink.net> wrote:
>
>> One reason I'm interested is that I can't figure out how reverse_fold
>> would work on a sequence, S, such that begin<S>::type with just a
>> forward iterator. I would have thought that you'd need a
>> bidirectional iterator in order to traverse backwards; yet:
>>
>> https://svn.boost.org/trac/boost/browser/trunk/libs/mpl/test/fold.cpp#L46
>>
>> shows that it works on lists.
>
> More later, but remember there's recursion involved. You apply the
> forward function "on the way in" and the reverse one "on the way out" of
> the recursion.
>
Thanks David.
I thought it would be interesting to compare the mpl folds with the
haskell folds.
From pp. 116117 of:
http://haskell.org/defxnxtxon/haskell98report.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"?
regards,
Larry
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk