How to implement boost MPL FOLD in C++11 only using parameter pack ?

Question

boost mpl has more common algo - fold . This algo is basic for many other algorithms.

template< typename Seq, typename State, typename Op> struct fold { ... }
//Here Seq is <T0,T1,...,Tn> any sequence.
// result of fold is  op<  op < ...< op<State,T0>::type, T1>::type > ... >, Tn>::type

for more information read link.

Fold in c++11 with variadic templates may redefined following:

 template< typename state, typename op, typename ...elements> struct fold;

How to implement it is not problem, but HOW TO IMPLEMENT IT using only parameter packing is difficult or may unsolveable problem.

Q: Can it to implement only using parameter packing??

I want something like

template< typename OP, typename State, typename ...T>
struct fold
{
     // only for illustration
     typedef  apply< apply<....<apply<Op,State,T>>...>::type type; 
};

Answer 1

Here is a stab at a logarithmic template recursion depth fold implementation.

#include <cstddef>

template<typename... Ts> struct types {};
template<typename T, typename U>
struct concat;
template<typename... Ts, typename... Us>
struct concat< types<Ts...>, types<Us...> > {
  typedef types<Ts..., Us...> result;
};
template<typename Ts, typename Us>
using Concat = typename concat<Ts, Us>::result;

template<std::size_t n, typename Ts>
struct split;
template<std::size_t n, typename... Ts>
struct split<n, types<Ts...>> {
private:
  typedef split<n/2, types<Ts...>> one;
  typedef split<n-n/2, typename one::right> two;
public:
  typedef Concat< typename one::left, typename two::left > left;
  typedef typename two::right right;
};
template<typename... Ts>
struct split<0, types<Ts...>> {
  typedef types<> left;
  typedef types<Ts...> right;
};
template<typename T, typename... Ts>
struct split<1, types<T, Ts...>> {
  typedef types<T> left;
  typedef types<Ts...> right;
};
template<template<typename, typename>class OP, typename State, typename Ts>
struct fold_helper;
template<template<typename, typename>class OP, typename State, typename... Ts>
struct fold_helper<OP, State, types<Ts...>> {
private:
  typedef split<sizeof...(Ts)/2, types<Ts...>> parts;
  typedef typename parts::left left;
  typedef typename parts::right right;
  typedef typename fold_helper<OP, State, left>::result left_result;
public:
  typedef typename fold_helper<OP, left_result, right>::result result;
};
template<template<typename, typename>class OP, typename State>
struct fold_helper<OP, State, types<>> {
  typedef State result;
};
template<template<typename, typename>class OP, typename State, typename T>
struct fold_helper<OP, State, types<T>> {
  typedef typename OP<State,T>::type result;
};
template<template<typename, typename>class OP, typename State, typename... Ts>
struct fold {
  typedef typename fold_helper<OP, State, types<Ts...>>::result type;
};
template<template<typename, typename>class OP, typename State, typename... Ts>
using Fold = typename fold<OP, State, Ts...>::type;

template<typename left, typename right>
struct op_test {
  typedef int type;
};

int main() {
  Fold< op_test, double, int, char, char*, int* > foo = 8;
}

here I first take the linear list, and break it into two half-length lists using the split metafunction.

Once I have two halves, I fold over the first half, then take the result of that and fold over the second half.

While O(N) work is done, you are only O(lg(N)) deep at any point.

I don't see a theoretical reason why we cannot pull off O(lg(lg(N)) depth, but neither do I see the point: with a ~1000 max depth, you'd have to have dozens of nested folds on type lists 100s long to run out of template stack space: in my experience the compiler blows up long before the logarithmic depth limit is reached.

And now it compiles: http://ideone.com/CdKAAT

split is a generally useful way of dealing with long lists without recursing once per element. fold and fold_helper are pretty obvious once you have the logarithmic split.

Answer 2

Why the restriction on only parameter packing?

Like many parameter pack solutions, you're likely going to have to delve into either some sort of overloading or partial specialization. Given that you're writing a template metafunction, I would go with partial specialization.

The below handles the case with 0 elements by returning state, and we use that position in the template to accumulate the result. The specialization handles the 1+ case, by combining the first element with the state, and recursively calling the template metafunction.

template< typename OP, typename State, typename ...T>
struct fold
{
    typedef State type;
};

template<typename OP, typename State, typename Head, typename... Tail>
struct fold< OP, State, Head, Tail...>
{
   typedef typename fold<OP, typename OP::template apply<State,Head>::type, Tail...>::type type;
};

http://ideone.com/DDCCbB