Как реализовать boost MPL FOLD в С++ 11 только с использованием пакета параметров?

Вот пример реализации логарифмической глубины рекурсии шаблона fold.

#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;
}

здесь я сначала беру линейный список и разбиваю его на два списка половинной длины, используя метафункцию split.

Когда у меня есть две половины, я fold по первой половине, затем беру результат этого и fold по второй половине.

В то время как работа O(N) выполняется, вы в любой момент находитесь в глубине только O(lg(N)) .

Я не вижу теоретической причины, по которой мы не можем достичь глубины O(lg(lg(N)) , но я не вижу и смысла: при максимальной глубине ~ 1000 вам нужно будет иметь десятки вложенных fold на списки типов длиной в 100 секунд, чтобы исчерпать пространство стека шаблона: по моему опыту, компилятор взрывается задолго до того, как будет достигнут предел логарифмической глубины.

И теперь он компилируется: http://ideone.com/CdKAAT

split — это обычно полезный способ работы с длинными списками без рекурсии один раз для каждого элемента. fold и fold_helper довольно очевидны, если у вас есть логарифмическое split.

Почему ограничение только на упаковку параметров?

Как и во многих решениях для пакетов параметров, вам, вероятно, придется углубиться либо в какую-то перегрузку, либо в частичную специализацию. Учитывая, что вы пишете метафункцию шаблона, я бы выбрал частичную специализацию.

В приведенном ниже примере обрабатывается случай с 0 элементами путем возврата состояния, и мы используем эту позицию в шаблоне для накопления результата. Специализация обрабатывает случай 1+, комбинируя первый элемент с состоянием и рекурсивно вызывая метафункцию шаблона.

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