[boost] Re: best way to make {reverse_}fold a sequence

From: David Abrahams (dave_at_[hidden])
Date: 2005-03-01 10:25:50

Larry Evans <cppljevans_at_[hidden]> writes:

> On 02/28/2005 06:35 PM, David Abrahams wrote:
>> Larry Evans <cppljevans_at_[hidden]> writes:
>> 
>>>On 02/28/2005 10:01 AM, David Abrahams wrote:
> [snip]
>>>>You're folding some kind of cons cell, right?  Don't you want to
>>>>implement begin and end on that?
>>>>  template <class A, class B>
>>>>  struct begin<inherit<A,B> >
>>>>  {
>>>>     ...
>>>>  };
>>>>or something?
>>>
>>> Yes.  But how do I know what A or B is.  
>> ??
>> At the point of ... the compiler knows what they are
>
> So, I tried:
> //{--------- cut-here --------
> template <
>    template<typename,typename>class ForwardOpTmpl
>  , typename LeftArg
>  , typename RightArg
>  >
> struct begin < ForwardOpTmpl<LeftArg,RightArg> >
> {
>     typedef ForwardOpTmpl<LeftArg,RightArg> type;
> };

Of course that is way too general.  Not every template that might
match is meant to be a sequence.

(Also: do you really mean your sequence iterators to be the same type
as the sequence itself?)

> template <
>   template<typename,typename>class ForwardOpTmpl
> , typename LeftArg
> , typename RightArg
>>
> struct next < ForwardOpTmpl<LeftArg,RightArg> >
> {
>     typedef RightArg type;
> };
> //}--------- cut-here --------
> But intel-linux said next was ambiguous.  

As above, too general, but I'm curious anyway: ambiguous with what?  A
single declaration can't be ambiguous with itself.

> Also, the above
> code assumes the last arg to fold was:
>
>   ForwardOpTmpl<arg<2>,arg<1> >

No it doesn't.  The last arg to fold has nothing to do with it.  It
might have been a metafunction class.  In fact, fold has nothing to do
with it.

The above code tries to make all type structures built on two-element
class templates look like sequences.  But it's too general and assumes
way too much.  For example, the structure might be a tree.

> I was hoping to be more general, but maybe just for my test,
> it would be OK.

!? *More* general?  That's definitely going down the wrong road.

>>>It has to be the result
>>> of size<Sequence>-1 applications of ForwardOp.  
>>
>> Do you mean that you want to restrict the partial specialization
>> matching to only match your tuple types?  You don't have to use
>> inherit directly, you know; you could just derive your own my_inherit
>> class from it and match that in the partial specialization.  If you
>> only use my_inherit to build these tuples, you're home free.
>> 
> Replacing ForwardOpTmpl with my_inherit, defined as:
>
> template< typename Left, typename Right>
> struct my_inherit: inherit2<Left,Right>
> {
>     typedef my_inherit type;
> };
>
> still got the ambiguous error message with intel-linux.  

Well of course it did.  Just as declaring a class template called
ForwardOpTmpl before writing your begin and next above wouldn't have
changed anything either.

template <class Left, class Right>
struct next<my_inherit<Left,Right> >
{
  // ... whatever
};

would be more appropriate.

> gcc gave some
> other error message.
>
> Even if the above did, work, I'd need an end specialization,
> and that would involve knowing the 2nd arg to fold; 

Again, fold has nothing to do with it.

> hence,
> the specialization would have to be:
>
> template<typename Sequence, typename Start, typename ForwardOp>
> struct end<fold<Sequence,Start,ForwardOp>::type>
> {
> ...
> };
>
> which is doomed to fail (AFAICT) because of the non-deduced
> context.
>
> Or am I missing something again?

Forget about fold.  It's just a metafunction that _you_ happen to be
using to build the eventual sequence type.  The fold algorithm has
nothing to do with building sequences, intrinsically, just as
std::accumulate (its analogue) has nothing to do with any particular
job.  You need to focus on the class of types that gets built by your
code and stop looking at fold.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com