A recursive_fold_left_all Template Function Implementation in C++

Question

This is a follow-up question for A recursive_sum Template Function Implementation with Unwrap Level in C++. I am trying to implement a recursive version fold_left template function in this post.

The experimental implementation

recursive_fold_left_all Template Function:

/*  recursive_fold_left_all template function performs fold left operation on input container exhaustively
*/
template<typename T>
constexpr auto recursive_fold_left_all(const T& input)
{
    return input;
}

template<std::ranges::input_range T, class I,
         class F>
constexpr auto recursive_fold_left_all(const T inputRange, I init, F f)
{
    return std::ranges::fold_left(inputRange, init, f);
}

template<std::ranges::input_range T, class I,
         class F>
requires(std::ranges::input_range<std::ranges::range_value_t<T>>)
constexpr auto recursive_fold_left_all(const T inputRange, I init, F f)
{

    return std::invoke(f, init, recursive_fold_left_all(
        UL::recursive_transform<recursive_depth<T>() - 1>(
            inputRange,
            [&](auto&& element){ return recursive_fold_left_all(element, I{}, f); }),
            I{}, f
        ));
}

Full Testing Code

The full testing code:

//  A recursive_fold_left_all Template Function Implementation 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 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_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_fold_left_all template function performs fold left operation on input container exhaustively
*/
template<typename T>
constexpr auto recursive_fold_left_all(const T& input)
{
    return input;
}

template<std::ranges::input_range T, class I,
         class F>
constexpr auto recursive_fold_left_all(const T inputRange, I init, F f)
{
    return std::ranges::fold_left(inputRange, init, f);
}

template<std::ranges::input_range T, class I,
         class F>
requires(std::ranges::input_range<std::ranges::range_value_t<T>>)
constexpr auto recursive_fold_left_all(const T inputRange, I init, F f)
{
    
    return std::invoke(f, init, recursive_fold_left_all(
        UL::recursive_transform<recursive_depth<T>() - 1>(
            inputRange,
            [&](auto&& element){ return recursive_fold_left_all(element, I{}, f); }),
            I{}, f
        ));
}

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

void recursive_fold_left_all_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_fold_left_all function test with vectors / std::plus<>(): \n";
    auto recursive_fold_left_all_result1 = recursive_fold_left_all(test_vectors, static_cast<int>(1), std::plus<>());
    std::cout << recursive_fold_left_all_result1 << "\n\n";

    std::cout << "recursive_fold_left_all function test with vectors / std::multiplies<>(): \n";
    auto recursive_fold_left_all_result2 = recursive_fold_left_all(test_vectors, static_cast<int>(2), std::multiplies<>());
    std::cout << recursive_fold_left_all_result2 << "\n\n";

    //  From: https://en.cppreference.com/w/cpp/algorithm/ranges/fold_left
    std::vector<std::pair<char, float>> data {{'A', 2.f}, {'B', 3.f}, {'C', 3.5f}};
    auto recursive_fold_left_all_result3 = recursive_fold_left_all
    (
        data | std::ranges::views::values, 2.0f, std::multiplies<>()
    );
    std::cout << "recursive_fold_left_all_result3: " << recursive_fold_left_all_result3 << '\n';

    std::array<int, 8> arr {1, 2, 3, 4, 5, 6, 7, 8};
    // use a program defined function object (lambda-expression):
    auto recursive_fold_left_all_result4 = recursive_fold_left_all
    (
        arr, "A", [](std::string s, int x) { return s + ':' + std::to_string(x); }
    );
    std::cout << "recursive_fold_left_all_result4: " << recursive_fold_left_all_result4 << '\n';

    return;
}

int main()
{
    recursive_fold_left_all_tests();

    return 0;
}

The output of the test code above:

Play with test_vectors:

recursive_fold_left_all function test with vectors / std::plus<>(): 
82

recursive_fold_left_all function test with vectors / std::multiplies<>(): 
0

recursive_fold_left_all_result3: 42
recursive_fold_left_all_result4: A:1:2:3:4:5:6:7:8

Godbolt link is here.

All suggestions are welcome.

The summary information:

Which question it is a follow-up to?

A recursive_sum Template Function Implementation with Unwrap Level in C++.
What changes has been made in the code since last question?

I am trying to implement a recursive version fold_left template function in this post.
Why a new review is being asked for?

Please review recursive_fold_left_all and all suggestions are welcome.

JimmyHu · Accepted Answer · 2023-08-11 22:25:35Z

This makes lots of unnecessary copies. It already starts with the function declaration:

constexpr auto recursive_fold_left_all(const T inputRange, I init, F f)

Because inputRange is passed by value, a copy is made before the function even starts. And since this is called recursively, copies are made at every recursion level. But it gets worse:

UL::recursive_transform<recursive_depth<T>() - 1>(…)

Your recursive_transform() function produces a new container as its output. This is a temporary copy that will hold values until a regular std::ranges::fold_left() will fold the items in it.

I see how you got here: you wanted to do the folding itself recursively. However, consider instead just recursively visiting each value in the input, and then applying the fold operation to each value. If you have a recursive_foreach(), then you can just write:

template<class T, class I, class F>
constexpr auto recursive_fold_left_all(const T& inputRange, I init, F f)
{
    recursive_foreach(inputRange, [&](auto& value) {
        init = std::invoke(f, init, value);
    });

    return init;
}

However, you can make a recursive version from scratch like so:

template<class T, class I, class F>
constexpr auto recursive_fold_left_all(const T& value, I init, F f) {
    return std::invoke(f, init, value);
}

template<std::ranges::input_range T, class I, class F>
constexpr auto recursive_fold_left_all(const T& inputRange, I init, F f)
{
    return std::ranges::fold_left(range, init, [&](auto& value) {
        return recursive_fold_left_all(value, I{}, f);
    });
}

Also note that in general, you should only need two overloads for recursive functions: the generic recursive case, and the terminal case. You should not need a third one.

Stack Exchange Network

A recursive_fold_left_all Template Function Implementation in C++

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

A recursive_fold_left_all Template Function Implementation in C++

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions