Skip to main content
Code Review

Return to Answer

added 785 characters in body
Source Link
G. Sliepen
G. Sliepen
  • 69.3k
  • 3
  • 75
  • 180

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

If you want your original behavior, the caller could combine recursive_transform() and recursive_sum() themselves.

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); }
);
Source Link
G. Sliepen
G. Sliepen
  • 69.3k
  • 3
  • 75
  • 180

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.

If you want your original behavior, the caller could combine recursive_transform() and recursive_sum() themselves.