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 fold
s 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
.