How to implement folding with variadic templates

Question

I have an almost working solution. However, it fails to compile some simple cases, and I can't decipher the error message.

My current solution:

#define AUTO_RETURN( EXPR ) -> decltype( EXPR ) \
{ return EXPR; }

template< typename BinaryFunc, typename First, typename Second >
auto foldl( BinaryFunc&& func, First&& first, Second&& second )
AUTO_RETURN( func( std::forward<First>(first), std::forward<Second>(second) ) )

template<typename BinaryFunc, typename First, typename Second, typename... Rest >
auto foldl( BinaryFunc&& func, First&& first, Second&& second, Rest&&... rest )
AUTO_RETURN(
   foldl(
      std::forward<BinaryFunc>(func),
      func( std::forward<First>(first), std::forward<Second>(second) ),
      std::forward<Rest>(rest)... )
   )

This works as expected:

struct adder
{
   template< int LHS, int RHS >
   std::integral_constant<int,LHS+RHS>
   operator()( std::integral_constant<int,LHS>, std::integral_constant<int,RHS> )
   {
      return {};
   }
};

auto result = foldl( adder(),
      std::integral_constant<int,19>{},
      std::integral_constant<int,23>{}
   );

assert( result.value == 42 );

However this fails to compile.

foldl( adder(),
      std::integral_constant<int,1>{},
      std::integral_constant<int,2>{},
      std::integral_constant<int,3>{},
      std::integral_constant<int,4>{},
   );

Oddly, if I remove all std::forward and rvalue refs from the code it works fine.

What am I doing wrong?
Is this a compiler bug?

I think only `std::forward(rest)...` is failing, the rest looks fine. — ildjarn, May 20 '11 at 00:06
This reminds me of http://stackoverflow.com/questions/3744400/decltype-with-a-variadic-template-function It's possibly the same issue — sellibitze, May 20 '11 at 11:07

Anthony Williams · Accepted Answer · 2011-05-20T15:52:06.380

The problem is that the decltype in the return type of the variadic foldl cannot see the variadic foldl, as it hasn't been fully declared yet, so it cannot recurse to another instantiation of itself.

You can do it with a helper struct:

template<typename BinaryFunc, typename... Args >
struct folder;

template<typename BinaryFunc, typename First, typename Second>
struct folder<BinaryFunc,First,Second>
{
    static auto foldl( BinaryFunc&& func, First&& first, Second&& second )
        AUTO_RETURN( func( std::forward<First>(first), std::forward<Second>(second) ) )
};

template<typename BinaryFunc, typename First, typename Second, typename... Rest >
struct folder<BinaryFunc,First,Second,Rest...>
{
    static auto foldl(BinaryFunc&& func, First&& first, Second&& second, Rest&&... rest )
        AUTO_RETURN(
            (folder<
            BinaryFunc,
             decltype(func( std::forward<First>(first), std::forward<Second>(second) )),Rest...>::
            foldl(
                std::forward<BinaryFunc>(func),
                func( std::forward<First>(first), std::forward<Second>(second) ),
                std::forward<Rest>(rest)... )
                ))
};

template< typename BinaryFunc, typename... Args >
auto foldl( BinaryFunc&& func, Args&& ... args )
AUTO_RETURN(
    (folder<BinaryFunc,Args...>::foldl(
      std::forward<BinaryFunc>(func),
      std::forward<Args>(args)... ))
   )

So, is it not a compiler bug but really a restriction in the C++11 standard? Could you please tell where to look for it in the text of the standard? — Alexey Kukanov, May 20 '11 at 09:15
I believe so. I cannot find anywhere that says the name of the function being declared **is** in scope in the trailing return type, so by default I would therefore say that it **isn't** in scope at this point. See 3.3.2p1 --- the declarator of a function includes the trailing return type. — Anthony Williams, May 20 '11 at 09:57
why did you add use a `Third` template parameter, instead of `First`, `Second`, and `Rest`? — deft_code, May 20 '11 at 15:06
It was left over from my initial code. It is unnecessary; I've removed it from my answer. — Anthony Williams, May 20 '11 at 15:53

score 6 · Answer 2 · edited May 23 '17 at 10:29

Thank you for a great question that caused me to look into a few new areas in C++11.

Anthony W. was faster with a solution; but I still want to share mine, which also uses a helper struct (and it's admittedly more verbose). First, let me share a link to a similar question trailing return type using decltype with a variadic template function; the answers there are based on the same idea of a helper struct, so their authors deserve credit.

The code below is checked with ideone. Note that it does not use AUTO_RETURN anymore, as the helper struct now takes care of the type.

template< typename BinaryFunc, typename First, typename... Types >
struct helper;

template< typename BinaryFunc, typename First>
struct helper<BinaryFunc, First> {
    typedef decltype(std::declval<First>()) type;
};

template< typename BinaryFunc, typename First, typename Second >
struct helper<BinaryFunc, First, Second> {
    typedef decltype(
        std::declval<BinaryFunc>()( std::declval<First>(), std::declval<Second>() )
    ) type;
};

template< typename BinaryFunc, typename First, typename Second, typename... Rest >
struct helper<BinaryFunc, First, Second, Rest...>  {
    typedef typename helper< BinaryFunc,
                             typename helper<BinaryFunc, First, Second>::type,
                             Rest...
                           >::type
                     type;
};

template< typename BinaryFunc, typename First, typename Second >
typename helper<BinaryFunc, First, Second>::type
foldl( BinaryFunc&& func, First&& first, Second&& second ) {
    return func( std::forward<First>(first), std::forward<Second>(second) );
}

template< typename BinaryFunc, typename First, typename Second, typename... Rest >
typename helper<BinaryFunc, First, Second, Rest...>::type
foldl( BinaryFunc&& func, First&& first, Second&& second, Rest&&... rest ) {
   return foldl(
      std::forward<BinaryFunc>(func),
      func( std::forward<First>(first), std::forward<Second>(second) ),
      std::forward<Rest>(rest)...
   );
}

How to implement folding with variadic templates

2 Answers2

Linked