Title
ranges::fold_meow should explicitly spell out the return type
Status
new
Section
[algorithm.syn][alg.fold]
Submitter
Hewill Kang

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

Messages

Date: 2024-05-05.10:18:42

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<input_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
                 indirectly-binary-left-foldable<T, I> F>
          constexpr auto fold_left(I first, S last, T init, F f) ->
            decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>;
    
        template<input_range R, class T = range_value_t<R>,
                 indirectly-binary-left-foldable<T, iterator_t<R>> F>
          constexpr auto fold_left(R&& r, T init, F f) ->
            decay_t<invoke_result_t<F&, T, range_reference_t<R>>>;
    
        template<input_iterator I, sentinel_for<I> S,
                 indirectly-binary-left-foldable<iter_value_t<I>, I> F>
          requires constructible_from<iter_value_t<I>, iter_reference_t<I>>
          constexpr auto fold_left_first(I first, S last, F f) ->
            optional<decay_t<invoke_result_t<F&, iter_value_t<I>, iter_reference_t<I>>>>;
    
        template<input_range R, indirectly-binary-left-foldable<range_value_t<R>, iterator_t<R>> F>
          requires constructible_from<range_value_t<R>, range_reference_t<R>>
          constexpr auto fold_left_first(R&& r, F f) ->
            optional<decay_t<invoke_result_t<F&, range_value_t<R>, range_reference_t<R>>>>;
    
        template<bidirectional_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
                 indirectly-binary-right-foldable<T, I> F>
          constexpr auto fold_right(I first, S last, T init, F f) ->
            decay_t<invoke_result_t<F&, iter_reference_t<I>, T>>;
    
        template<bidirectional_range R, class T = range_value_t<R>,
                 indirectly-binary-right-foldable<T, iterator_t<R>> F>
          constexpr auto fold_right(R&& r, T init, F f) ->
            decay_t<invoke_result_t<F&, range_reference_t<R>, T>>;
    
        template<bidirectional_iterator I, sentinel_for<I> S,
                 indirectly-binary-right-foldable<iter_value_t<I>, I> F>
          requires constructible_from<iter_value_t<I>, iter_reference_t<I>>
        constexpr auto fold_right_last(I first, S last, F f) ->
          optional<decay_t<invoke_result_t<F&, iter_reference_t<I>, iter_value_t<I>>>>;
    
        template<bidirectional_range R,
                 indirectly-binary-right-foldable<range_value_t<R>, iterator_t<R>> F>
          requires constructible_from<range_value_t<R>, range_reference_t<R>>
        constexpr auto fold_right_last(R&& r, F f) ->
          optional<decay_t<invoke_result_t<F&, range_reference_t<R>, range_value_t<R>>>>;
    
        template<class I, class T>
          using fold_left_with_iter_result = in_value_result<I, T>;
        template<class I, class T>
          using fold_left_first_with_iter_result = in_value_result<I, T>;
    
        template<input_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
                 indirectly-binary-left-foldable<T, I> F>
          constexpr see belowauto fold_left_with_iter(I first, S last, T init, F f) ->
            fold_left_with_iter_result<I, decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>>;
    
        template<input_range R, class T = range_value_t<R>,
                 indirectly-binary-left-foldable<T, iterator_t<R>> F>
          constexpr see belowauto fold_left_with_iter(R&& r, T init, F f) ->
            fold_left_with_iter_result<borrowed_iterator_t<R>,
                                       decay_t<invoke_result_t<F&, T, range_reference_t<R>>>>;
    
        template<input_iterator I, sentinel_for<I> S,
                 indirectly-binary-left-foldable<iter_value_t<I>, I> F>
          requires constructible_from<iter_value_t<I>, iter_reference_t<I>>
          constexpr see belowauto fold_left_first_with_iter(I first, S last, F f) ->
            fold_left_first_with_iter_result<
              I, optional<decay_t<invoke_result_t<F&, iter_value_t<I>, iter_reference_t<I>>>>>;
    
        template<input_range R,
                 indirectly-binary-left-foldable<range_value_t<R>, iterator_t<R>> F>
          requires constructible_from<range_value_t<R>, range_reference_t<R>>
          constexpr see belowauto fold_left_first_with_iter(R&& r, F f) ->
            fold_left_first_with_iter_result<
              borrowed_iterator_t<R>,
              optional<decay_t<invoke_result_t<F&, range_value_t<R>, range_reference_t<R>>>>>;
      }
      […]
    }
    
  2. Modify [alg.fold] as indicated:

    template<input_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
             indirectly-binary-left-foldable<T, I> F>
    constexpr auto ranges::fold_left(I first, S last, T init, F f) ->
      decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>;
    
    template<input_range R, class T = range_value_t<R>,
             indirectly-binary-left-foldable<T, iterator_t<R>> F>
    constexpr auto ranges::fold_left(R&& r, T init, F f) ->
      decay_t<invoke_result_t<F&, T, range_reference_t<R>>>;
    

    -1- Returns:

    ranges::fold_left_with_iter(std::move(first), last, std::move(init), f).value
    
    template<input_iterator I, sentinel_for<I> S,
             indirectly-binary-left-foldable<iter_value_t<I>, I> F>
      requires constructible_from<iter_value_t<I>, iter_reference_t<I>>
      constexpr auto ranges::fold_left_first(I first, S last, F f) ->
        optional<decay_t<invoke_result_t<F&, iter_value_t<I>, iter_reference_t<I>>>>;
    
    template<input_range R, indirectly-binary-left-foldable<range_value_t<R>, iterator_t<R>> F>
      requires constructible_from<range_value_t<R>, range_reference_t<R>>
      constexpr auto ranges::fold_left_first(R&& r, F f) ->
        optional<decay_t<invoke_result_t<F&, range_value_t<R>, range_reference_t<R>>>>;
    

    -2- Returns:

    ranges::fold_left_first_with_iter(std::move(first), last, f).value
    
    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) ->
        decay_t<invoke_result_t<F&, iter_reference_t<I>, T>>;
    
    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) ->
        decay_t<invoke_result_t<F&, range_reference_t<R>, T>>;  
    

    -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<bidirectional_iterator I, sentinel_for<I> S,
            indirectly-binary-right-foldable<iter_value_t<I>, I> F>
      requires constructible_from<iter_value_t<I>, iter_reference_t<I>>
    constexpr auto ranges::fold_right_last(I first, S last, F f) ->
      optional<decay_t<invoke_result_t<F&, iter_reference_t<I>, iter_value_t<I>>>>;
    
    template<bidirectional_range R,
             indirectly-binary-right-foldable<range_value_t<R>, iterator_t<R>> F>
     requires constructible_from<range_value_t<R>, range_reference_t<R>>
    constexpr auto ranges::fold_right_last(R&& r, F f) ->
      optional<decay_t<invoke_result_t<F&, range_reference_t<R>, range_value_t<R>>>>;
    

    -4- Let U be decltype(ranges::fold_right(first, last, iter_value_t<I>(*first), f)).

    -5- Effects: Equivalent to:

    if (first == last)
      return optional<U>();
    I tail = ranges::prev(ranges::next(first, std::move(last)));
    return optional<U>(in_place,
      ranges::fold_right(std::move(first), tail, iter_value_t<I>(*tail), std::move(f)));
    
    template<input_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
             indirectly-binary-left-foldable<T, I> F>
      constexpr see belowauto ranges::fold_left_with_iter(I first, S last, T init, F f) ->
        fold_left_with_iter_result<I, decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>>;
    
    template<input_range R, class T = range_value_t<R>,
             indirectly-binary-left-foldable<T, iterator_t<R>> F>
      constexpr see belowauto ranges::fold_left_with_iter(R&& r, T init, F f) ->
        fold_left_with_iter_result<borrowed_iterator_t<R>,
                                   decay_t<invoke_result_t<F&, T, range_reference_t<R>>>>;
    

    -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.

    template<input_iterator I, sentinel_for<I> S,
             indirectly-binary-left-foldable<iter_value_t<I>, I> F>
      requires constructible_from<iter_value_t<I>, iter_reference_t<I>>
      constexpr see belowauto ranges::fold_left_first_with_iter(I first, S last, F f) ->
        fold_left_first_with_iter_result<
          I, optional<decay_t<invoke_result_t<F&, iter_value_t<I>, iter_reference_t<I>>>>>;
    
    template<input_range R,
             indirectly-binary-left-foldable<range_value_t<R>, iterator_t<R>> F>
      requires constructible_from<range_value_t<R>, range_reference_t<R>>
      constexpr see belowauto ranges::fold_left_first_with_iter(R&& r, F f) ->
        fold_left_first_with_iter_result<
          borrowed_iterator_t<R>,
          optional<decay_t<invoke_result_t<F&, range_value_t<R>, range_reference_t<R>>>>>;
    

    -9- Let U be

    decltype(ranges::fold_left(std::move(first), last, iter_value_t<I>(*first), f))
    

    -10- Effects: Equivalent to:

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

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

Date: 2024-05-03.00:00:00

Unlike other algorithms, the return types of ranges::fold_meow are specified in terms of auto and see blew, and its implementation details depend on the return types of other overloads through decltype(fold_meow(...)).

This makes determining the return type of a certain overload (such as fold_right_last) extremely difficult even for experts, requiring several trips back and forth to different overloads to finally understand what the actual return type is. The situation is even worse for newbies because such a form of specifying the return type makes it impossible for the IDE to deduce the real return type, which is extremely user-unfriendly.

I think that explicitly specifying the return type for these overloads not only greatly improves readability but also offloads the compiler from deducing the return type, which can definitely be considered an improvement.

The proposed resolution does not touch the Effects clause and only changes the function signature to seek minimal changes.

History
Date User Action Args
2024-05-05 10:18:42adminsetmessages: + msg14113
2024-05-03 00:00:00admincreate