#include <type_traits>
#include <utility>
#include <array>
#include <iostream>

// Library //////////////////////////////////////////////

// Indexing trick
template <int... Is>
struct seq {};
template <int I, int... Is>
struct gen_seq : gen_seq<I - 1, I - 1, Is...> {};
template <int... Is>
struct gen_seq<0, Is...> : seq<Is...> {};

// -- Helpers
namespace {
// Short-cut to get type. Add rvalue-ref if necessary.
template <class T>
typename std::add_rvalue_reference<T>::type val();
// identity operation on types.
template <class T>
struct id { typedef T type; };

// Type of a reduction.  (To make GCC happy)
template <class F, class Arg, class... Args> struct reduced_type;
template <class F, class Arg> struct reduced_type<F, Arg> : id<Arg> {};
template <class F, class A, class B, class... Args>
struct reduced_type<
    F, A, B, Args...> : id<decltype(F()(val<A>(),
                                        val<typename reduced_type<
                                            F, B, Args...>::type>()))> {};

// Type list.
template <class... T> struct type_list {};
template <int I, class T, class... Ts>
struct gen_type_list : gen_type_list<I - 1, T, T, Ts...> {};
template <class T, class... Ts>
struct gen_type_list<0, T, Ts...> : type_list<Ts...> {};

// Type of an array reduction.  (To make GCC happy)
template <class F, class... Args>
typename reduced_type<F, Args...>::type
arr_reduced_type_impl(F, type_list<Args...>);
template <class F, int N, class Arg>
struct arr_reduced_type
    : id<decltype(arr_reduced_type_impl(F(), gen_type_list<N, Arg>()))> {};
}

// -- Argument reduce
// Reduces an argument list by pair-wise application of `Func` beginning from
// the right hand side.
//
//     arg_reduce<Func>()(1, 2, 3)  -->  f(1, f(2, 3)),  where f is Func().
template <class Func>
struct arg_reduce {
    // Edge condition: Single argument.
    template <class Arg>
    constexpr Arg operator()(Arg&& arg) const {
        return std::forward<Arg>(arg);
    }

    // Variadic template recursion
    template <class Arg, class... Args>
    constexpr auto operator()(Arg&& arg, Args&&... args)
        const -> typename reduced_type<Func, Arg, Args...>::type {
        return Func()(std::forward<Arg>(arg),
                   operator()(std::forward<Args>(args)...));
    }
};

// -- Array reduce
// Reduces an array by pair-wise application of `Func` beginning from
// the right hand side.
//
//     arr_reduce<Func>()({{1, 2, 3}})  -->  f(1, f(2, 3)),  where f is Func().
template <class Func>
struct arr_reduce {
  private:
    // !!! TODO: Is this the correct way of forwarding arrays?
    // const ref version
    template <class Arg, std::size_t N, int... Is>
    constexpr auto arr_reduce_impl(const std::array<Arg, N> &arr, seq<Is...>)
        const -> typename arr_reduced_type<Func, N, Arg>::type {
        return arg_reduce<Func>()(std::get<Is>(arr)...);
    }
    // lvalue ref version
    template <class Arg, std::size_t N, int... Is>
    constexpr auto arr_reduce_impl(std::array<Arg, N> &&arr, seq<Is...>)
        const -> typename arr_reduced_type<Func, N, Arg>::type {
        return arg_reduce<Func>()(std::get<Is>(std::move(arr))...);
    }

  public:
    // const ref interface
    template <class Arg, std::size_t N>
    constexpr auto operator()(const std::array<Arg, N> &arr)
        const -> typename arr_reduced_type<Func, N, Arg>::type {
        return arr_reduce_impl(arr, gen_seq<N>{});
    }
    // lvalue ref interface
    template <class Arg, std::size_t N>
    constexpr auto operator()(std::array<Arg, N> &&arr)
        const -> typename arr_reduced_type<Func, N, Arg>::type {
        return arr_reduce_impl(std::move(arr), gen_seq<N>{});
    }
};

// -- Plus
struct plus {
    template <class A, class B>
    constexpr auto operator()(A &&a, B &&b)
        const -> decltype(std::forward<A>(a) + std::forward<B>(b)) {
        return std::forward<A>(a) + std::forward<B>(b);
    }
};

// -- Multiplies
struct multiplies {
    template <class A, class B>
    constexpr auto operator()(A &&a, B &&b)
        const -> decltype(std::forward<A>(a) * std::forward<B>(b)) {
        return std::forward<A>(a) * std::forward<B>(b);
    }
};

// -- Summation
using arg_sum = arg_reduce<plus>;
using arr_sum = arr_reduce<plus>;
// !!! TODO: Why not?
// arg_sum = arg_reduce<plus>();
// arr_sum = arg_reduce<plus>();

// -- Product
using arg_prod = arg_reduce<multiplies>;
using arr_prod = arr_reduce<multiplies>;


// Test ///////////////////////////////////////////////////

int main() {
    std::cout << "arg_sum: " << arg_sum()(1) << ", " << arg_sum()(1, 2, 3, 4)
              << std::endl;
    std::cout << "arr_sum: " << arr_sum()(std::array<int, 1>{ { 1 } }) << ", "
              << arr_sum()(std::array<int, 4>{ { 1, 2, 3, 4 } }) << std::endl;
    std::cout << "arg_prod: " << arg_prod()(1) << ", "
              << arg_prod()(1, 2, 3, 4) << std::endl;
    std::cout << "arr_prod: " << arr_prod()(std::array<int, 1>{ { 1 } })
              << ", " << arr_prod()(std::array<int, 4>{ { 1, 2, 3, 4 } })
              << std::endl;
}