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-02 17:16:49

On 04/02/09 14:34, Larry Evans wrote:
 > On 03/13/09 18:49, David Abrahams wrote:
[snip]
 > Lists can only be constructed backwards because lists don't have a
 > push_back?  IOW, with only a push_front, the lists have to be
 > constructed:
 >
 >   push_front
 >   < push_front
 >     < push_front
 >       < list<>
 >       , i3
 >       >
 >     , i2
 >     >
 >   , i1
 >   >
 >
 > to create list<i1,i2,i3>?  So, a traversal from back to front,
 > (i3->i1), is needed, and, for example,
 >
 >   fold<vector<i1,i2,i3>,list<>, push_front<_,_> >
 >
 > would give:
 >
 >   list<i3,i2,i1>
 >
 > Instead, to create list<i1,i2,i3> from some sequence, S<i1,i2,i3>,
 > reverse_fold would be needed:
 >
 >   reverse_fold<S<i1,i2,i3>,list<>, push_front<_,_> >
 >
 > Is that about what you mean?
 >
[snip]

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.  Another reason I'm interested is that
both vector and list are implemented using what looks like binary
operators, v_item, and l_item, and I'm wondering why they couldn't be
done with some sort of fold method.  After all the vector
super:

   v_item<T_i, vector<T_i-1,T_i-2,...> >

looks like it could be done with a fold.  Inspired by that example,
I actually coded one:

-{--code fold_reverse--
   template
   < typename IterNow
   , typename IterEnd
   , typename State
   , typename ForwardOp
   , typename NextOp=next<arg<1> >
   >
   struct
fold_reverse_iter
: apply
   < ForwardOp
   , typename fold_reverse_iter
     < typename apply<NextOp,IterNow>::type
     , IterEnd
     , State
     , ForwardOp
     , NextOp
     >::type
   , IterNow
   >
{
};

   template
   < typename IterEnd
   , typename State
   , typename ForwardOp
   , typename NextOp
   >
   struct
fold_reverse_iter
   < IterEnd
   , IterEnd
   , State
   , ForwardOp
   , NextOp
   >
{
         typedef
       State
     type
     ;
};

   template
   < class Sequence
   , class State
   , class ForwardOp
   >
   struct
fold_reverse
: fold_reverse_iter
   < typename begin<Sequence>::type
   , typename end<Sequence>::type
   , State
   , typename lambda<ForwardOp>::type::template
     apply
     < arg<1>
     , deref<arg<2> >
     >
   >
{
};

-}--code fold_reverse--

Note how similar it is to the normal fold for the variadic compiler:

-{--code fold--

   template
   < typename IterNow
   , typename IterEnd
   , typename State
   , typename ForwardOp
   , typename NextOp=next<arg<1> >
   >
   struct
fold_iter
: fold_iter
   < typename apply<NextOp,IterNow>::type
   , IterEnd
   , typename apply<ForwardOp,State,IterNow>::type
   , ForwardOp
   , NextOp
   >
{
};

   template
   < typename IterEnd
   , typename State
   , typename ForwardOp
   , typename NextOp
   >
   struct
fold_iter
   < IterEnd
   , IterEnd
   , State
   , ForwardOp
   , NextOp
   >
{
         typedef
       State
     type
     ;
};

   template
   < typename Sequence
   , typename State
   , typename ForwardOp
   >
   struct
fold
: fold_iter
   < typename begin<Sequence>::type
   , typename end<Sequence>::type
   , State
   , typename lambda<ForwardOp>::type::template
     apply
     < arg<1>
     , deref<arg<2> >
     >
   >
{
};

-}--code fold--

So, back to v_item and fold_reverse_iter.

The difference is that instead of:

   v_item
   < T0
   , vector<T...>
   >

in fold_reverse_iter there's:

   apply
   < ForwardOp
   , typename fold_reverse_iter
     < typename apply<NextOp,IterNow>::type
     , IterEnd
     , State
     , ForwardOp
     , NextOp
     >::type
   , IterNow
   >

where ForwardOp would be push_front<arg<1>, deref<arg<2> > >.

So, my next question is what's the advantage of using v_item<
vector<T...> > instead of using fold_reverse_iter?  I guess you could
say it's more complicated, but then it reuses code and it's not (IMO)
that much more complicated.  OTOH, using iter_fold_if is more
complicated and the justification may be that it also reuses code;
however, I'm wondering if it could be simplified by using something
like the fold_reverse_iter.

-regards,
Larry