1 /*! 2 @file 3 Defines `boost::hana::iterate`. 4 5 @copyright Louis Dionne 2013-2017 6 Distributed under the Boost Software License, Version 1.0. 7 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) 8 */ 9 10 #ifndef BOOST_HANA_FUNCTIONAL_ITERATE_HPP 11 #define BOOST_HANA_FUNCTIONAL_ITERATE_HPP 12 13 #include <boost/hana/config.hpp> 14 #include <boost/hana/core/when.hpp> 15 #include <boost/hana/functional/partial.hpp> 16 17 #include <cstddef> 18 19 20 BOOST_HANA_NAMESPACE_BEGIN 21 //! @ingroup group-functional 22 //! Applies another function `n` times to its argument. 23 //! 24 //! Given a function `f` and an argument `x`, `iterate<n>(f, x)` returns 25 //! the result of applying `f` `n` times to its argument. In other words, 26 //! @code 27 //! iterate<n>(f, x) == f(f( ... f(x))) 28 //! ^^^^^^^^^^ n times total 29 //! @endcode 30 //! 31 //! If `n == 0`, `iterate<n>(f, x)` returns the `x` argument unchanged 32 //! and `f` is never applied. It is important to note that the function 33 //! passed to `iterate<n>` must be a unary function. Indeed, since `f` 34 //! will be called with the result of the previous `f` application, it 35 //! may only take a single argument. 36 //! 37 //! In addition to what's documented above, `iterate` can also be 38 //! partially applied to the function argument out-of-the-box. In 39 //! other words, `iterate<n>(f)` is a function object applying `f` 40 //! `n` times to the argument it is called with, which means that 41 //! @code 42 //! iterate<n>(f)(x) == iterate<n>(f, x) 43 //! @endcode 44 //! 45 //! This is provided for convenience, and it turns out to be especially 46 //! useful in conjunction with higher-order algorithms. 47 //! 48 //! 49 //! Signature 50 //! --------- 51 //! Given a function \f$ f : T \to T \f$ and `x` and argument of data 52 //! type `T`, the signature is 53 //! \f$ 54 //! \mathtt{iterate_n} : (T \to T) \times T \to T 55 //! \f$ 56 //! 57 //! @tparam n 58 //! An unsigned integer representing the number of times that `f` 59 //! should be applied to its argument. 60 //! 61 //! @param f 62 //! A function to apply `n` times to its argument. 63 //! 64 //! @param x 65 //! The initial value to call `f` with. 66 //! 67 //! 68 //! Example 69 //! ------- 70 //! @include example/functional/iterate.cpp 71 #ifdef BOOST_HANA_DOXYGEN_INVOKED 72 template <std::size_t n> __anon603b1ea00102(auto&& f) 73 constexpr auto iterate = [](auto&& f) { 74 return [perfect-capture](auto&& x) -> decltype(auto) { 75 return f(f( ... f(forwarded(x)))); 76 }; 77 }; 78 #else 79 template <std::size_t n, typename = when<true>> 80 struct iterate_t; 81 82 template <> 83 struct iterate_t<0> { 84 template <typename F, typename X> 85 constexpr X operator()(F&&, X&& x) const 86 { return static_cast<X&&>(x); } 87 }; 88 89 template <> 90 struct iterate_t<1> { 91 template <typename F, typename X> 92 constexpr decltype(auto) operator()(F&& f, X&& x) const { 93 return f(static_cast<X&&>(x)); 94 } 95 }; 96 97 template <> 98 struct iterate_t<2> { 99 template <typename F, typename X> 100 constexpr decltype(auto) operator()(F&& f, X&& x) const { 101 return f(f(static_cast<X&&>(x))); 102 } 103 }; 104 105 template <> 106 struct iterate_t<3> { 107 template <typename F, typename X> 108 constexpr decltype(auto) operator()(F&& f, X&& x) const { 109 return f(f(f(static_cast<X&&>(x)))); 110 } 111 }; 112 113 template <> 114 struct iterate_t<4> { 115 template <typename F, typename X> 116 constexpr decltype(auto) operator()(F&& f, X&& x) const { 117 return f(f(f(f(static_cast<X&&>(x))))); 118 } 119 }; 120 121 template <> 122 struct iterate_t<5> { 123 template <typename F, typename X> 124 constexpr decltype(auto) operator()(F&& f, X&& x) const { 125 return f(f(f(f(f(static_cast<X&&>(x)))))); 126 } 127 }; 128 129 template <std::size_t n> 130 struct iterate_t<n, when<(n >= 6) && (n < 12)>> { 131 template <typename F, typename X> 132 constexpr decltype(auto) operator()(F&& f, X&& x) const { 133 return iterate_t<n - 6>{}(f, 134 f(f(f(f(f(f(static_cast<X&&>(x))))))) 135 ); 136 } 137 }; 138 139 template <std::size_t n> 140 struct iterate_t<n, when<(n >= 12) && (n < 24)>> { 141 template <typename F, typename X> 142 constexpr decltype(auto) operator()(F&& f, X&& x) const { 143 return iterate_t<n - 12>{}(f, 144 f(f(f(f(f(f(f(f(f(f(f(f( 145 static_cast<X&&>(x) 146 )))))))))))) 147 ); 148 } 149 }; 150 151 template <std::size_t n> 152 struct iterate_t<n, when<(n >= 24) && (n < 48)>> { 153 template <typename F, typename X> 154 constexpr decltype(auto) operator()(F&& f, X&& x) const { 155 return iterate_t<n - 24>{}(f, 156 f(f(f(f(f(f(f(f(f(f(f(f( 157 f(f(f(f(f(f(f(f(f(f(f(f( 158 static_cast<X&&>(x) 159 )))))))))))) 160 )))))))))))) 161 ); 162 } 163 }; 164 165 template <std::size_t n> 166 struct iterate_t<n, when<(n >= 48)>> { 167 template <typename F, typename X> 168 constexpr decltype(auto) operator()(F&& f, X&& x) const { 169 return iterate_t<n - 48>{}(f, 170 f(f(f(f(f(f(f(f(f(f(f(f( 171 f(f(f(f(f(f(f(f(f(f(f(f( 172 f(f(f(f(f(f(f(f(f(f(f(f( 173 f(f(f(f(f(f(f(f(f(f(f(f( 174 static_cast<X&&>(x) 175 )))))))))))) 176 )))))))))))) 177 )))))))))))) 178 )))))))))))) 179 ); 180 } 181 }; 182 183 template <std::size_t n> 184 struct make_iterate_t { 185 template <typename F> 186 constexpr decltype(auto) operator()(F&& f) const 187 { return hana::partial(iterate_t<n>{}, static_cast<F&&>(f)); } 188 189 template <typename F, typename X> 190 constexpr decltype(auto) operator()(F&& f, X&& x) const { 191 return iterate_t<n>{}(static_cast<F&&>(f), 192 static_cast<X&&>(x)); 193 } 194 }; 195 196 template <std::size_t n> 197 constexpr make_iterate_t<n> iterate{}; 198 #endif 199 BOOST_HANA_NAMESPACE_END 200 201 #endif // !BOOST_HANA_FUNCTIONAL_ITERATE_HPP 202