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

Question

This is a follow-up question for A recursive_transform_reduce Function for Various Type Arbitrary Nested Iterable Implementation in C++ and recursive_invocable and recursive_project_invocable Concept Implementation in C++. I am trying to implement another version recursive_transform_reduce function which takes unwrap_level as an input in this post. Moreover, the recursive_invocable concept is used here, also.

The Usage Description

Similar to std::transform_reduce, the purpose of recursive_transform_reduce template function is to apply a function (unary operation) to each element located in the specified unwrap level in the given range then reduce the results with a binary operation. There are four parameters in recursive_transform_reduce function (the version without execution policy) and the first and second parameters are necessary (The second one is to determine the output type).

The experimental implementation

recursive_transform_reduce Template Function

//  recursive_transform_reduce template function implementation
template<std::size_t unwrap_level, class Input, class T, class UnaryOp = std::identity, class BinaryOp = std::plus<T>>
requires(recursive_invocable<unwrap_level, UnaryOp, Input>)
constexpr auto recursive_transform_reduce(const Input& input, T init = {}, const UnaryOp& unary_op = {}, const BinaryOp& binop = std::plus<T>())
{
    if constexpr (unwrap_level > 0)
    {
        return std::transform_reduce(std::ranges::begin(input), std::ranges::end(input), init, binop, [&](auto& element) {
            return recursive_transform_reduce<unwrap_level - 1>(element, init, unary_op, binop);
        });
    }
    else
    {
        return std::invoke(binop, init, std::invoke(unary_op, input));
    }
}

//  recursive_transform_reduce template function implementation with execution policy
template<std::size_t unwrap_level, class ExecutionPolicy, class Input, class T, class UnaryOp = std::identity, class BinaryOp = std::plus<T>>
requires(recursive_invocable<unwrap_level, UnaryOp, Input>&&
         std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>)
constexpr auto recursive_transform_reduce(ExecutionPolicy execution_policy, const Input& input, T init = {}, const UnaryOp& unary_op = {}, const BinaryOp& binop = std::plus<T>())
{
    if constexpr (unwrap_level > 0)
    {
        return std::transform_reduce(
            execution_policy,
            std::ranges::begin(input),
            std::ranges::end(input),
            init,
            binop,
            [&](auto& element) {
            return recursive_transform_reduce<unwrap_level - 1>(execution_policy, element, init, unary_op, binop);
        });
    }
    else
    {
        return std::invoke(binop, init, std::invoke(unary_op, input));
    }
}

Full Testing Code

The full testing code:

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

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <concepts>
#include <deque>
#include <execution>
#include <exception>
//#include <experimental/ranges/algorithm>
#include <experimental/array>
#include <functional>
#include <iostream>
#include <iterator>
#include <ranges>
#include <string>
#include <utility>
#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_unwrap_type_t struct implementation
template<std::size_t, typename, typename...>
struct recursive_unwrap_type { };

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

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

template<std::size_t unwrap_level, typename T1, typename... Ts>
using recursive_unwrap_type_t = typename recursive_unwrap_type<unwrap_level, T1, Ts...>::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;

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

template<   typename F, 
            template<class, std::size_t> class Container,
            typename T,
            std::size_t N>
struct recursive_array_invoke_result<1, F, Container<T, N>>
{
    using type = Container<
        std::invoke_result_t<F, std::ranges::range_value_t<Container<T, N>>>,
        N>;
};

template<   std::size_t unwrap_level,
            typename F, 
            template<class, std::size_t> class Container,
            typename T,
            std::size_t N>
requires (  std::ranges::input_range<Container<T, N>> &&
            requires { typename recursive_array_invoke_result<
                                    unwrap_level - 1,
                                    F,
                                    std::ranges::range_value_t<Container<T, N>>>::type; })                //  The rest arguments are ranges
struct recursive_array_invoke_result<unwrap_level, F, Container<T, N>>
{
    using type = Container<
        typename recursive_array_invoke_result<
        unwrap_level - 1,
        F,
        std::ranges::range_value_t<Container<T, N>>
        >::type, N>;
};

template<   std::size_t unwrap_level,
            typename F,
            template<class, std::size_t> class Container,
            typename T,
            std::size_t N>
using recursive_array_invoke_result_t = typename recursive_array_invoke_result<unwrap_level, F, Container<T, N>>::type;

//  recursive_array_unwrap_type struct implementation, https://stackoverflow.com/a/76347485/6667035
template<std::size_t, typename>
struct recursive_array_unwrap_type { };

template<template<class, std::size_t> class Container,
              typename T,
              std::size_t N>
struct recursive_array_unwrap_type<1, Container<T, N>>
{
    using type = std::ranges::range_value_t<Container<T, N>>;
};

template<std::size_t unwrap_level, template<class, std::size_t> class Container,
              typename T,
              std::size_t N>
requires (  std::ranges::input_range<Container<T, N>> &&
            requires { typename recursive_array_unwrap_type<
                                    unwrap_level - 1,
                                    std::ranges::range_value_t<Container<T, N>>>::type; })                //  The rest arguments are ranges
struct recursive_array_unwrap_type<unwrap_level, Container<T, N>>
{
    using type = typename recursive_array_unwrap_type<
        unwrap_level - 1,
        std::ranges::range_value_t<Container<T, N>>
        >::type;
};

template<std::size_t unwrap_level, class Container>
using recursive_array_unwrap_type_t = typename recursive_array_unwrap_type<unwrap_level, Container>::type;

//  https://codereview.stackexchange.com/a/253039/231235
template<std::size_t dim, class T, template<class...> class Container = std::vector>
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<dim - 1, T, Container>(input, times));
    }
}

template<std::size_t dim, std::size_t times, class T>
constexpr auto n_dim_array_generator(T input)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        std::array<decltype(n_dim_array_generator<dim - 1, times>(input)), times> output;
        for (size_t i = 0; i < times; i++)
        {
            output[i] = n_dim_array_generator<dim - 1, times>(input);
        }
        return output;
    }
}

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

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

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

template<typename T_Base, std::ranges::input_range Range>
requires (!std::same_as<Range, T_Base>)
constexpr std::size_t recursive_depth()
{
    return recursive_depth<T_Base, std::ranges::range_value_t<Range>>() + std::size_t{1};
}

//  is_recursive_invocable template function implementation
template<std::size_t unwrap_level, class F, class... T>
requires(unwrap_level <= recursive_depth<T...>())
static constexpr bool is_recursive_invocable()
{
    if constexpr (unwrap_level == 0) {
        return std::invocable<F, T...>;
    } else {
        return is_recursive_invocable<
                    unwrap_level - 1,
                    F,
                    std::ranges::range_value_t<T>...>();
    }
}

//  recursive_invocable concept
template<std::size_t unwrap_level, class F, class... T>
concept recursive_invocable =
        is_recursive_invocable<unwrap_level, F, T...>();

//  is_recursive_project_invocable template function implementation
template<std::size_t unwrap_level, class Proj, class F, class... T>
requires(unwrap_level <= recursive_depth<T...>() &&
         recursive_invocable<unwrap_level, Proj, T...>)
static constexpr bool is_recursive_project_invocable()
{
    if constexpr (unwrap_level == 0) {
        return std::invocable<F, std::invoke_result_t<Proj, T...>>;
    } else {
        return is_recursive_project_invocable<
                    unwrap_level - 1,
                    Proj,
                    F,
                    std::ranges::range_value_t<T>...>();
    }
}

//  recursive_project_invocable concept
template<class F, std::size_t unwrap_level, class Proj, class... T>
concept recursive_projected_invocable =
        is_recursive_project_invocable<unwrap_level, Proj, F, T...>();

/*  recursive_all_of template function implementation with unwrap level
*/
template<std::size_t unwrap_level, class T, class Proj = std::identity, 
         recursive_projected_invocable<unwrap_level, Proj, T> UnaryPredicate>
constexpr auto recursive_all_of(T&& value, UnaryPredicate&& p, Proj&& proj = {}) {
    if constexpr (unwrap_level > 0)
    {
        return std::ranges::all_of(value, [&](auto&& element) {
            return recursive_all_of<unwrap_level - 1>(element, p, proj);
        });
    }
    else
    {
        return std::invoke(p, std::invoke(proj, value));
    }
}

/*  recursive_find template function implementation with unwrap level
*/
template<std::size_t unwrap_level, class R, class T, class Proj = std::identity>
requires(recursive_invocable<unwrap_level, Proj, R>)
constexpr auto recursive_find(R&& range, T&& target, Proj&& proj = {})
{
    if constexpr (unwrap_level > 0)
    {
        return std::ranges::find_if(range, [&](auto& element) {
            return recursive_find<unwrap_level - 1>(element, target, proj);
        }) != std::ranges::end(range);
    }
    else
    {
        return range == std::invoke(proj, target);
    }
}

template<std::size_t unwrap_level, class ExecutionPolicy, class R, class T, class Proj = std::identity>
requires(recursive_invocable<unwrap_level, Proj, R>&&
         std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>)
constexpr auto recursive_find(ExecutionPolicy execution_policy, R&& range, T&& target, Proj&& proj = {})
{
    if constexpr (unwrap_level > 0)
    {
        return std::find_if(execution_policy,
                    std::ranges::begin(range),
                    std::ranges::end(range),
                    [&](auto& element) {
            return recursive_find<unwrap_level - 1>(execution_policy, element, target, proj);
        }) != std::ranges::end(range);
    }
    else
    {
        return range == std::invoke(proj, target);
    }
}

/*  recursive_find_if template function implementation with unwrap level
*/
template<std::size_t unwrap_level, class T, class Proj = std::identity, 
         recursive_projected_invocable<unwrap_level, Proj, T> UnaryPredicate>
constexpr auto recursive_find_if(T&& value, UnaryPredicate&& p, Proj&& proj = {}) {
    if constexpr (unwrap_level > 0)
    {
        return std::ranges::find_if(value, [&](auto& element) {
            return recursive_find_if<unwrap_level - 1>(element, p, proj);
        }) != std::ranges::end(value);
    }
    else
    {
        return std::invoke(p, std::invoke(proj, value));
    }
}

/*  recursive_find_if_not template function implementation with unwrap level
*/
template<std::size_t unwrap_level, class T, class Proj = std::identity, 
         recursive_projected_invocable<unwrap_level, Proj, T> UnaryPredicate>
constexpr auto recursive_find_if_not(T&& value, UnaryPredicate&& p, Proj&& proj = {}) {
    if constexpr (unwrap_level > 0)
    {
        return std::ranges::find_if(value, [&](auto& element) {
            return recursive_find_if_not<unwrap_level - 1>(element, p, proj);
        }) != std::ranges::end(value);
    }
    else
    {
        return !std::invoke(p, std::invoke(proj, value));
    }
}

//  recursive_any_of template function implementation with unwrap level
template<std::size_t unwrap_level, class T, class Proj = std::identity, 
         recursive_projected_invocable<unwrap_level, Proj, T> UnaryPredicate>
constexpr auto recursive_any_of(T&& value, UnaryPredicate&& p, Proj&& proj = {})
{
    return recursive_find_if<unwrap_level>(value, p, proj);
}

//  recursive_none_of template function implementation with unwrap level
template<std::size_t unwrap_level, class T, class Proj = std::identity, 
         recursive_projected_invocable<unwrap_level, Proj, T> UnaryPredicate>
constexpr auto recursive_none_of(T&& value, UnaryPredicate&& p, Proj&& proj = {})
{
    return !recursive_any_of<unwrap_level>(value, p, proj);
}

template<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(std::ranges::cbegin(input), std::ranges::cend(input), output.begin(), 
        [level](auto&& x)
        {
            std::cout << std::string(level, ' ') << x << std::endl;
            return x;
        }
    );
    return output;
}

template<std::ranges::input_range T>
requires (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::ranges::transform(std::ranges::cbegin(input), std::ranges::cend(input), std::ranges::begin(output),
        [level](auto&& element)
        {
            return recursive_print(element, level + 1);
        }
    );
    return output;
}

//  recursive_transform_reduce template function implementation
template<std::size_t unwrap_level, class Input, class T, class UnaryOp = std::identity, class BinaryOp = std::plus<T>>
requires(recursive_invocable<unwrap_level, UnaryOp, Input>)
constexpr auto recursive_transform_reduce(const Input& input, T init = {}, const UnaryOp& unary_op = {}, const BinaryOp& binop = std::plus<T>())
{
    if constexpr (unwrap_level > 0)
    {
        return std::transform_reduce(std::ranges::begin(input), std::ranges::end(input), init, binop, [&](auto& element) {
            return recursive_transform_reduce<unwrap_level - 1>(element, init, unary_op, binop);
        });
    }
    else
    {
        return std::invoke(binop, init, std::invoke(unary_op, input));
    }
}

//  recursive_transform_reduce template function implementation with execution policy
template<std::size_t unwrap_level, class ExecutionPolicy, class Input, class T, class UnaryOp = std::identity, class BinaryOp = std::plus<T>>
requires(recursive_invocable<unwrap_level, UnaryOp, Input>&&
         std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>)
constexpr auto recursive_transform_reduce(ExecutionPolicy execution_policy, const Input& input, T init = {}, const UnaryOp& unary_op = {}, const BinaryOp& binop = std::plus<T>())
{
    if constexpr (unwrap_level > 0)
    {
        return std::transform_reduce(
            execution_policy,
            std::ranges::begin(input),
            std::ranges::end(input),
            init,
            binop,
            [&](auto& element) {
            return recursive_transform_reduce<unwrap_level - 1>(execution_policy, element, init, unary_op, binop);
        });
    }
    else
    {
        return std::invoke(binop, init, std::invoke(unary_op, input));
    }
}

//  recursive_size template function implementation
template<class T> requires (!std::ranges::range<T>)
constexpr auto recursive_size(const T& input)
{
    return std::size_t{1};
}

template<std::ranges::range Range> requires (!(std::ranges::input_range<std::ranges::range_value_t<Range>>))
constexpr auto recursive_size(const Range& input)
{
    return std::ranges::size(input);
}

template<std::ranges::range Range> requires (std::ranges::input_range<std::ranges::range_value_t<Range>>)
constexpr auto recursive_size(const Range& input)
{
    return std::transform_reduce(std::ranges::begin(input), std::ranges::end(input), std::size_t{}, std::plus<std::size_t>(), [](auto& element) {
        return recursive_size(element);
        });
}

template<typename T>
concept is_recursive_sizeable = requires(T x)
{
    recursive_size(x);
};

//  Copy from https://stackoverflow.com/a/37264642/6667035
#ifndef NDEBUG
#   define M_Assert(Expr, Msg) \
    __M_Assert(#Expr, Expr, __FILE__, __LINE__, Msg)
#else
#   define M_Assert(Expr, Msg) ;
#endif

void __M_Assert(const char* expr_str, bool expr, const char* file, int line, const char* msg)
{
    if (!expr)
    {
        std::cerr << "Assert failed:\t" << msg << "\n"
            << "Expected:\t" << expr_str << "\n"
            << "Source:\t\t" << file << ", line " << line << "\n";
        abort();
    }
}

void recursive_transform_reduce_tests()
{
    auto test_vectors_1 = n_dim_container_generator<1, int, std::vector>(1, 3);
    //  basic usage case
    M_Assert(recursive_transform_reduce<1>(test_vectors_1, 0) == 3, "Basic usage case failed");

    //  basic usage case with execution policy
    M_Assert(recursive_transform_reduce<1>(std::execution::par, test_vectors_1, 0) == 3,
        "Basic usage case with execution policy failed");

    //  test case with unary operation
    M_Assert(recursive_transform_reduce<1>(
        test_vectors_1,
        0,
        [&](auto&& element) { return element + 1; }) == 6,
        "Test case with unary operation failed");

    //  test case with unary operation, execution policy
    M_Assert(recursive_transform_reduce<1>(
        std::execution::par,
        test_vectors_1,
        0,
        [&](auto&& element) { return element + 1; }) == 6,
        "Test case with unary operation, execution policy failed");

    //  test case with unary operation and binary operation
    M_Assert(recursive_transform_reduce<1>(
        test_vectors_1,
        1,
        [&](auto&& element) { return element + 1; },
        [&](auto&& element1, auto&& element2) { return element1 * element2; }) == 8,
        "Test case with unary operation and binary operation failed");

    //  test case with unary operation, binary operation and execution policy
    M_Assert(recursive_transform_reduce<1>(
        std::execution::par,
        test_vectors_1,
        1,
        [&](auto&& element) { return element + 1; },
        [&](auto&& element1, auto&& element2) { return element1 * element2; }) == 8,
        "Test case with unary operation, binary operation and execution policy failed");

    auto test_string_vector_1 = n_dim_container_generator<1, std::string, std::vector>("1", 3);
    //  test case with std::string
    M_Assert(recursive_transform_reduce<1>(test_string_vector_1, std::string("")) == "111",
        "Test case with std::string failed");

    //  test case with std::string, execution policy
    M_Assert(recursive_transform_reduce<1>(
        std::execution::par,
        test_string_vector_1, std::string("")) == "111",
        "Test case with std::string, execution policy failed");

    //  test case with std::string, unary operation
    M_Assert(recursive_transform_reduce<1>(
        test_string_vector_1,
        std::string(""),
        [&](auto&& element) { return element + "2";}) == "121212",
        "Test case with std::string, unary operation failed");

    //  test case with std::string, unary operation, execution policy
    M_Assert(recursive_transform_reduce<1>(
        std::execution::par,
        test_string_vector_1,
        std::string(""),
        [&](auto&& element) { return element + "2";}) == "121212",
        "Test case with std::string, unary operation, execution policy failed");

    std::cout << "All tests passed!\n";

    return;
}

int main()
{
    auto start = std::chrono::system_clock::now();
    recursive_transform_reduce_tests();
    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::time_t end_time = std::chrono::system_clock::to_time_t(end);
    std::cout << "Computation finished at " << std::ctime(&end_time) << "elapsed time: " << elapsed_seconds.count() << '\n';
    return EXIT_SUCCESS;
}

The output of the test code above:

All tests passed!
Computation finished at Sat Mar  2 10:36:27 2024
elapsed time: 0.00234773

Godbolt link is here.

All suggestions are welcome.

The summary information:

Which question it is a follow-up to?

A recursive_transform_reduce Function for Various Type Arbitrary Nested Iterable Implementation in C++ and

recursive_invocable and recursive_project_invocable Concept Implementation in C++
What changes has been made in the code since last question?

I am trying to implement another version recursive_transform_reduce function which takes unwrap_level as an input in this post.
Why a new review is being asked for?

Please review the implementation of recursive_transform_reduce template function and its tests.

G. Sliepen · Accepted Answer · 2024-03-02 19:28:14Z

Incorrect handling of the `init` parameter

Given this piece of code:

std::vector<int> foo = {2, 3, 4, 5};
std::cout << recursive_transform_reduce<1>(foo, 1) << '\n';

I expect the output to be equal to 1 + 2 + 3 + 4 + 5, or 15. However, this will print 19, because you apply the value of init for every element you visit. The first thing to fix is the non-recursive case, it should simply be:

if constexpr (unwrap_level > 0) {
    …
}
else
{
    return std::invoke(unary_op, input);
}

This will then result in the correct output for the example I gave. But it still results in the wrong output for more nested containers.

Note that your test cases don't catch this because you yourself thought the wrong behavior was the correct one. One way that could maybe have been avoided is if you had added a test that compares the output of recursive_transform_reduce<1>() with the output of std::transform_reduce() on the same container.

Stack Exchange Network

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

1 Answer 1

Incorrect handling of the `init` parameter

Your Answer

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

Linked

Hot Network Questions

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

1 Answer 1

Incorrect handling of the init parameter

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Incorrect handling of the `init` parameter

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