再帰深度を抑えた畳込み関数

FTMPのメタ関数で使われている畳込みの実装アプローチをソースコードと勉強会で発表された資料を参考に理解した(気になった)ので、constexprで再現してみました。パックの分割に当たる操作と、相互再帰を利用して畳み込みがうまく実現されています。foldlとfoldrのコードは殆ど同じですが一応両方載せておきます。

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

#include <sprout/tuple.hpp>
#include <sprout/functional.hpp>
#include <iostream>

// foldl
template <typename Func, typename A, typename Bs>
constexpr A foldl(const Func& f, const A& a, const Bs& bs);

template <typename Func, typename A, typename B>
constexpr A foldl(const Func& f, const A& a, const sprout::tuple<B>& b);

template <typename Func, typename A>
constexpr A foldl(const Func& f, const A& a, const sprout::tuple<>&);

template <typename Func, typename A, typename Bs, sprout::index_t... LIndices,
          sprout::index_t... RIndices>
constexpr A foldl_impl(const Func& f, const A& a, const Bs& bs,
                       sprout::index_tuple<LIndices...>,
                       sprout::index_tuple<RIndices...>) {
  return foldl(
      f, foldl(f, a, sprout::forward_as_tuple(sprout::get<LIndices>(bs)...)),
      sprout::forward_as_tuple(sprout::get<RIndices>(bs)...));
}

template <typename Func, typename A, typename B>
constexpr A foldl(const Func& f, const A& a, const sprout::tuple<B>& b) {
  return f(a, sprout::get<0>(b));
}

template <typename Func, typename A>
constexpr A foldl(const Func&, const A& a, const sprout::tuple<>&) {
  return a;
}

template <typename Func, typename A, typename Bs>
constexpr A foldl(const Func& f, const A& a, const Bs& bs) {
  return foldl_impl(
      f, a, bs,
      sprout::index_range<0, sprout::tuple_size<Bs>::value / 2>::make(),
      sprout::index_range<sprout::tuple_size<Bs>::value / 2,
                          sprout::tuple_size<Bs>::value>::make());
}

// foldr
template <typename Func, typename A, typename Bs>
constexpr A foldr(const Func& f, const A& a, const Bs& bs);

template <typename Func, typename A, typename B>
constexpr A foldr(const Func& f, const A& a, const sprout::tuple<B>& b);

template <typename Func, typename A>
constexpr A foldr(const Func& f, const A& a, const sprout::tuple<>&);

template <typename Func, typename A, typename Bs, sprout::index_t... LIndices,
          sprout::index_t... RIndices>
constexpr A foldr_impl(const Func& f, const A& a, const Bs& bs,
                       sprout::index_tuple<LIndices...>,
                       sprout::index_tuple<RIndices...>) {
  return foldr(
      f, foldr(f, a, sprout::forward_as_tuple(sprout::get<RIndices>(bs)...)),
      sprout::forward_as_tuple(sprout::get<LIndices>(bs)...));
}

template <typename Func, typename A, typename B>
constexpr A foldr(const Func& f, const A& a, const sprout::tuple<B>& b) {
  return f(sprout::get<0>(b), a);
}

template <typename Func, typename A>
constexpr A foldr(const Func&, const A& a, const sprout::tuple<>&) {
  return a;
}

template <typename Func, typename A, typename Bs>
constexpr A foldr(const Func& f, const A& a, const Bs& bs) {
  return foldr_impl(
      f, a, bs,
      sprout::index_range<0, sprout::tuple_size<Bs>::value / 2>::make(),
      sprout::index_range<sprout::tuple_size<Bs>::value / 2,
                          sprout::tuple_size<Bs>::value>::make());
}


int main() {
  std::cout << foldl(sprout::plus<int>{}, 0, sprout::make_tuple(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))
            << std::endl;
  std::cout << foldr(sprout::plus<int>{}, 0, sprout::make_tuple(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))
            << std::endl;
}