Re: MPL and apply_if trouble

From: David Abrahams (dave_at_[hidden])
Date: 2003-05-20 10:56:46

Tarjei Knapstad <tarjeik_at_[hidden]> writes:

> On Mon, 2003-05-19 at 21:34, David Abrahams wrote:
>> Tarjei Knapstad <tarjeik_at_[hidden]> writes:
>> 
>> > I encountered the following problem today which I've reduced down to a
>> > simple example. Basically what I want to do is recurse through a
>> > typelist (mpl::vector) popping an element each time and end recursion by
>> > using apply_if with mpl::empty<List> as the condition. I've made a
>> > simple Reverse class template to illustrate the problem. (The Reverse
>> > class is of course intended to reverse the contents of a typelist....)
>> >
>> > --------------------- begin code ---------------------
>> >
>> > #include <boost/mpl/front.hpp>
>> > #include <boost/mpl/push_back.hpp>
>> > #include <boost/mpl/pop_front.hpp>
>> > #include <boost/mpl/apply_if.hpp>
>> > #include <boost/mpl/empty.hpp>
>> > #include <boost/mpl/size.hpp>
>> > #include <boost/mpl/vector.hpp>
>> >
>> > using namespace boost::mpl;
>> >
>> > template <typename List>
>> > struct Reverse
>> > {
>> >     typedef typename front<List>::type           FrontElem;
>> >     typedef typename pop_front<List>::type       Rest;
>> >     typedef typename apply_if<
>> >                         empty<Rest>,
>> >                         vector<FrontElem>,
>> >                         typename push_back<typename Reverse<Rest>::Type,
>> >                                            FrontElem>::type
>> >                              >::type             Type;
>> > };
>> >
>> > typedef vector<int,int,long>        List;
>> > typedef Reverse<List>::Type         RevList;
>> >

<snip>

>>and it's easy to see that pop_front<List>::type is
>> evaluated whether List is empty or not.
>>
> ...is it? 

Sure!  What happens when you try to Reverse an empty sequence?

> I thought apply_if<> only instantiated either the 'true' or
> 'false' statement depending on the condition. 

Yes, but it doesn't inhibit evaluation *lexically*.  Whenever you
write ::type, you get a non-lazy evaluation.  In fact, your apply_if
is not delaying anything, since you greedily evaluate the 2nd
argument, and the first argument is already the right type.  You'd get
the first argument correctly because

       vector<T1, T2, ... TN>::type == vector<T1, T2, ... TN>

And for the same reasons, the 2nd argument to apply_if has the right
type but is evaluated early.  Even if you stripped the outer
typename...::type and  wrote: 

     typedef typename apply_if<
         empty<Rest>
       , vector<FrontElem>
       , push_back<
             typename Reverse<Rest>::Type
           , FrontElem
         >
     >::type Type;

you'd still be in trouble because Reverse is being evaluated
greedily.  The code above translates to something like (runtime):

     return (  // select a function object
          Rest.empty()
        ? boost::bind(identity, seq<type>(1, FrontElem))
        : boost::bind(push_back, reverse(Rest), FrontElem)
        )
        (); // now invoke it

If you really want to do it that way, break the thing you want to
delay out into a separate metafunction:

    template <class Seq, class E>
    struct append_reversed
      : push_back<typename Reverse<Seq>::type, E>
    {
    };

    ...

     typedef typename apply_if<
         empty<Rest>
       , vector<FrontElem>
       , append_reversed<Rest,FrontElem>
     >::type Type;

or, apply a lambda expression explicitly:

     typedef typename apply_if<
         empty<Rest>
       , vector<FrontElem>
       , apply<
             lambda<push_back<Reverse<_1>, FrontElem> >
           , Rest
         >
     >::type Type;

>> Some things to note:
>> 
>>      1. If your algorithm is doing repeated pop_fronts, you probably
>>         want a list: since each successive list is a sublist of the
>>         previous one, the new list doesn't cost any instantiations
>> 
>>      2. Barring that, use an iterator_range to avoid instantiating a
>>         new vector at each iteration
>> 
> Thanks, will keep in mind. In fact it looks like I can more or less
> adopt my STL mindset to the MPL which I guess is half the point :) 
> (barring the pop_back stuff ;) )

Oh, and please, do yourself a favor and follow the MPL metafunction
protocol!  That means your result is called "::type", not "::Type".

>>      3. The easy way to do this is 
>> 
>>             mpl::fold<
>>                 List
>>               , mpl::push_front<>
>>               , typename mpl::clear<List>::type>::type
>>             >
>> 
>>         I believe.
>> 
> Thanks a lot, this works great! (except that the push_front and clear
> arguments need to be switched around)
>
> Thanks once again for your help Dave,

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