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

Question

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;

//  recursive_variadic_invoke_result_t implementation
template<std::size_t, typename, typename, typename...>
struct recursive_variadic_invoke_result { };

template<typename F, class...Ts1, template<class...>class Container1, typename... Ts>
struct recursive_variadic_invoke_result<1, F, Container1<Ts1...>, 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...>> &&
            requires { typename recursive_variadic_invoke_result<
                                    unwrap_level - 1,
                                    F,
                                    std::ranges::range_value_t<Container1<Ts1...>>,
                                    std::ranges::range_value_t<Ts>...>::type; })                //  The rest arguments are ranges
struct recursive_variadic_invoke_result<unwrap_level, F, Container1<Ts1...>, Ts...>
{
    using type = Container1<
        typename recursive_variadic_invoke_result<
        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>
using recursive_variadic_invoke_result_t = typename recursive_variadic_invoke_result<unwrap_level, F, T1, Ts...>::type;

//  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);
        recursive_variadic_invoke_result<unwrap_level, F, Container> output(std::span{input});
        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)
    {
        Container<recursive_variadic_invoke_result_t<unwrap_level, F, T>, N> output;

        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
            recursive_variadic_invoke_result_t<unwrap_level, F, T> output{};
            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

Godbolt link

All suggestions are welcome.

The summary information:

Which question it is a follow-up to?

A Summation Function For Various Type Arbitrary Nested Iterable Implementation in C++ and

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.

G. Sliepen · Accepted Answer · 2023-04-20 08:51:52Z

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? — JimmyHu, Commented Apr 20, 2023 at 7:38
Thank you for updating the answer. I understand the opinion you mentioned. :) — JimmyHu, Commented Apr 20, 2023 at 11:42

Stack Exchange Network

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

1 Answer 1

Make it more generic

Associativity and initial values

Meaning of the unwrap level

Your Answer

Not the answer you're looking for? Browse other questions tagged
c++
recursion
template
c++20
constrained-templates
or ask your own question.

Linked

Hot Network Questions

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

1 Answer 1

Make it more generic

Associativity and initial values

Meaning of the unwrap level

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++recursiontemplatec++20constrained-templates or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
c++
recursion
template
c++20
constrained-templates
or ask your own question.