hana/functional/iterate.hpp

0001 /*!
0002 @file
0003 Defines `boost::hana::iterate`.
0004
0005 Copyright Louis Dionne 2013-2022
0006 Distributed under the Boost Software License, Version 1.0.
0007 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
0008  */
0009
0010 #ifndef BOOST_HANA_FUNCTIONAL_ITERATE_HPP
0011 #define BOOST_HANA_FUNCTIONAL_ITERATE_HPP
0012
0013 #include <boost/hana/config.hpp>
0014 #include <boost/hana/core/when.hpp>
0015 #include <boost/hana/functional/partial.hpp>
0016
0017 #include <cstddef>
0018
0019
0020 namespace boost { namespace hana {
0021     //! @ingroup group-functional
0022     //! Applies another function `n` times to its argument.
0023     //!
0024     //! Given a function `f` and an argument `x`, `iterate<n>(f, x)` returns
0025     //! the result of applying `f` `n` times to its argument. In other words,
0026     //! @code
0027     //!     iterate<n>(f, x) == f(f( ... f(x)))
0028     //!                         ^^^^^^^^^^ n times total
0029     //! @endcode
0030     //!
0031     //! If `n == 0`, `iterate<n>(f, x)` returns the `x` argument unchanged
0032     //! and `f` is never applied. It is important to note that the function
0033     //! passed to `iterate<n>` must be a unary function. Indeed, since `f`
0034     //! will be called with the result of the previous `f` application, it
0035     //! may only take a single argument.
0036     //!
0037     //! In addition to what's documented above, `iterate` can also be
0038     //! partially applied to the function argument out-of-the-box. In
0039     //! other words, `iterate<n>(f)` is a function object applying `f`
0040     //! `n` times to the argument it is called with, which means that
0041     //! @code
0042     //!     iterate<n>(f)(x) == iterate<n>(f, x)
0043     //! @endcode
0044     //!
0045     //! This is provided for convenience, and it turns out to be especially
0046     //! useful in conjunction with higher-order algorithms.
0047     //!
0048     //!
0049     //! Signature
0050     //! ---------
0051     //! Given a function \f$ f : T \to T \f$ and `x` and argument of data
0052     //! type `T`, the signature is
0053     //! \f$
0054     //!     \mathtt{iterate_n} : (T \to T) \times T \to T
0055     //! \f$
0056     //!
0057     //! @tparam n
0058     //! An unsigned integer representing the number of times that `f`
0059     //! should be applied to its argument.
0060     //!
0061     //! @param f
0062     //! A function to apply `n` times to its argument.
0063     //!
0064     //! @param x
0065     //! The initial value to call `f` with.
0066     //!
0067     //!
0068     //! Example
0069     //! -------
0070     //! @include example/functional/iterate.cpp
0071 #ifdef BOOST_HANA_DOXYGEN_INVOKED
0072     template <std::size_t n>
0073     constexpr auto iterate = [](auto&& f) {
0074         return [perfect-capture](auto&& x) -> decltype(auto) {
0075             return f(f( ... f(forwarded(x))));
0076         };
0077     };
0078 #else
0079     template <std::size_t n, typename = when<true>>
0080     struct iterate_t;
0081
0082     template <>
0083     struct iterate_t<0> {
0084         template <typename F, typename X>
0085         constexpr X operator()(F&&, X&& x) const
0086         { return static_cast<X&&>(x); }
0087     };
0088
0089     template <>
0090     struct iterate_t<1> {
0091         template <typename F, typename X>
0092         constexpr decltype(auto) operator()(F&& f, X&& x) const {
0093             return f(static_cast<X&&>(x));
0094         }
0095     };
0096
0097     template <>
0098     struct iterate_t<2> {
0099         template <typename F, typename X>
0100         constexpr decltype(auto) operator()(F&& f, X&& x) const {
0101             return f(f(static_cast<X&&>(x)));
0102         }
0103     };
0104
0105     template <>
0106     struct iterate_t<3> {
0107         template <typename F, typename X>
0108         constexpr decltype(auto) operator()(F&& f, X&& x) const {
0109             return f(f(f(static_cast<X&&>(x))));
0110         }
0111     };
0112
0113     template <>
0114     struct iterate_t<4> {
0115         template <typename F, typename X>
0116         constexpr decltype(auto) operator()(F&& f, X&& x) const {
0117             return f(f(f(f(static_cast<X&&>(x)))));
0118         }
0119     };
0120
0121     template <>
0122     struct iterate_t<5> {
0123         template <typename F, typename X>
0124         constexpr decltype(auto) operator()(F&& f, X&& x) const {
0125             return f(f(f(f(f(static_cast<X&&>(x))))));
0126         }
0127     };
0128
0129     template <std::size_t n>
0130     struct iterate_t<n, when<(n >= 6) && (n < 12)>> {
0131         template <typename F, typename X>
0132         constexpr decltype(auto) operator()(F&& f, X&& x) const {
0133             return iterate_t<n - 6>{}(f,
0134                 f(f(f(f(f(f(static_cast<X&&>(x)))))))
0135             );
0136         }
0137     };
0138
0139     template <std::size_t n>
0140     struct iterate_t<n, when<(n >= 12) && (n < 24)>> {
0141         template <typename F, typename X>
0142         constexpr decltype(auto) operator()(F&& f, X&& x) const {
0143             return iterate_t<n - 12>{}(f,
0144                 f(f(f(f(f(f(f(f(f(f(f(f(
0145                     static_cast<X&&>(x)
0146                 ))))))))))))
0147             );
0148         }
0149     };
0150
0151     template <std::size_t n>
0152     struct iterate_t<n, when<(n >= 24) && (n < 48)>> {
0153         template <typename F, typename X>
0154         constexpr decltype(auto) operator()(F&& f, X&& x) const {
0155             return iterate_t<n - 24>{}(f,
0156                 f(f(f(f(f(f(f(f(f(f(f(f(
0157                 f(f(f(f(f(f(f(f(f(f(f(f(
0158                     static_cast<X&&>(x)
0159                 ))))))))))))
0160                 ))))))))))))
0161             );
0162         }
0163     };
0164
0165     template <std::size_t n>
0166     struct iterate_t<n, when<(n >= 48)>> {
0167         template <typename F, typename X>
0168         constexpr decltype(auto) operator()(F&& f, X&& x) const {
0169             return iterate_t<n - 48>{}(f,
0170                 f(f(f(f(f(f(f(f(f(f(f(f(
0171                 f(f(f(f(f(f(f(f(f(f(f(f(
0172                 f(f(f(f(f(f(f(f(f(f(f(f(
0173                 f(f(f(f(f(f(f(f(f(f(f(f(
0174                     static_cast<X&&>(x)
0175                 ))))))))))))
0176                 ))))))))))))
0177                 ))))))))))))
0178                 ))))))))))))
0179             );
0180         }
0181     };
0182
0183     template <std::size_t n>
0184     struct make_iterate_t {
0185         template <typename F>
0186         constexpr decltype(auto) operator()(F&& f) const
0187         { return hana::partial(iterate_t<n>{}, static_cast<F&&>(f)); }
0188
0189         template <typename F, typename X>
0190         constexpr decltype(auto) operator()(F&& f, X&& x) const {
0191             return iterate_t<n>{}(static_cast<F&&>(f),
0192                                   static_cast<X&&>(x));
0193         }
0194     };
0195
0196     template <std::size_t n>
0197     BOOST_HANA_INLINE_VARIABLE constexpr make_iterate_t<n> iterate{};
0198 #endif
0199 }} // end namespace boost::hana
0200
0201 #endif // !BOOST_HANA_FUNCTIONAL_ITERATE_HPP