On 04/03/09 21:31, David Abrahams wrote:
on Thu Apr 02 2009, Larry Evans <cppljevans-AT-suddenlink.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. 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"? -regards, Larry