# 27 Algorithms library [algorithms]

## 27.6 Non-modifying sequence operations [alg.nonmodifying]

### 27.6.18 Fold [alg.fold]

```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); 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); ```
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); 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); ```
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); 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); ```
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); 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); ```
Let U be decltype(ranges​::​fold_right(first, last, iter_value_t<I>(*first), f)).
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 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); ```
Let U be decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>.
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)};
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 below ranges::fold_left_first_with_iter(I first, S last, F f); 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 below ranges::fold_left_first_with_iter(R&& r, F f); ```
Let U be decltype(ranges::fold_left(std::move(first), last, iter_value_t<I>(*first), f))
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)};
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.