A recursive_foreach_all Template Function Implementation in C++

Question

This is a follow-up question for A recursive_fold_left_all Template Function Implementation in C++. As mentioned in G. Sliepen's answer, I am trying to implement recursive_foreach_all template function in this post.

The experimental implementation

recursive_foreach_all Template Function:

/*  recursive_foreach_all template function performs specific function on input container exhaustively
*/
template<class T, class Proj = std::identity, class F>
constexpr auto recursive_foreach_all(T& value, F f, Proj proj = {})
{
    return std::invoke(f, std::invoke(proj, value));
}

template<std::ranges::input_range T, class Proj = std::identity, class F>
constexpr auto recursive_foreach_all(T& inputRange, F f, Proj proj = {})
{
    return std::ranges::for_each(inputRange, [&](auto& value) {
        return recursive_foreach_all(value, f, proj);
    });
}

Full Testing Code

The full testing code:

//  A recursive_foreach_all 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_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));
    }
}

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

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 (unwrap_level <= recursive_depth<T>()&&        //  handling incorrect unwrap levels more gracefully, https://codereview.stackexchange.com/a/283563/231235
              !std::ranges::view<T>)
    constexpr auto recursive_transform(const T& input, const F& f)
    {
        if constexpr (unwrap_level > 0)
        {
            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()
        }
    }

    //  recursive_transform implementation (the version with unwrap_level, with execution policy)
    template<std::size_t unwrap_level = 1, class ExPo, 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::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
    constexpr auto recursive_transform(ExPo execution_policy, const T& input, const F& f)
    {
        if constexpr (unwrap_level > 0)
        {
            recursive_variadic_invoke_result_t<unwrap_level, F, T> output{};
            output.resize(input.size());
            std::mutex mutex;
            std::transform(execution_policy, std::ranges::cbegin(input), std::ranges::cend(input), std::ranges::begin(output),
                [&](auto&& element)
                {
                    std::lock_guard lock(mutex);
                    return recursive_transform<unwrap_level - 1>(execution_policy, element, f);
                });
            return output;
        }
        else
        {
            return f(input);
        }
    }

    //  recursive_transform implementation (binary case, the version with unwrap_level)
    template<std::size_t unwrap_level = 1, class ExPo, std::ranges::input_range R1, std::ranges::input_range R2, std::copy_constructible F>
    constexpr auto recursive_transform(ExPo execution_policy, const R1& input1, const R2& input2, const F& f)
    {
        if constexpr (unwrap_level > 0)
        {
            recursive_variadic_invoke_result_t<unwrap_level, F, R1> output{};
            output.resize(input1.size());
            std::mutex mutex;
            std::transform(execution_policy, std::ranges::cbegin(input1), std::ranges::cend(input1), std::ranges::cbegin(input2), std::ranges::begin(output),
                [&](auto&& element1, auto&& element2)
                {
                    std::lock_guard lock(mutex);
                    return recursive_transform<unwrap_level - 1>(execution_policy, element1, element2, f);
                });
            return output;
        }
        else
        {
            return f(input1, input2);
        }
    }
}

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

/*  recursive_foreach_all template function performs specific function on input container exhaustively
*/
template<class T, class Proj = std::identity, class F>
constexpr auto recursive_foreach_all(T& value, F f, Proj proj = {})
{
    return std::invoke(f, std::invoke(proj, value));
}

template<std::ranges::input_range T, class Proj = std::identity, class F>
constexpr auto recursive_foreach_all(T& inputRange, F f, Proj proj = {})
{
    return std::ranges::for_each(inputRange, [&](auto& value) {
        return recursive_foreach_all(value, f, proj);
    });
}

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_foreach_all_test();

int main()
{
    auto start = std::chrono::system_clock::now();
    recursive_foreach_all_test();
    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 0;
}

void recursive_foreach_all_test()
{
    auto print = [](const auto& n) { std::cout << ' ' << n; };
    std::vector<std::pair<int, std::string>> pairs {{1,"one"}, {2,"two"}, {3,"three"}};
    std::vector<std::vector<std::pair<int, std::string>>> pairs_vector{pairs, pairs};

    std::cout << "project the pair::first: ";
    recursive_foreach_all(pairs_vector, print, [](const auto& p) { return p.first; });
    std::cout << "\n";

    std::cout << "project the pair::second: ";
    recursive_foreach_all(pairs_vector, print, [](const auto& p) { return p.second; });
    std::cout << "\n\n";

    std::cout << "Play with test_vectors:\n";
    auto test_vectors = n_dim_container_generator<std::vector, 4, int>(1, 3);
    recursive_foreach_all(test_vectors, [](auto& element){ ++element; return; });
    recursive_print(test_vectors);

    std::cout << "Play with test_arrays:\n";
    auto test_arrays = n_dim_array_generator<4, 3>(1);
    recursive_foreach_all(test_arrays, [](auto& element){ ++element; return; });
    recursive_print(test_arrays);
}

The output of the test code above:

project the pair::first:  1 2 3 1 2 3
project the pair::second:  one two three one two three

Play with test_vectors:
Level 0:
 Level 1:
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
 Level 1:
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
 Level 1:
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
Play with test_arrays:
Level 0:
 Level 1:
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
 Level 1:
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
 Level 1:
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
  Level 2:
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
   Level 3:
   2
   2
   2
Computation finished at Tue Aug 15 11:46:33 2023
elapsed time: 0.00124901

Godbolt link is here.

All suggestions are welcome.

The summary information:

Which question it is a follow-up to?

A recursive_fold_left_all Template Function Implementation in C++.
What changes has been made in the code since last question?

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

Please review recursive_foreach_all template function implementation and all suggestions are welcome.

JimmyHu · Accepted Answer · 2023-08-27 21:09:40Z

While this is a very reasonable looking recursive foreach function, it doesn't quite have all the same semantics as std::ranges::for_each(). In particular, the standard, non-recursive version returns the function object and an iterator. While the iterator is arguably not very useful, the function object is, at least when it is properly handled by the recursive algorithm: if you look at the example usage, you'll see that it can be used to calculate the sum of a range, with the sum being stored in the function object by value. So in order to be able to do the following:

struct Sum {
    void operator()(int n) { sum += n; }
    int sum {0};
};

auto test_vectors = n_dim_container_generator<std::vector, 4, int>(1, 3);
    recursive_foreach_all(test_vectors, [](auto& element){ ++element; return; });
auto [i, s] = recursive_foreach_all(test_vectors, Sum());
std::cout << "Sum: " << s.sum << '\n';

You have to change your recursive version a bit. In particular, you have to pass std::ranges::for_each() a fuction object that stores f, and for each call to operator() updates its copy of f:

template<std::ranges::input_range T, class Proj = std::identity, class F>
constexpr auto recursive_foreach_all(T& inputRange, F f, Proj proj = {})
{
    struct RecursiveF {
        constexpr auto
        operator()(T::reference value) {
            f = recursive_foreach_all(value, f, proj).second;
        }
        F f;
        Proj proj;
    };

    auto [i, result] = std::ranges::for_each(inputRange, RecursiveF(std::move(f), proj));
    return std::make_pair(i, std::move(result.f));
}

You would have to update the terminal case as well. You might also have to think about what to do with proj: should it be moved in and out of recursive calls as well? Because that too can have state, but in my code above, that state is lost when recursive calls are made. It might be better to just create one object with the state, and pass a reference to recursive calls:

namespace impl {

template<class F, class Proj>
struct recursive_for_each_state {
     F f;
     Proj proj;
};

template<class T, class State>
constexpr void recursive_foreach_all(T& value, State& state) {
    std::invoke(state.f, std::invoke(state.proj, value));
}

template<std::ranges::input_range T, class State>
constexpr void recursive_foreach_all(T& inputRange, State& state) {
    for (auto& item: inputRange)
        recursive_foreach_all(item, state);
}

}

template<class T, class Proj = std::identity, class F>
constexpr auto recursive_foreach_all(T& inputRange, F f, Proj proj = {})
{
    impl::recursive_for_each_state state(std::move(f), std::move(proj));
    impl::recursive_foreach_all(inputRange, state);
    return std::make_pair(inputRange.end(), std::move(state.f));
}

That inputRange.end() does not work for all types of inputs. You could consider just returning state.f (like std::for_each() does).

Finally, since the standard library uses for_each as the name, consider adding the extra underscore to your name as well: recursive_for_each_all().

Thank you for your answering. I am doing some experiments and I found that there is a problem that how to map the customized Sum struct to the internal struct recursive_for_each_state? Do I need to add a constructor in recursive_for_each_state struct? If there is any misunderstanding, please let me know. — JimmyHu
– JimmyHu, Commented Aug 27, 2023 at 13:20
The Sum object will be the f in recursive_for_each_state. Note that Sum has an operator()(), so std::invoke(state.f, …) will work. — G. Sliepen
– G. Sliepen, Commented Aug 27, 2023 at 18:58

Stack Exchange Network

A recursive_foreach_all Template Function Implementation in C++

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

A recursive_foreach_all Template Function Implementation in C++

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions