# A recursive_sum Template Function Implementation with Unwrap Level in C++

This is a follow-up question for A Summation Function For Various Type Arbitrary Nested Iterable Implementation in C++ and A recursive_transform_view Template Function Implementation. In the previous question, the implementation of recursive_sum template function performs summation operation on input container exhaustively. I am trying to make another version recursive_sum function which is used for dealing with nested iterables with unwrap level in C++.

The experimental implementation

• recursive_sum template function implementation:

template<   std::size_t unwrap_level,
class T>
requires (unwrap_level <= recursive_depth<T>())
constexpr auto recursive_sum(const T& input)
{
if constexpr (recursive_depth<T>() - unwrap_level == 0)
{
return input;
}
else
{
return UL::recursive_transform<unwrap_level>(
input,
[](auto&& element){ return recursive_sum_all(element); }
);
}
}


Full Testing Code

The full testing code:

//  A recursive_sum Template Function Implementation with Unwrap Level in C++

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <complex>
#include <concepts>
#include <deque>
#include <execution>
#include <exception>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <mutex>
#include <numeric>
#include <optional>
#include <queue>
#include <ranges>
#include <stack>
#include <stdexcept>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

//  is_reservable concept
template<class T>
concept is_reservable = requires(T input)
{
input.reserve(1);
};

//  is_sized concept, https://codereview.stackexchange.com/a/283581/231235
template<class T>
concept is_sized = requires(T x)
{
std::size(x);
};

template<typename T>
concept is_summable = requires(T x) { x + x; };

//  recursive_depth function implementation
template<typename T>
constexpr std::size_t recursive_depth()
{
return 0;
}

template<std::ranges::input_range Range>
constexpr std::size_t recursive_depth()
{
return recursive_depth<std::ranges::range_value_t<Range>>() + 1;
}

//  recursive_invoke_result_t implementation
template<typename, typename>
struct recursive_invoke_result { };

template<typename T, std::regular_invocable<T> F>
struct recursive_invoke_result<F, T> { using type = std::invoke_result_t<F, T>; };

template<typename F, template<typename...> typename Container, typename... Ts>
requires (
!std::regular_invocable<F, Container<Ts...>>&&          //  F cannot be invoked to Container<Ts...> directly
std::ranges::input_range<Container<Ts...>>&&
requires { typename recursive_invoke_result<F, std::ranges::range_value_t<Container<Ts...>>>::type; })
struct recursive_invoke_result<F, Container<Ts...>>
{
using type = Container<
typename recursive_invoke_result<
F,
std::ranges::range_value_t<Container<Ts...>>
>::type
>;
};

template<template<typename, std::size_t> typename Container,
typename T,
std::size_t N,
std::regular_invocable<Container<T, N>> F>
struct recursive_invoke_result<F, Container<T, N>>
{
using type = std::invoke_result_t<F, Container<T, N>>;
};

template<template<typename, std::size_t> typename Container,
typename T,
std::size_t N,
typename F>
requires (
!std::regular_invocable<F, Container<T, N>>&&          //  F cannot be invoked to Container<Ts...> directly
requires { typename recursive_invoke_result<F, std::ranges::range_value_t<Container<T, N>>>::type; })
struct recursive_invoke_result<F, Container<T, N>>
{
using type = Container<
typename recursive_invoke_result<
F,
std::ranges::range_value_t<Container<T, N>>
>::type
, N>;
};

template<typename F, typename T>
using recursive_invoke_result_t = typename recursive_invoke_result<F, T>::type;

template<std::size_t, typename, typename, typename...>

template<typename F, class...Ts1, template<class...>class Container1, typename... Ts>
{
using type = Container1<std::invoke_result_t<F,
std::ranges::range_value_t<Container1<Ts1...>>,
std::ranges::range_value_t<Ts>...>>;
};

template<std::size_t unwrap_level, typename F, class...Ts1, template<class...>class Container1, typename... Ts>
requires (  std::ranges::input_range<Container1<Ts1...>> &&
unwrap_level - 1,
F,
std::ranges::range_value_t<Container1<Ts1...>>,
std::ranges::range_value_t<Ts>...>::type; })                //  The rest arguments are ranges
{
using type = Container1<
unwrap_level - 1,
F,
std::ranges::range_value_t<Container1<Ts1...>>,
std::ranges::range_value_t<Ts>...
>::type>;
};

template<std::size_t unwrap_level, typename F, typename T1, typename... Ts>

//  https://codereview.stackexchange.com/a/253039/231235
template<template<class...> class Container = std::vector, std::size_t dim, class T>
constexpr auto n_dim_container_generator(T input, std::size_t times)
{
if constexpr (dim == 0)
{
return input;
}
else
{
return Container(times, n_dim_container_generator<Container, dim - 1, T>(input, times));
}
}

namespace UL                                                //   unwrap_level
{
template< std::ranges::input_range Container,
std::copy_constructible F>
requires (std::ranges::view<Container>&&
std::is_object_v<F>)
constexpr auto make_view(const Container& input, const F& f) noexcept
{
return std::ranges::transform_view(
input,
[&f](const auto&& element) constexpr { return recursive_transform(element, f ); } );
}

/* Override make_view to catch dangling references.  A borrowed range is
* safe from dangling..
*/
template <std::ranges::input_range T>
requires (!std::ranges::borrowed_range<T>)
constexpr std::ranges::dangling make_view(T&&) noexcept
{
return std::ranges::dangling();
}

//  clone_empty_container template function implementation
template< std::size_t unwrap_level = 1,
std::ranges::input_range Container,
std::copy_constructible F>
requires (std::ranges::view<Container>&&
std::is_object_v<F>)
constexpr auto clone_empty_container(const Container& input, const F& f) noexcept
{
const auto view = make_view(input, f);
return output;
}

//  recursive_transform template function implementation (the version with unwrap_level template parameter)
template<   std::size_t unwrap_level = 1,
class T,
std::copy_constructible F>
requires (unwrap_level <= recursive_depth<T>()&&        //  handling incorrect unwrap levels more gracefully, https://codereview.stackexchange.com/a/283563/231235
std::ranges::view<T>&&
std::is_object_v<F>)
constexpr auto recursive_transform(const T& input, const F& f)
{
if constexpr (unwrap_level > 0)
{
auto output = clone_empty_container(input, f);
if constexpr (is_reservable<decltype(output)>&&
is_sized<decltype(input)>)
{
output.reserve(input.size());
std::ranges::transform(
input,
std::ranges::begin(output),
[&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); }
);
}
else
{
std::ranges::transform(
input,
std::inserter(output, std::ranges::end(output)),
[&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); }
);
}
return output;
}
else if constexpr(std::regular_invocable<F, T>)
{
return std::invoke(f, input);
}
else
{
static_assert(!std::regular_invocable<F, T>, "Uninvocable?");
}
}

/* This overload of recursive_transform is to support std::array
*/
template< std::size_t unwrap_level = 1,
template<class, std::size_t> class Container,
typename T,
std::size_t N,
typename F >
requires (std::ranges::input_range<Container<T, N>>)
constexpr auto recursive_transform(const Container<T, N>& input, const F& f)
{

std::ranges::transform(
input,
std::ranges::begin(output),
[&f](auto&& element){ return recursive_transform<unwrap_level - 1>(element, f); }
);

return output;
}

//  recursive_transform function implementation (the version with unwrap_level, without using view)
template<std::size_t unwrap_level = 1, class T, class F>
requires (!std::ranges::view<T>)
constexpr auto recursive_transform(const T& input, const F& f)
{
if constexpr (unwrap_level > 0)
{
static_assert(unwrap_level <= recursive_depth<T>(),
"unwrap level higher than recursion depth of input");   //  trying to handle incorrect unwrap levels more gracefully
std::ranges::transform(
input,                      //  passing a range to std::ranges::transform()
std::inserter(output, std::ranges::end(output)),
[&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); }
);
return output;
}
else
{
return std::invoke(f, input);   //   use std::invoke()
}
}
}

namespace NonUL
{

template< std::ranges::input_range Container,
std::copy_constructible F>
requires (std::ranges::input_range<Container>&&
std::ranges::view<Container>&&
std::is_object_v<F>)
constexpr auto make_view(const Container& input, const F& f) noexcept
{
return std::ranges::transform_view(
input,
[&f](const auto&& element) constexpr { return recursive_transform(element, f ); } );
}

/* Override make_view to catch dangling references.  A borrowed range is
* safe from dangling..
*/
template <std::ranges::input_range T>
requires (!std::ranges::borrowed_range<T>)
constexpr std::ranges::dangling make_view(T&&) noexcept
{
return std::ranges::dangling();
}

/* Base case of NonUL::recursive_transform template function
https://codereview.stackexchange.com/a/283581/231235
*/
template<   typename T,
std::regular_invocable<T> F>
requires (std::copy_constructible<F>)
constexpr auto recursive_transform( const T& input, const F& f )
{
return std::invoke( f, input );
}

/* The recursive case of NonUL::recursive_transform template function
https://codereview.stackexchange.com/a/283581/231235
*/
template< std::ranges::input_range Container,
std::copy_constructible F>
requires (std::ranges::input_range<Container>&&
std::ranges::view<Container>&&
std::is_object_v<F>)
constexpr auto recursive_transform(const Container& input, const F& f)
{
const auto view = make_view(input, f);
recursive_invoke_result_t<F, Container> output( std::ranges::begin(view), std::ranges::end(view) );

// One last sanity check.
if constexpr( is_sized<Container> && is_sized<recursive_invoke_result_t<F, Container>> )
{
assert( output.size() == input.size() );
}

return output;
}

/* The recursive case of NonUL::recursive_transform template function for std::array
https://codereview.stackexchange.com/a/283581/231235
*/
template< template<typename, std::size_t> typename Container,
typename T,
std::size_t N,
std::copy_constructible F>
requires std::ranges::input_range<Container<T, N>>
constexpr auto recursive_transform(const Container<T, N>& input, const F& f)
{
Container<recursive_invoke_result_t<F, T>, N> output;

std::ranges::transform(                     //  Use std::ranges::transform() for std::arrays
input,
std::ranges::begin(output),
[&f](auto&& element){ return recursive_transform(element, f); }
);

// One last sanity check.
if constexpr( is_sized<Container<T, N>> && is_sized<recursive_invoke_result_t<F, Container<T, N>>> )
{
assert( output.size() == input.size() );
}

return output;
}
}

/*  recursive_sum_all template function performs summation operation on input container exhaustively
*/
template<class T> requires is_summable<T>
auto recursive_sum_all(const T& input)
{
return input;
}

template<std::ranges::input_range T>
auto recursive_sum_all(const T inputArray)
{
typedef typename std::iterator_traits<typename T::iterator>::value_type
value_type;

decltype(recursive_sum_all(std::declval<value_type &&>())) sun_output{};
for (auto& element : inputArray)
{
sun_output += recursive_sum_all(element);
}
return sun_output;
}

template<   std::size_t unwrap_level,
class T>
requires (unwrap_level <= recursive_depth<T>())
constexpr auto recursive_sum(const T& input)
{
if constexpr (recursive_depth<T>() - unwrap_level == 0)
{
return input;
}
else
{
return UL::recursive_transform<unwrap_level>(
input,
[](auto&& element){ return recursive_sum_all(element); }
);
}
}

template<class T>
requires (std::ranges::input_range<T>)
constexpr auto recursive_print(const T& input, const int level = 0)
{
T output = input;
std::cout << std::string(level, ' ') << "Level " << level << ":" << std::endl;
std::transform(input.cbegin(), input.cend(), output.begin(),
[level](auto&& x)
{
std::cout << std::string(level, ' ') << x << std::endl;
return x;
}
);
return output;
}

template<class T>
requires (std::ranges::input_range<T> &&
std::ranges::input_range<std::ranges::range_value_t<T>>)
constexpr T recursive_print(const T& input, const int level = 0)
{
T output = input;
std::cout << std::string(level, ' ') << "Level " << level << ":" << std::endl;
std::transform(input.cbegin(), input.cend(), output.begin(),
[level](auto&& element)
{
return recursive_print(element, level + 1);
}
);
return output;
}

void recursive_sum_tests()
{
auto test_vectors = n_dim_container_generator<std::vector, 4, int>(1, 3);

std::cout << "Play with test_vectors:\n\n";

std::cout << "recursive_sum_all function: \n";
auto recursive_sum_all_result = recursive_sum_all(test_vectors);
std::cout << recursive_sum_all_result << "\n\n";

std::cout << "unwrap_level = 4:\n";
auto test_output_1 = recursive_sum<4>(test_vectors);
recursive_print(test_output_1);
std::cout << "\n\n";

std::cout << "unwrap_level = 3:\n";
auto test_output_2 = recursive_sum<3>(test_vectors);
recursive_print(test_output_2);
std::cout << "\n\n";

std::cout << "unwrap_level = 2:\n";
auto test_output_3 = recursive_sum<2>(test_vectors);
recursive_print(test_output_3);
std::cout << "\n\n";

std::cout << "unwrap_level = 1:\n";
auto test_output_4 = recursive_sum<1>(test_vectors);
recursive_print(test_output_4);
std::cout << "\n\n";

std::cout << "unwrap_level = 0:\n";
auto test_output_5 = recursive_sum<0>(test_vectors);
std::cout << test_output_5 << "\n\n";

return;
}

int main()
{
recursive_sum_tests();

return 0;
}


The output of the test code above:

Play with test_vectors:

recursive_sum_all function:
81

unwrap_level = 4:
Level 0:
Level 1:
Level 2:
Level 3:
1
1
1
Level 3:
1
1
1
Level 3:
1
1
1
Level 2:
Level 3:
1
1
1
Level 3:
1
1
1
Level 3:
1
1
1
Level 2:
Level 3:
1
1
1
Level 3:
1
1
1
Level 3:
1
1
1
Level 1:
Level 2:
Level 3:
1
1
1
Level 3:
1
1
1
Level 3:
1
1
1
Level 2:
Level 3:
1
1
1
Level 3:
1
1
1
Level 3:
1
1
1
Level 2:
Level 3:
1
1
1
Level 3:
1
1
1
Level 3:
1
1
1
Level 1:
Level 2:
Level 3:
1
1
1
Level 3:
1
1
1
Level 3:
1
1
1
Level 2:
Level 3:
1
1
1
Level 3:
1
1
1
Level 3:
1
1
1
Level 2:
Level 3:
1
1
1
Level 3:
1
1
1
Level 3:
1
1
1

unwrap_level = 3:
Level 0:
Level 1:
Level 2:
3
3
3
Level 2:
3
3
3
Level 2:
3
3
3
Level 1:
Level 2:
3
3
3
Level 2:
3
3
3
Level 2:
3
3
3
Level 1:
Level 2:
3
3
3
Level 2:
3
3
3
Level 2:
3
3
3

unwrap_level = 2:
Level 0:
Level 1:
9
9
9
Level 1:
9
9
9
Level 1:
9
9
9

unwrap_level = 1:
Level 0:
27
27
27

unwrap_level = 0:
81



All suggestions are welcome.

The summary information:

• Which question it is a follow-up to?

A recursive_transform_view Template Function Implementation

• What changes has been made in the code since last question?

I am trying to implement recursive_sum template function with unwrap level parameter in this post. In this example, I think that the usage of the version recursive_transform with unwrap level is necessary. If there is any misunderstanding, please let me know.

• Why a new review is being asked for?

Please review the experimental implementation of recursive_sum template function. The function perfroms the summation operation on specified level of container.

# Make it more generic

Summing is a very specific operation. What if you want to calculate the product of all elements instead? Or get the minimum or maximum value? Instead of hardcoding the operation, create a recursive_reduce() that works like std::reduce(). You can still have it sum by default if you don't specify which operation to perform.

# Associativity and initial values

Note that the order in which you perform operations matters. While operator+ is often associative, it doesn't have to be. That's why in C++23, std::ranges::fold_left() and std::ranges::fold_right() were introduced.

Furthermore, some value types might not have a default constructor, thus sun_output{} might not compile. This is why most algorithms in the STL that perform some kind of reduction take an initial value as a parameter. I recommend you add that here as well.

Sometimes you know the input is non-empty, and you want to avoid providing an initial values. C++23 introduced std::ranges::fold_left_first() and related functions for this purpose.

# Meaning of the unwrap level

I was surprised by the fact that your recursive_sum() uses recursive_transform() internally, and by the output from your example code. I would rather have expected the following:

std::vector<std::string> words = {"foo", "bar", "baz", "quux"};

std::cout << recursive_sum<2>(words) << '\n';
std::cout << recursive_sum<1>(words) << '\n';


To output:

:
foobarbazquux


Basically, the call to recursive_sum<2>(words) would unwrap two levels, so it would iterate over the characters in each string, whereas recursive_sum<1>(words) would unwrap only the vector, and add the strings together.

I think that would be more logical. Also consider math libraries that have vector and matrix types that can be iterated over; sometimes you want to sum the elements of a matrix, sometimes you want to sum matrices together, but your code will always sum the innermost elements.

Here is how I would implement a basic recursive_sum():

template<std::size_t unwrap_level,
class R,
class T = recursive_unwrap_type<unwrap_level, R>>
requires (unwrap_level <= recursive_depth<R>())
constexpr auto recursive_sum(const R& input, T init = {})
{
if constexpr (unwrap_level > 0) {
for (const auto& element: input) {
init = recursive_sum(element, init);
}
} else {
init += input;
}

return init;
}


Where recursive_unwrap_type<unwrap_level, R> would give you the type after unwrapping R for unwrap_level levels.

If you want your original behavior, the caller could then combine recursive_transform() and recursive_sum() themselves, like so:

auto test_output_3 = recursive_transform<2>(
test_vectors,
[](auto&& element){ return recursive_sum(element); }
);

• Thank you for answering. > I was surprised by the fact that your recursive_sum() uses recursive_transform() internally. Do you have any other idea for the implementation of recursive_sum function? Or there is any other better way to do this? Commented Apr 20, 2023 at 7:38
• Thank you for updating the answer. I understand the opinion you mentioned. :) Commented Apr 20, 2023 at 11:42