ranges::fold_meow is overconstrained
Hewill Kang

Created on 2024-05-03.00:00:00 last changed 1 month ago


Date: 2024-05-05.09:41:01

Proposed resolution:

This wording is relative to N4981.

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

    #include <initializer_list>     // see [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 [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.

Date: 2024-05-03.00:00:00

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.

Date User Action Args
2024-05-05 09:41:01adminsetmessages: + msg14111
2024-05-03 00:00:00admincreate