A recursive_transform_view Template Function Implementation

Question

This is a follow-up question for A recursive_transform Template Function with Unwrap Level for std::array Implementation in C++. Considering the suggestion mentioned in Davislor's answer, I am trying to implement recursive_transform_view template function and comparing it with recursive_transform template function. The proposed experimental implementation is tested with int (non-nested input test), non-nested std::array, std::vector container. Please noticed that without specifying unwrap_level, generic lambda (auto&& or auto) cannot be used.

The experimental implementation

The experimental implementations of recursive_transform_view template function is as follows.

• recursive_transform_view function implementation:

  /* Base case of recursive_transform_view template function
   https://codereview.stackexchange.com/a/283581/231235
  */
  template< typename T,
   std::invocable<T> F >
  requires (std::copy_constructible<F>)
  constexpr auto recursive_transform_view( const T& input, const F& f )
  {
   return std::invoke( f, input );
  }
  /* The recursive case of recursive_transform_view template function
   https://codereview.stackexchange.com/a/283581/231235
  */
  template< template<typename...> typename Container,
   std::copy_constructible F,
   typename... Ts >
  requires (std::ranges::input_range<Container<Ts...>>&&
   std::ranges::view<Container<Ts...>>)
  constexpr auto recursive_transform_view(const Container<Ts...>& input, const F& f)
  {
   const auto view = std::ranges::transform_view(
   std::ranges::subrange( std::begin(input), std::end(input) ),
   [f](const auto& x) constexpr { return recursive_transform_view( x, f ); } );
   recursive_invoke_result_t<F, Container<Ts...>> output( view.begin(), view.end() );
   // One last sanity check.
   if constexpr( is_sized<Container<Ts...>> && is_sized<recursive_invoke_result_t<F, Container<Ts...>>> )
   {
   assert( output.size() == input.size() );
   }
   return output;
  }
  /* The recursive case of recursive_transform_view 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_view(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::begin(output),
   [&f](auto&& element){ return recursive_transform_view(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;
  }
  

Full Testing Code

The full testing code:

// A recursive_transform_view Template Function Implementation
#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);
};
// 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::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::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::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::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;
// clone_empty_container template function implementation
template<class T, class F>
constexpr auto clone_empty_container(const T& input, const F& f)
{
 recursive_invoke_result_t<F, T> output;
 return output;
}
// recursive_transform template function implementation (the version with unwrap_level)
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
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)>) // reserve space
 {
 output.reserve(input.size());
 }
 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()
 }
}
/* 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_invoke_result_t<F, T>, N> output;
 std::ranges::transform( // Use std::ranges::transform() for std::arrays as well
 input,
 std::begin(output),
 [&f](auto&& element){ return recursive_transform<unwrap_level - 1>(element, f); }
 );
 return output;
}
/* Base case of recursive_transform_view template function
 https://codereview.stackexchange.com/a/283581/231235
 */
template< typename T,
 std::invocable<T> F >
requires (std::copy_constructible<F>)
constexpr auto recursive_transform_view( const T& input, const F& f )
{
 return std::invoke( f, input );
}
/* The recursive case of recursive_transform_view template function
 https://codereview.stackexchange.com/a/283581/231235
 */
template< template<typename...> typename Container,
 std::copy_constructible F,
 typename... Ts >
requires (std::ranges::input_range<Container<Ts...>>&&
 std::ranges::view<Container<Ts...>>)
constexpr auto recursive_transform_view(const Container<Ts...>& input, const F& f)
{
 const auto view = std::ranges::transform_view(
 std::ranges::subrange( std::begin(input), std::end(input) ),
 [f](const auto& x) constexpr { return recursive_transform_view( x, f ); } );
 recursive_invoke_result_t<F, Container<Ts...>> output( view.begin(), view.end() );
 // One last sanity check.
 if constexpr( is_sized<Container<Ts...>> && is_sized<recursive_invoke_result_t<F, Container<Ts...>>> )
 {
 assert( output.size() == input.size() );
 }
 return output;
}
/* The recursive case of recursive_transform_view 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_view(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::begin(output),
 [&f](auto&& element){ return recursive_transform_view(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;
}
void tests()
{
 // non-nested input test, lambda function applied on input directly
 std::cout << "non-nested input test, lambda function applied on input directly:\n";
 int test_number = 3;
 auto recursive_transform_output1 = recursive_transform<0>(test_number, [](auto&& element) { return element + 1; });
 std::cout << "recursive_transform function output: \n"
 << recursive_transform_output1 << '\n';
 auto recursive_transform_view_output1 = recursive_transform_view(test_number, [](auto&& element) { return element + 1; });
 std::cout << "recursive_transform_view function output: \n"
 << recursive_transform_view_output1 << "\n\n";
 assert(recursive_transform_output1 == recursive_transform_view_output1);
 // test with non-nested std::array container
 std::cout << "test with non-nested std::array container:\n";
 static constexpr std::size_t D = 3;
 auto test_array = std::array< double, D >{1, 2, 3};
 auto recursive_transform_output2 = recursive_transform<1>(test_array, [](auto&& element) { return element + 1; });
 std::cout << "recursive_transform function output: \n";
 for(int i = 0; i < recursive_transform_output2.size(); ++i)
 {
 std::cout << recursive_transform_output2[i] << " ";
 }
 std::cout << '\n';
 // Without specifying unwrap_level, generic lambda (auto&& or auto) cannot be used.
 // error: invalid operands to binary expression ('std::array<double, 3>' and 'int')
 //auto recursive_transform_view_output2 = recursive_transform_view(test_array, [](auto&& element) { return element + 1; });
 auto recursive_transform_view_output2 = recursive_transform_view(test_array, [](int&& element) { return element + 1; });
 std::cout << "recursive_transform_view function output: \n";
 for(int i = 0; i < recursive_transform_view_output2.size(); ++i)
 {
 std::cout << recursive_transform_view_output2[i] << " ";
 }
 std::cout << "\n\n";
 // test with nested std::arrays
 auto test_nested_array = std::array< decltype(test_array), D >{test_array, test_array, test_array};
 //std::cout << "test with nested std::arrays: \n"
 // << recursive_transform<2>(test_nested_array, [](auto&& element) { return element + 1; })[0][0] << '\n';
 std::cout << "std::vector input test, lambda function applied on input directly:\n";
 std::vector<int> test_vector1 = {
 1, 2, 3
 };
 auto recursive_transform_output3 = recursive_transform<0>(test_vector1, [](auto element)
 {
 element.push_back(4);
 element.push_back(5);
 return element;
 });
 std::cout << "recursive_transform function output: \n";
 for(int i = 0; i < recursive_transform_output3.size(); ++i)
 {
 std::cout << recursive_transform_output3[i] << " ";
 }
 std::cout << '\n';
 std::vector<int> test_vector2 = {
 1, 2, 3
 };
 // Error from Clang:
 // error: no matching function for call to '__begin'
 /*
 auto recursive_transform_view_output3 = recursive_transform_view(test_vector2, [](int element)
 {
 return element;
 });
 std::cout << "recursive_transform_view function output: \n";
 for(int i = 0; i < recursive_transform_view_output3.size(); ++i)
 {
 std::cout << recursive_transform_view_output3[i] << " ";
 }
 */
 std::cout << "\n\n";
 std::vector<int> test_vector = {
 1, 2, 3
 };
 auto test_priority_queue = 
 std::priority_queue<int>(std::ranges::begin(test_vector), std::ranges::end(test_vector));
 std::cout << "test with std::priority_queue container: \n"
 << recursive_transform<0>(test_priority_queue, [](auto element)
 {
 element.push(4);
 element.push(5);
 element.push(6);
 return element;
 }).top() << '\n';
 // Convert each int element in std::vector to std::string
 // std::vector<int> -> std::vector<std::string>
 auto recursive_transform_result = recursive_transform<1>(
 test_vector,
 [](int x)->std::string { return std::to_string(x); }
 ); // For testing
 std::cout << "std::vector<int> -> std::vector<std::string>: " +
 recursive_transform_result.at(0) << '\n'; // 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>(
 recursive_transform_result,
 [](std::string x) { return std::atoi(x.c_str()); }).at(0) + 1 << '\n'; // std::string element to int
 // std::vector<std::vector<int>> -> std::vector<std::vector<std::string>>
 std::vector<decltype(test_vector)> test_nested_vector = {
 test_vector, test_vector, test_vector
 };
 auto recursive_transform_result2 = recursive_transform<2>(
 test_nested_vector,
 [](int x)->std::string { return std::to_string(x); }
 ); // For testing
 std::cout << "string: " + recursive_transform_result2.at(0).at(0) << '\n'; // 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>(
 test_deque,
 [](int x)->std::string { return std::to_string(x); }); // For testing
 std::cout << "string: " + recursive_transform_result3.at(0) << '\n';
 // 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>(
 test_deque2,
 [](int x)->std::string { return std::to_string(x); }); // For testing
 std::cout << "string: " + recursive_transform_result4.at(0).at(0) << '\n';
 // std::list<int> -> std::list<std::string>
 std::list<int> test_list = { 1, 2, 3, 4 };
 auto recursive_transform_result5 = recursive_transform<1>(
 test_list,
 [](int x)->std::string { return std::to_string(x); }); // For testing
 std::cout << "string: " + recursive_transform_result5.front() << '\n';
 // 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>(
 test_list2,
 [](int x)->std::string { return std::to_string(x); }); // For testing
 std::cout << "string: " + recursive_transform_result6.front().front() << '\n';
}
int main()
{
 tests();
 return 0;
}

The output of the test code above:

non-nested input test, lambda function applied on input directly:
recursive_transform function output: 
4
recursive_transform_view function output: 
4
test with non-nested std::array container:
recursive_transform function output: 
2 3 4 
recursive_transform_view function output: 
2 3 4 
std::vector input test, lambda function applied on input directly:
recursive_transform function output: 
1 2 3 4 5 
test with std::priority_queue container: 
6
std::vector<int> -> std::vector<std::string>: 1
std::vector<string> -> std::vector<int>: 2
string: 1
string: 1
string: 1
string: 1
string: 1

Godbolt link

All suggestions are welcome.

The summary information:

• Which question it is a follow-up to?

  A recursive_transform Template Function with Unwrap Level for std::array Implementation in C++

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

  I am trying to implement recursive_transform_view template function and comparing it with recursive_transform template function.

• Why a new review is being asked for?

  Please review the experimental implementation of recursive_transform_view template function. If there is any misunderstanding, please let me know.

• Davislor: Dont have a chance to write a full review right now, but one observation. I don’t think the std::transform with std::begin(output) as the destination is going to work for containers where you need to insert. When I tried this, I generated a std::ranges::transform_view and constructed output from its begin and end iterators.
• Davislor: Some of the concepts here are not being applied correctly. Why does F need to be copy constructible? It’s only captured and passed by reference. But it should be invocable. And you should call .size() on a container only if it is_sized, within an if constexpr block, to avoid a compile error if the type does not have that member function.
• JimmyHu: @Davislor Thank you for the comments. About why does F need to be copy constructible, please check en.cppreference.com/w/cpp/ranges/transform_view . std::copy_constructible is used in transform_view.
• Davislor: Ah, I see. [[range.transform] requires F to be copy-constructable because one of the constructors of std::transform_view<V, F> takes a copy of F. And you do actually declare std::invocable in the base case, so it won’t match unless that does. Looks okay.

Answer 1

The name is wrong

Calling this recursive_transform_view() gives the impression that this return a std::ranges::view. However, semantically your function does the same as recursive_transform() from your earlier questions, and this is just an improved version based on Davislor's suggestions. So it should still be named recursive_transform().

If you want to be able to compare a new version of recursive_transform() to an old one in the same program, then consider wrapping them each in their own namespace.

Of course, it might be interesting in itself to create a recursive_transform_view() that does return a view...

Match the requirements of std::ranges::transform_view()

If your code is going to call std::ranges::transform_view(), make sure you add the same requires clauses to your own function. See the code at the end of my answer for an example.

However, you must take into account the recursion. Before Davislor pointed out my mistake, I had included this in the requires clause as well:

&& std::regular_invocable<F&, std::ranges::range_reference_t<Container>>

However, that is wrong, since the function F only needs to work at the bottom level of the recursion. You could make the requires clause recurse:

&& std::regular_invocable<F&, std::ranges::range_reference_t<
 recursive_invoke_result_t<F, Container>
>>

Although I don't think that will make the error message you would get from passing an incorrect F any better.

You don't need Ts... in the generic recursive case

In the generic recursive case, your have a template template parameter template<typename...> typename Container and a parameter pack typename... Ts. However, you don't need to know anything about the structure of Container in this case, you only need to pass it on to recursive_invoke_result_t<>. So you can just take Container as a regular template parameter:

template< std::ranges::input_range Container,
 std::copy_constructible F >
requires (std::ranges::view<Container> &&
 std::is_object_v<F>)
constexpr auto recursive_transform_view(const Container& input, const F& f)
{
 ...
 recursive_invoke_result_t<F, Container> output( view.begin(), view.end() );
 ...
}

• Davislor: When I did it, I called it traverse, like in Haskell.
• Davislor: In the generic recursive case, at least in the implementation this is based on, you do need to know the first parameter of Container<T, Ts...>, because the output is a Container<U> that might have a different element type. My implementation didn’t handle all cases, but for example, traverse( double[3], double(*)(double) ) actually returned a std::array<double, 3>, because you can’t return an array in C or C++. So, traverse(std::vector<double[3]>, double(*)(double) returned a std::vector<std::array<double, 3>> instead. This happened to work with the default allocatpr.
• Davislor: Also, F isn’t necessarily invocable on a top-level range reference to the container. The contents might be another layer of containers. Checking invocability on the base case and not the recursive case, like the answer does already, is correct.
• G. Sliepen: @Davislor Oops, you're right. Well, you could make the top-level requires clause itself recurse down to the base level as well... but I have no idea what this will do to the error messages. I'll have to check that out. But about the generic recurisve case, you do not need to know anything, you just need to pass it to recursive_invoke_result_t, and the latter one needs the template template parameters to construct the right output type. And you also need template template parameters in the specialization for std::arrays.
• Davislor: Thinking about it some more, I realized that, in fact, the recursive cases all need to check that their transformation function is not invocable on their first argument. Otherwise, if you pass a function whose domain is a container? It will match the recursive overload instead of the base case (or both ambiguously), try to recurse further, and break.

Answer 2

Please Post a More Minimal Example

There’s a lot here that was copied from other answers, or implements a completely different algorithm than the one you’re asking for feedback on. At least split up the two different implementations and the test harness into modules. And please point us where you want to look.

For example, I think you want feedback on recursive_transform(const T& input, const F& f), but it’s buried deep in your post.

So, About that recursive_transform

I mean this overload:

// recursive_transform template function implementation (the version with unwrap_level)
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
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)>) // reserve space
 {
 output.reserve(input.size());
 }
 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()
 }
}

Okay, in one of my answers, I left a silly comment like use std::ranges::transform_view on the same line where I called std::ranges::transform_view. I originally wrote that as a reminder to myself to go back and refactor, and meant to remove it when I was done. Please don’t imitate my mistake and litter your code with more comments like it:

return std::invoke(f, input); // use std::invoke()

This is far too obvious to need a comment. You might want a comment to explain why you used std::invoke

return std::invoke(f, input); // In templates, std::invoke(f, x) is more general and less ambiguous than f(x).

Or maybe how you know it works. Or maybe even a warning:

return std::invoke(f, input); // TODO: check std::regular_invocable<F, T>

As for the implementation itself, it has similar problems to other uses of std::inserter in your previous questions. The current implementation of std::inserter is inefficient, and it also only works on a container that supports push_back. You’ve heard me say that before.

You’re also trying to use it on a function that returns a different type than its argument, which I wasn’t expecting to need to support, but also didn’t check for. Let that be a lesson to you as well! I’ll come back to that.

You Found a Library Bug

 // Error from Clang:
 // error: no matching function for call to '__begin'
 /*
 auto recursive_transform_view_output3 = recursive_transform_view(test_vector2, [](int element)
 {
 return element;
 });
 std::cout << "recursive_transform_view function output: \n";
 for(int i = 0; i < recursive_transform_view_output3.size(); ++i)
 {
 std::cout << recursive_transform_view_output3[i] << " ";
 }
 */

This is a bug with (I believe) the libstdc++ implementation of std::ranges. If you upgrade from Clang 15.0.0 to the latest trunk branch, it will fix this and give you another bug with your partial template specializations.

Based on your idea to restrict the containers with the std::range::input_range concept, I realized that constructing a subrange object is not needed.

Naming Conventions

This isn’t a view; it’s an implementation of recursive_transform implemented using a call to std::ranges::transform_view. I called my own version traverse, because I first learned the pattern in Haskell.

I originally wrote the concept definitions with names like is_sized, but the convention in C++ is not to name concepts with is_. So, std::same_as is a concept, and std::is_same is a function that checks for something similar.

Update: What if Your Funtion Takes a Container?

This was a bug you copied from me: previously, if you passed in a transformation function that takes a container, such as, it would fail:

static const std::vector<std::array<int, 2>> test_data4 =
 { {1, 0}, {0, 1} };
const auto test_result4 = traverse( test_data4,
 [](const std::array<int, 2>& v)constexpr{ return v[0]+v[1]; } 
 );

Since this would incorrectly match the overload for traverse( const Container<T, N>&, const F& ). The fix here is to add a new requirement to all the recursive overloads, disabling them if they also match the base case (that is, if the container they match is invokable by F). I’ve edited this in below.

Update: the Helper Template

You currently are using the type recursive_invoke_result_t with the type constraint std::ranges::input_range to deduce the return type of the invocations. That’s better than what I did in several ways (using the concept from the standard library is better than reinventing the wheel like me), but it does have one disadvantage.

If you ever need to support a container with an irregular return type under the transformation—such as transforming a C-style array into a std::array because a function cannot return the former, or transforming a std::basic_string<T> into a std::vector<U> when U is not a character type—you would also need to overload your helper template, and always keep it consistent with the function templates elsewhere. If you do the type deduction within the functions themselves, the necessary code is all in one place.

You Still Don’t Need a User-Supplied Nesting Level

You say, "Please noticed that without specifying unwrap_level, generic lambda (auto&& or auto) cannot be used."

So write [](const double x) or [](const T& x) instead of [](auto&& x). Or a named helper function like container_sum<double>, which will be more readable anyway. Or you can even write a helper function with constraints on its template parameters, like the complicated container_sum I wrote here (or an even more complicated one that also works on std::valarray), so you don’t even have to write <double>—although that isn’t necessary.

You Want Something More Flexible

What I wrote assumed that the transformation function had the same type as its input. You’re converting containers of int to containers of std::string. However, std::vector<int> expands to std::vector<int, std::allocator<int>. This gets broken down into Container = std::vector, T = int, and Ts... = std::allocator<int>. You cannot replace only T! That gets you a std::vector<std::string, std::allocator<int>>, which won’t work!

If the default allocators and comparators are always good enough, you can just specialize your output type as Container<T> and let it fill in the remaining fields with the default values. Otherwise, standard library containers might take a size_t size parameter, an allocator, a comparator, a key type, and a hash function.

How You Could Fix This

Here’s a stripped-down version of the code for a std::array-like container, which uses the std::rangs::transform_view implementation. Since you put the effort into getting the template requirements right, so will I:

#include <algorithm> // move
#include <cassert>
#include <concepts>
#include <cstddef> // size_t
#include <functional> // invoke
#include <ranges> // transform_view
#include <utility> // declval
/* A container or range constructible from its own iterator and sentinel
 * types.
 */
template<class T>
concept constructible_from_iterators = requires(T x) {
 std::ranges::input_range<T>;
 std::constructible_from< decltype(std::ranges::begin(x)),
 decltype(std::ranges::end(x)) >;
};
/* Base case for traversal: a single input to the transformation function.
 * If called by another overload, which passed f to
 * std::ranges::transform_view, f must be regular-invocable on T.
 */
template< typename T,
 typename F >
 requires std::regular_invocable<F, T>
constexpr auto traverse( const T& input, const F& f )
{
 return std::invoke( f, input );
}
/* This overload was needed to support traversing std::array. It enforces
 * the C++20 requirements to pass an F to std::ranges::transform_view,
 * except std::regular_invocable, which is checked in the base case. Will
 * attempt to either construct it from the view or move the elements of the
 * view over.
 */
template< template<class T, std::size_t> class Container,
 typename F,
 typename T,
 std::size_t N >
 requires (!std::regular_invocable<F, Container<T, N>>) &&
 std::ranges::input_range<Container<T, N>> &&
 std::copy_constructible<F> &&
 std::is_object_v<F> &&
 ( constructible_from_iterators<Container<T, N>> ||
 std::default_initializable<Container<T, N>> )
constexpr auto traverse( const Container<T, N>& input, const F& f )
{
 using U = decltype(traverse(std::declval<T>(), f));
 using OutputT = Container<U, N>;
 static_assert( std::ranges::input_range<OutputT>,
 "Could not deduce the return type." );
 const auto results = std::ranges::transform_view(
 input,
 [&f](const T& x)constexpr{ return traverse(x, f); } );
 if constexpr (std::constructible_from<OutputT,
 decltype(results.begin()),
 decltype(results.end())>) {
 return OutputT(results.begin(), results.end());
 } else {
 static_assert( std::default_initializable<OutputT>,
 "Must be able to create a return object." );
 static_assert( std::ranges::output_range<OutputT, U>,
 "The return object must be writable." );
 OutputT output;
 // Sanity check that the container is enough like a std::array:
 assert(std::ranges::size(output) == std::ranges::size(input));
/* The results of the transform_view should be movable, since passing an
 * identity funtion that returns move references to this algorithm would be
 * absurd.
 */
 std::move( results.begin(), results.end(), std::ranges::begin(output) );
 return output;
 }
}

The test case:

static constexpr std::array<unsigned, 5> test_data1 = { 1, 2, 3, 4, 5 };
static constexpr auto test_result1 = traverse( test_data1,
 [](const unsigned& x)constexpr{ return static_cast<double>(x); }
 );

compiles on Godbolt (also showing which version of the compiler you need to use) to the constants

main::test_data1:
 .long 1 # 0x1
 .long 2 # 0x2
 .long 3 # 0x3
 .long 4 # 0x4
 .long 5 # 0x5
main::test_result1:
 .quad 0x3ff0000000000000 # double 1
 .quad 0x4000000000000000 # double 2
 .quad 0x4008000000000000 # double 3
 .quad 0x4010000000000000 # double 4
 .quad 0x4014000000000000 # double 5

But that’s the simplest case, and was already working.

Supporting Other Containers

Standard library containers fall into several different paradigms, but the one that you’re going for is, <T, Allocator<T>>. That is, if you transform a std::vector<int, std::allocator<int>> with a function that maps int to std::string, you want the type of the output to be std::vector<std::string, std::allocator<std::string>>. If you pass std::allocator<int> to the std::string container, it will fail!

Here, then, is a version that accepts any allocator—so long as it takes one template parameter, the element type of the container.

/* Matches the interface of an allocator, such as std::allocate<T>.
 */
template<class A, typename T>
concept allocator = requires(A a, std::size_t n) {
 {a.allocate(n)} -> std::same_as<T*>;
 {a.deallocate(a.allocate(n), n)} -> std::same_as<void>;
};
/* An overload for containers similar to std::vector<T, Alloc>. Also emfprces
 * the requirements of std::tanges::transform_view. Assumes that the allocator
 * is a template class with T as its only parameter.
 */
template< template<class T, class A> class Container,
 typename F,
 typename T,
 template<typename> class A
 >
 requires (!std::regular_invocable<F, Container<T, A<T>>>) &&
 std::ranges::input_range<Container< T, A<T> >> &&
 constructible_from_iterators<Container< T, A<T> >> &&
 std::copy_constructible<F> &&
 std::is_object_v<F> &&
 allocator<A<T>, T>
constexpr auto traverse( const Container<T, A<T>>& input, const F& f )
{
 using U = decltype(traverse(std::declval<T>(), f));
 using OutputT = Container<U, A<U>>;
 static_assert( std::ranges::input_range<OutputT>,
 "Could not deduce the return type." );
 static_assert(allocator<A<U>, U>, "Could not deduce allocator type.");
 const auto results = std::ranges::transform_view(
 input,
 [&f](const T& x)constexpr{ return traverse(x, f); } );
 return OutputT(results.begin(), results.end());
}

There’s a lot of code reuse here. What about container types such as std::set that take both a Compare and an Allocator parameter? The logic is identical but for the template parameters:

/* Matches the interface of a comparator for T, such as std::less<T>
 */
template<class C, typename T>
concept comparator = requires(T x, C c) {
 {c(x,x)} -> std::convertible_to<bool>;
};
/* An overload similar to the above, intended for containers such as std::set.
 * which take both a comparator and an allocator. Assumes that both are
 * classes with a single template parameter, the Key.
 */
template< template<class K, class C, class A> class Container,
 typename F,
 typename K,
 template<typename> class C,
 template<typename> class A
 >
 requires (!std::regular_invocable<F, Container<K, C<K>, A<K>>>) &&
 std::ranges::input_range<Container< K, C<K>, A<K> >> &&
 constructible_from_iterators<Container<K, C<K>, A<K>>> &&
 std::copy_constructible<F> &&
 std::is_object_v<F> &&
 allocator<A<K>, K> &&
 comparator<C<K>, K>
constexpr auto traverse( const Container<K, C<K>, A<K>>& input, const F& f )
{
 using U = decltype(traverse(std::declval<K>(), f));
 using OutputT = Container<U, C<U>, A<U>>;
 static_assert( std::ranges::input_range<OutputT>,
 "Could not deduce the return type." );
 static_assert(allocator<A<U>, U>, "Could not deduce allocator type.");
 static_assert(comparator<C<U>, U>, "Could not deduce comparator type.");
 const auto results = std::ranges::transform_view(
 input,
 [&f](const K& x)constexpr{ return traverse(x, f); } );
 return OutputT(results.begin(), results.end());
}

Putting it All Together

Library code:

#include <algorithm> // move
#include <cassert>
#include <concepts>
#include <cstddef> // size_t
#include <functional> // invoke
#include <ranges> // transform_view
#include <utility> // declval
/* A container or range constructible from its own iterator and sentinel
 * types.
 */
template<class T>
concept constructible_from_iterators = requires(T x) {
 std::ranges::input_range<T>;
 std::constructible_from< decltype(std::ranges::begin(x)),
 decltype(std::ranges::end(x)) >;
};
/* Matches the interface of an allocator, such as std::allocate<T>.
 */
template<class A, typename T>
concept allocator = requires(A a, std::size_t n) {
 {a.allocate(n)} -> std::same_as<T*>;
 {a.deallocate(a.allocate(n), n)} -> std::same_as<void>;
};
/* Matches the interface of a comparator for T, such as std::less<T>
 */
template<class C, typename T>
concept comparator = requires(T x, C c) {
 {c(x,x)} -> std::convertible_to<bool>;
};
/* Forward declarations of the recursive overloads, to allow nesting in any
 * order.
 */
template< template<class T, std::size_t> class Container,
 typename F,
 typename T,
 std::size_t N >
 requires (!std::regular_invocable<F, Container<T, N>>) &&
 std::ranges::input_range<Container<T, N>> &&
 std::copy_constructible<F> &&
 std::is_object_v<F> &&
 ( constructible_from_iterators<Container<T, N>> ||
 std::default_initializable<Container<T, N>> )
constexpr auto traverse( const Container<T, N>& input, const F& f );
template< template<class T, class A> class Container,
 typename F,
 typename T,
 template<typename> class A
 >
 requires (!std::regular_invocable<F, Container<T, A<T>>>) &&
 std::ranges::input_range<Container< T, A<T> >> &&
 constructible_from_iterators<Container< T, A<T> >> &&
 std::copy_constructible<F> &&
 std::is_object_v<F> &&
 allocator<A<T>, T>
constexpr auto traverse( const Container<T, A<T>>& input, const F& f );
template< template<class K, class C, class A> class Container,
 typename F,
 typename K,
 template<typename> class C,
 template<typename> class A
 >
 requires (!std::regular_invocable<F, Container<K, C<K>, A<K>>>) &&
 std::ranges::input_range<Container< K, C<K>, A<K> >> &&
 constructible_from_iterators<Container<K, C<K>, A<K>>> &&
 std::copy_constructible<F> &&
 std::is_object_v<F> &&
 allocator<A<K>, K> &&
 comparator<C<K>, K>
constexpr auto traverse( const Container<K, C<K>, A<K>>& input, const F& f );
/* Base case for traversal: a single input to the transformation function.
 * If called by another overload, which passed f to
 * std::ranges::transform_view, f must be regular-invocable on T.
 */
template< typename T,
 typename F >
 requires std::regular_invocable<F, T>
constexpr auto traverse( const T& input, const F& f )
{
 return std::invoke( f, input );
}
/* This overload was needed to support traversing std::array. It enforces
 * the C++20 requirements to pass an F to std::ranges::transform_view,
 * except std::regular_invocable, which is checked in the base case. Will
 * attempt to either construct it from the view or move the elements of the
 * view over.
 */
template< template<class T, std::size_t> class Container,
 typename F,
 typename T,
 std::size_t N >
 requires (!std::regular_invocable<F, Container<T, N>>) &&
 std::ranges::input_range<Container<T, N>> &&
 std::copy_constructible<F> &&
 std::is_object_v<F> &&
 ( constructible_from_iterators<Container<T, N>> ||
 std::default_initializable<Container<T, N>> )
constexpr auto traverse( const Container<T, N>& input, const F& f )
{
 using U = decltype(traverse(std::declval<T>(), f));
 using OutputT = Container<U, N>;
 static_assert( std::ranges::input_range<OutputT>,
 "Could not deduce the return type." );
 const auto results = std::ranges::transform_view(
 input,
 [&f](const T& x)constexpr{ return traverse(x, f); } );
 if constexpr (std::constructible_from<OutputT,
 decltype(results.begin()),
 decltype(results.end())>) {
 return OutputT(results.begin(), results.end());
 } else {
 static_assert( std::default_initializable<OutputT>,
 "Must be able to create a return object." );
 static_assert( std::ranges::output_range<OutputT, U>,
 "The return object must be writable." );
 OutputT output;
 // Sanity check that the container is enough like a std::array:
 assert(std::ranges::size(output) == std::ranges::size(input));
/* The results of the transform_view should be movable, since passing an
 * identity funtion that returns move references to this algorithm would be
 * absurd.
 */
 std::move( results.begin(), results.end(), std::ranges::begin(output) );
 return output;
 }
}
/* An overload for containers similar to std::vector<T, Alloc>. Also emfprces
 * the requirements of std::tanges::transform_view. Assumes that the allocator
 * is a template class with T as its only parameter.
 */
template< template<class T, class A> class Container,
 typename F,
 typename T,
 template<typename> class A
 >
 requires (!std::regular_invocable<F, Container<T, A<T>>>) &&
 std::ranges::input_range<Container< T, A<T> >> &&
 constructible_from_iterators<Container< T, A<T> >> &&
 std::copy_constructible<F> &&
 std::is_object_v<F> &&
 allocator<A<T>, T>
constexpr auto traverse( const Container<T, A<T>>& input, const F& f )
{
 using U = decltype(traverse(std::declval<T>(), f));
 using OutputT = Container<U, A<U>>;
 static_assert( std::ranges::input_range<OutputT>,
 "Could not deduce the return type." );
 static_assert(allocator<A<U>, U>, "Could not deduce allocator type.");
 const auto results = std::ranges::transform_view(
 input,
 [&f](const T& x)constexpr{ return traverse(x, f); } );
 return OutputT(results.begin(), results.end());
}
/* An overload similar to the above, intended for containers such as std::set.
 * which take both a comparator and an allocator. Assumes that both are
 * classes with a single template parameter, the Key.
 */
template< template<class K, class C, class A> class Container,
 typename F,
 typename K,
 template<typename> class C,
 template<typename> class A
 >
 requires (!std::regular_invocable<F, Container<K, C<K>, A<K>>>) &&
 std::ranges::input_range<Container< K, C<K>, A<K> >> &&
 constructible_from_iterators<Container<K, C<K>, A<K>>> &&
 std::copy_constructible<F> &&
 std::is_object_v<F> &&
 allocator<A<K>, K> &&
 comparator<C<K>, K>
constexpr auto traverse( const Container<K, C<K>, A<K>>& input, const F& f )
{
 using U = decltype(traverse(std::declval<K>(), f));
 using OutputT = Container<U, C<U>, A<U>>;
 static_assert( std::ranges::input_range<OutputT>,
 "Could not deduce the return type." );
 static_assert(allocator<A<U>, U>, "Could not deduce allocator type.");
 static_assert(comparator<C<U>, U>, "Could not deduce comparator type.");
 const auto results = std::ranges::transform_view(
 input,
 [&f](const K& x)constexpr{ return traverse(x, f); } );
 return OutputT(results.begin(), results.end());
}

A bit of test framework:

#include <assert.h>
#include <concepts>
#include <cstdlib>
#include <iostream>
#include <source_location>
template <class T, class U>
 requires std::equality_comparable_with<T, U>
void expect_test( const T& expected,
 const U& got,
 const std::source_location location =
 std::source_location::current() )
{
 if (expected == got) {
 std::cout << "Test at "
 << location.function_name() << " ("
 << location.file_name() << ':'
 << location.line() << ':'
 << location.column() << ')'
 << " passed.\n";
 std::cout.flush();
 } else {
 std::cout.flush();
 // Flush stderr here if necessary.
 std::cerr << "Test at "
 << location.function_name() << " ("
 << location.file_name() << ':'
 << location.line() << ':'
 << location.column() << ')'
 << " FAILED!\n"
 << "Expected: " << expected << '\n'
 << "Got: " << got << '\n';
 std::exit(EXIT_FAILURE);
 }
}

And a test harness:

#include <array>
#include <iostream>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <vector>
using std::cerr, std::cout, std::endl, std::size_t;
/* A classic ASCII-only lowercase function, */
constexpr char8_t lowercase(const char c) noexcept
{
 return static_cast<char8_t>(( c >= 'A' && c <= 'Z' ) ?
 (c + ('a' - 'A')) :
 c);
}
int main()
{
 { // Test 1:
 static constexpr std::array<unsigned, 5> test_data1 = { 1, 2, 3, 4, 5 };
 static constexpr auto test_result1 = traverse( test_data1,
 [](const unsigned& x)constexpr{ return static_cast<double>(x); }
 );
 for ( size_t i = 0; i < test_result1.size(); ++i ) {
 expect_test(test_data1[i], test_result1[i]);
 }
 }
 { // Test 2:
 static const std::vector<char> test_data2 = {'H','e','l','l','o',',',' ','W','O','R','L','D','!','0円'};
 static const auto test_result2 = traverse( test_data2,
 &lowercase );
 static constexpr char8_t expected2[] = u8"hello, world!";
 
 if ( test_result2.size() == sizeof(expected2) &&
 memcmp( test_result2.data(), expected2, sizeof(expected2) ) == 0 ) {
 cout << "Test 2 passed." << endl;
 } else {
 cout.flush();
 cerr << "Test 2 FAILED with: "
 << reinterpret_cast<const char*>(test_result2.data())
 << endl;
 }
 }
 { // Test 3:
 static const std::set<int> test_data3 = {2,3,4,5,6};
 static const auto test_result3 = traverse( test_data3, std::negate<int>{} );
 static const std::set<int> expected3 = {-2,-3,-4,-5,-6};
 
 if (test_result3 == expected3) {
 cout << "Test 3 passed." << endl;
 } else {
 cerr << "Test 3 FAILED." << endl;
 }
 }
 { // Test 4:
 static const std::vector<std::array<int, 2>> test_data4 =
 { {1, 0}, {0, 1} };
 const auto test_result4 = traverse( test_data4,
 [](const std::array<int, 2>& v)constexpr{ return v[0]+v[1]; } 
 );
 static const std::vector<int> expected4 = {1, 1};
 if (test_result4 == expected4) {
 cout << "Test 4 passed." << endl;
 } else {
 cerr << "Test 4 FAILED." << endl;
 }
 }
 return EXIT_SUCCESS;
}

And here again is the link to the code on Godbolt.

• JimmyHu: Considering this, I prefer to use recursive_invoke_result_t instead of using decltype... like using U = decltype(traverse(std::declval<T>(), f));.
• Davislor: @JimmyHu But, that’s a great point and I should bring it up in my answer.
• Davislor: @JimmyHu Edited (and also made my code a bit more like OP’s).
• Davislor: @JimmyHu Okay, a follow-up. If you prefer to have a struct provide the return type as an alias, and not needing to call decltypw, there’s a way to have the best of both worlds. Declare a struct recursive_transform template with a using result_type declaration and astatic constexpr result_type operator() that takes two arguments. Then move the type constraints to the struct declaration and the implementation to operator().