4094. ranges::fold_meow is overconstrained

Section: 26.6.18 [alg.fold] Status: New Submitter: Hewill Kang Opened: 2024-05-03 Last modified: 2024-06-24

Priority: 3

View other active issues in [alg.fold].

View all other issues in [alg.fold].

View all issues with New status.

Discussion:

The two convertible_to constraints required by ranges::fold_meow mainly check whether the decayed result type of the binary operator can be constructed by both the invoke type and the initial value type.

However, using constructible_from seems more appropriate here because we don't need to care whether the two types can be converted implicitly and explicitly. Taking string and string_view as examples, the former can only be explicitly constructed by the latter and can be assigned by the latter, which makes ranges::fold_meow unable to fold ranges whose elements are of type string with an initial value of type string_view:

vector<string> vs{"a", "b", "c"};
string_view init{"d"};
auto result = ranges::fold_right(vs, init, plus{}); // still ill-formed after P2591R5 as the constraint is not satisfied

In addition, the two movable constraints in the function signature seem to be too strict as well since we only need to check that the decayed result type and the initial type can be move-constructible (one for returned by elidable move and one for move into other overloads) instead of whether they can be move-assignable.

[2024-06-24; Reflector poll]

Set priority to 3 after reflector poll. "NAD. Constraining algorithms is not about limiting the constraints to the bare minimum required by implementation details. That's what the C++0x attempt did - in an effort to maintain backward compatibility - and it's a mess. While the string/string_view case might look superficially appealing, it would also allow vector<string>/int, which is much less so."

Proposed resolution:

This wording is relative to N4981.

1. Modify 26.4 [algorithm.syn], header <algorithm> synopsis, as indicated:

   #include <initializer_list>     // see 17.11.2 [initializer.list.syn]
   
   namespace std {
     […]
     namespace ranges {
       […]
       template<class F, class T, class I, class U>
         concept indirectly-binary-left-foldable-impl =  // exposition only
           movablemove_constructible<T> && movablemove_constructible<U> &&
           convertible_toconstructible_from<T, U, T> && invocable<F&, U, iter_reference_t<I>> &&
           assignable_from<U&, invoke_result_t<F&, U, iter_reference_t<I>>>;
   
       template<class F, class T, class I>
         concept indirectly-binary-left-foldable =      // exposition only
           copy_constructible<F> && indirectly_readable<I> &&
           invocable<F&, T, iter_reference_t<I>> &&
           convertible_toconstructible_from<decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>,
                  decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>> &&
           indirectly-binary-left-foldable-impl<F, T, I,
                           decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>>;
       […]
     }
     […]
   }
   

2. Modify 26.6.18 [alg.fold] as indicated:

   template<bidirectional_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
            indirectly-binary-right-foldable<T, I> F>
     constexpr auto ranges::fold_right(I first, S last, T init, F f);
   template<bidirectional_range R, class T = range_value_t<R>,
            indirectly-binary-right-foldable<T, iterator_t<R>> F>
     constexpr auto ranges::fold_right(R&& r, T init, F f);
   

   -3- Effects: Equivalent to:

   using U = decay_t<invoke_result_t<F&, iter_reference_t<I>, T>>;
   if (first == last)
     return U(std::move(init));
   I tail = ranges::next(first, last);
   U accum =(invoke(f, *--tail, std::move(init)));
   while (first != tail)
     accum = invoke(f, *--tail, std::move(accum));
   return accum;
   

   […]

   template<input_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
            indirectly-binary-left-foldable<T, I> F>
     constexpr see below ranges::fold_left_with_iter(I first, S last, T init, F f);
   template<input_range R, class T = range_value_t<R>,
            indirectly-binary-left-foldable<T, iterator_t<R>> F>
     constexpr see below ranges::fold_left_with_iter(R&& r, T init, F f);
   

   -6- Let U be decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>.

   -7- Effects: Equivalent to:

   if (first == last)
     return {std::move(first), U(std::move(init))};
   U accum =(invoke(f, std::move(init), *first));
   for (++first; first != last; ++first)
     accum = invoke(f, std::move(accum), *first);
   return {std::move(first), std::move(accum)};
   

   -8- Remarks: The return type is fold_left_with_iter_result<I, U> for the first overload and fold_left_with_iter_result<borrowed_iterator_t<R>, U> for the second overload.