recursion – A recursive_transform template function for the multiple parameters cases in C++

This is a follow-up question for A recursive_transform template function for the binary operation cases in C++. Thanks for G. Sliepen’s answer. Based on the mentioned suggestion, I am attempting to improve the extendibility of recursive_transform template function for the multiple parameters cases.

  • recursive_invoke_result template struct and recursive_variadic_invoke_result template struct

    recursive_invoke_result struct is updated with integrating unwrap_level parameter instead of using std::invocable in order to make the logic of recursion be consistent. The recursive_invoke_result struct is focus on the result type of invoking functions with unary input and the recursive_variadic_invoke_result struct deals with the result type of invoking functions with multiple inputs.

  • recursive_transform template function for the multiple parameters cases

    The main part of this post. The multiple parameterized lambda for recursive transform is supported.

    For example, the following code can be compiled.

    std::vector<std::string> test_vector1{ "1", "4", "7" };
    std::vector<std::string> test_vector2{ "2", "5", "8" };
    std::vector<std::string> test_vector3{ "3", "6", "9" };
    std::vector<std::string> test_vector4{ "a", "b", "c" };
    auto output = recursive_transform<1>(
        ()(auto element1, auto element2, auto element3, auto element4) { return element1 + element2 + element3 + element4; },
        test_vector1, test_vector2, test_vector3, test_vector4);
    for (auto&& element : output)
    {
        std::cout << element << std::endl;
    }
    

    The output in the above code is a std::vector<std::string>. The console output:

    123a
    456b
    789c
    

The experimental implementation

  • recursive_invoke_result template struct implementation: recursive_invoke_result struct here integrating unwrap_level parameter. struct recursive_invoke_result<0, F, T> is a kind of partial template specialization which plays the role of recursion termination condition. Whether typename T is a range or not, the type just comes from std::invoke_result_t<F, T> if unwrap_level is 0.

    //  recursive_invoke_result_t implementation
    template<std::size_t, typename, typename>
    struct recursive_invoke_result { };
    
    template<typename T, typename F>
    struct recursive_invoke_result<0, F, T> { using type = std::invoke_result_t<F, T>; };
    
    template<std::size_t unwrap_level, typename F, template<typename...> typename Container, typename... Ts>
    requires (std::ranges::input_range<Container<Ts...>> &&
              requires { typename recursive_invoke_result<unwrap_level - 1, F, std::ranges::range_value_t<Container<Ts...>>>::type; })
    struct recursive_invoke_result<unwrap_level, F, Container<Ts...>>
    {
        using type = Container<typename recursive_invoke_result<unwrap_level - 1, F, std::ranges::range_value_t<Container<Ts...>>>::type>;
    };
    
    template<std::size_t unwrap_level, typename F, typename T>
    using recursive_invoke_result_t = typename recursive_invoke_result<unwrap_level, F, T>::type;
    
  • recursive_variadic_invoke_result template struct implementation: recursive_variadic_invoke_result struct deals with the result type of invoking functions with multiple inputs.

    //  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<0, F, Container1<Ts1...>, Ts...>
    {
        using type = std::invoke_result_t<F, Container1<Ts1...>, Ts...>;
    };
    
    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;
    
  • transform function for any $n$-ary function: from G. Sliepen’s answer

    template<typename OutputIt, typename NAryOperation, typename InputIt, typename... InputIts>
    OutputIt transform(OutputIt d_first, NAryOperation op, InputIt first, InputIt last, InputIts... rest) {
        while (first != last) {
            *d_first++ = op(*first++, (*rest++)...);
        }
        return d_first;
    }
    
  • The first recursive_transform template function overloading: dealing with unary input transform cases.

    //  recursive_transform implementation (the version with unwrap_level)
    template<std::size_t unwrap_level = 1, class T, class F>
    constexpr auto recursive_transform(const F& f, const T& input)
    {
        if constexpr (unwrap_level > 0)
        {
            recursive_invoke_result_t<unwrap_level, F, T> output{};
            std::ranges::transform(
                std::ranges::cbegin(input),
                std::ranges::cend(input),
                std::inserter(output, std::ranges::end(output)),
                (&f)(auto&& element) { return recursive_transform<unwrap_level - 1>(f, element); }
            );
            return output;
        }
        else
        {
            return f(input);
        }
    }
    
  • The second recursive_transform template function overloading: handling the cases with multiple input function.

    //  recursive_transform for the multiple parameters cases (the version with unwrap_level)
    template<std::size_t unwrap_level = 1, class F, class Arg1, class... Args>
    constexpr auto recursive_transform(const F& f, const Arg1& arg1, const Args&... args)
    {
        if constexpr (unwrap_level > 0)
        {
            recursive_variadic_invoke_result_t<unwrap_level, F, Arg1, Args...> output{};
            transform(
                std::inserter(output, std::ranges::end(output)),
                (&f)(auto&& element1, auto&&... elements) { return recursive_transform<unwrap_level - 1>(f, element1, elements...); },
                std::ranges::cbegin(arg1),
                std::ranges::cend(arg1),
                std::ranges::cbegin(args)...
            );
            return output;
        }
        else
        {
            return f(arg1, args...);
        }
    }
    

The testing code

In the following Godbolt link, the testing code is divide into three parts: unary_test_cases, binary_test_cases and ternary_test_cases.

A Godbolt link is here.

unary_test_cases and binary_test_cases are similar to the previous posts.

Let’s check ternary_test_cases:

void ternary_test_cases()
{
    std::cout << "*****ternary_test_cases*****" << std::endl;

    //  non-nested input test, lambda function applied on input directly
    int test_number = 3;
    std::cout << recursive_transform<0>(
        ()(auto&& element1, auto&& element2, auto&& element3) { return element1 + element2 + element3; },
        test_number, test_number, test_number) << std::endl;
    
    //  nested input test, lambda function applied on input directly
    std::vector<int> test_vector = {
        1, 2, 3
    };
    std::cout << recursive_transform<0>(()(auto element1, auto element2, auto element3)
        {
            return element1.size() + element2.size() + element3.size();
        },
        test_vector, test_vector, test_vector) << std::endl;
    
    //  std::vector<int> -> std::vector<std::string>
    auto recursive_transform_result = recursive_transform<1>(
        ()(int element1, int element2, int element3)->std::string { return std::to_string(element1 + element2 + element3); },
        test_vector, test_vector, test_vector
    );                                                                                  //  For testing
    std::cout << "std::vector<int> -> std::vector<std::string>: " +
        recursive_transform_result.at(1) << std::endl;                                  //  recursive_transform_result.at(0) is a std::string
    
    //  std::vector<string> -> std::vector<int>
    std::cout << "std::vector<string> -> std::vector<int>: "
              << recursive_transform<1>(
            ()(std::string element1, std::string element2, std::string element3) 
                  { return std::atoi((element1 + element2 + element3).c_str()); },
            recursive_transform_result, recursive_transform_result, recursive_transform_result).at(0) + 1 << std::endl;                         //  std::string element to int
    
    //  std::vector<std::vector<int>> -> std::vector<std::vector<std::string>>
    std::vector<decltype(test_vector)> test_vector2 = {
        test_vector, test_vector, test_vector
    };

    auto recursive_transform_result2 = recursive_transform<2>(
        ()(int element1, int element2, int element3)
        { return std::to_string(element1) + std::to_string(element2) + std::to_string(element3); },
        test_vector2, test_vector2, test_vector2
    );                                                                                  //  For testing
    std::cout << "string: " + recursive_transform_result2.at(0).at(0) << std::endl;     // recursive_transform_result.at(0).at(0) is also a std::string
    
    //  std::deque<int> -> std::deque<std::string>
    std::deque<int> test_deque;
    test_deque.push_back(1);
    test_deque.push_back(1);
    test_deque.push_back(1);

    auto recursive_transform_result3 = recursive_transform<1>(
        ()(int element1, int element2, int element3)
        { return std::to_string(element1) + std::to_string(element2) + std::to_string(element3); },
        test_deque, test_deque, test_deque);                            //  For testing

    std::cout << "string: " + recursive_transform_result3.at(0) << std::endl;
    
    //  std::deque<std::deque<int>> -> std::deque<std::deque<std::string>>
    std::deque<decltype(test_deque)> test_deque2;
    test_deque2.push_back(test_deque);
    test_deque2.push_back(test_deque);
    test_deque2.push_back(test_deque);

    auto recursive_transform_result4 = recursive_transform<2>(
        ()(int element1, int element2, int element3)
        { return std::to_string(element1) + std::to_string(element2) + std::to_string(element3); },
        test_deque2, test_deque2, test_deque2);                         //  For testing

    std::cout << "string: " + recursive_transform_result4.at(0).at(0) << std::endl;
    
    //  std::list<int> -> std::list<std::string>
    std::list<int> test_list = { 1, 2, 3, 4 };
    auto recursive_transform_result5 = recursive_transform<1>(
        ()(int element1, int element2, int element3)
        { return std::to_string(element1) + std::to_string(element2) + std::to_string(element3); },
        test_list, test_list, test_list);                               //  For testing
    std::cout << "string: " + recursive_transform_result5.front() << std::endl;


    //  std::list<std::list<int>> -> std::list<std::list<std::string>>
    std::list<std::list<int>> test_list2 = { test_list, test_list, test_list, test_list };
    auto recursive_transform_result6 = recursive_transform<2>(
        ()(int element1, int element2, int element3)
        { return std::to_string(element1) + std::to_string(element2) + std::to_string(element3); },
        test_list2, test_list2, test_list2);                            //  For testing
    std::cout << "string: " + recursive_transform_result6.front().front() << std::endl;
    return;
}

The output of the testing code above:

*****ternary_test_cases*****
9
9
std::vector<int> -> std::vector<std::string>: 6
std::vector<string> -> std::vector<int>: 334
string: 111
string: 111
string: 111
string: 111
string: 111

Other details

The different container types can be used simultaneously as the parameters of recursive_transform, such as the following example.

std::list<std::string> data1{ "1", "4", "7" };
std::vector<std::string> data2{ "2", "5", "8" };
std::list<std::string> data3{ "3", "6", "9" };
std::list<std::string> data4{ "a", "b", "c" };
auto output = recursive_transform<1>(
    ()(auto element1, auto element2, auto element3, auto element4) { return element1 + element2 + element3 + element4; },
    data1, data2, data3, data4);
std::cout << typeid(output).name() << std::endl;
for (auto&& element : output)
{
    std::cout << element << std::endl;
}

However, the container type of the output (in the case of output is ranges) follows the first input range parameter. Therefore, the type of the container of output is std::list<>.

The output of the testing code above (from clang):

NSt7__cxx114listINS_12basic_stringIcSt11char_traitsIcESaIcEEESaIS5_EEE
123a
456b
789c

All suggestions are welcome.

The summary information:

  • Which question it is a follow-up to?

    A recursive_transform template function for the binary operation cases in C++

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

    I am attempting to improve the extendibility of recursive_transform template function for the multiple parameters cases in this post.

  • Why a new review is being asked for?

    If there is any possible improvement, please let me know.