boost/hof/fix.hpp

0001 /*=============================================================================
0002     Copyright (c) 2014 Paul Fultz II
0003     fix.h
0004     Distributed under the Boost Software License, Version 1.0. (See accompanying
0005     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 ==============================================================================*/
0007
0008 #ifndef BOOST_HOF_GUARD_FUNCTION_FIX_H
0009 #define BOOST_HOF_GUARD_FUNCTION_FIX_H
0010
0011 /// fix
0012 /// ===
0013 ///
0014 /// Description
0015 /// -----------
0016 ///
0017 /// The `fix` function adaptor implements a fixed-point combinator. This can be
0018 /// used to write recursive functions.
0019 ///
0020 /// When using `constexpr`, a function can recurse to a depth that is defined by
0021 /// `BOOST_HOF_RECURSIVE_CONSTEXPR_DEPTH`(default is 16). There is no limitiation on
0022 /// recursion depth for non-constexpr functions. In addition, due to the
0023 /// eagerness of `constexpr` to instantiation templates, in some cases, an
0024 /// explicit return type must be specified in order to avoid reaching the
0025 /// recursion limits of the compiler. This can be accomplished using
0026 /// [`boost::hof::result`](/include/boost/hof/result):
0027 ///
0028 ///     int r = boost::hof::result<int>(factorial)(5);
0029 ///
0030 /// Synopsis
0031 /// --------
0032 ///
0033 ///     template<class F>
0034 ///     constexpr fix_adaptor<F> fix(F f);
0035 ///
0036 /// Semantics
0037 /// ---------
0038 ///
0039 ///     assert(fix(f)(xs...) == f(fix(f), xs...));
0040 ///
0041 /// Requirements
0042 /// ------------
0043 ///
0044 /// F must be:
0045 ///
0046 /// * [ConstFunctionObject](ConstFunctionObject)
0047 /// * MoveConstructible
0048 ///
0049 /// Example
0050 /// -------
0051 ///
0052 ///     #include <boost/hof.hpp>
0053 ///     #include <cassert>
0054 ///
0055 ///     int main() {
0056 ///         auto factorial = boost::hof::fix(
0057 ///             [](auto recurse, auto x) -> decltype(x) {
0058 ///                 return x == 0 ? 1 : x * recurse(x-1);
0059 ///             }
0060 ///         );
0061 ///         int r = boost::hof::result<int>(factorial)(5);
0062 ///         assert(r == 5*4*3*2*1);
0063 ///     }
0064 ///
0065 /// References
0066 /// ----------
0067 ///
0068 /// * [Fixed-point combinator](https://en.wikipedia.org/wiki/Fixed-point_combinator)
0069 /// * [Recursive](Recursive)
0070 ///
0071
0072 #include <boost/hof/always.hpp>
0073 #include <boost/hof/detail/callable_base.hpp>
0074 #include <boost/hof/reveal.hpp>
0075 #include <boost/hof/detail/delegate.hpp>
0076 #include <boost/hof/detail/move.hpp>
0077 #include <boost/hof/detail/make.hpp>
0078 #include <boost/hof/detail/static_const_var.hpp>
0079 #include <boost/hof/indirect.hpp>
0080 #include <boost/hof/result.hpp>
0081 #include <boost/hof/detail/recursive_constexpr_depth.hpp>
0082
0083
0084 namespace boost { namespace hof {
0085
0086 namespace detail{
0087
0088 template<class F>
0089 struct compute_indirect_ref
0090 { typedef indirect_adaptor<const F*> type; };
0091
0092 template<class F>
0093 struct compute_indirect_ref<indirect_adaptor<F*>>
0094 { typedef indirect_adaptor<F*> type; };
0095
0096 template<class F>
0097 constexpr indirect_adaptor<const F*> make_indirect_ref(const F& f) noexcept
0098 {
0099     return indirect_adaptor<const F*>(&f);
0100 }
0101
0102 template<class F>
0103 constexpr indirect_adaptor<const F*> make_indirect_ref(const indirect_adaptor<F*>& f) noexcept
0104 {
0105     return f;
0106 }
0107
0108 template<class F, class=void>
0109 struct fix_result
0110 {
0111     template<class... Ts>
0112     struct apply
0113     {
0114         typedef decltype(std::declval<F>()(std::declval<Ts>()...)) type;
0115     };
0116 };
0117
0118 template<class F>
0119 struct fix_result<F, typename holder<
0120     typename F::result_type
0121 >::type>
0122 {
0123     template<class...>
0124     struct apply
0125     {
0126         typedef typename F::result_type type;
0127     };
0128
0129 };
0130
0131 template<class F, class Result, int N>
0132 struct fix_adaptor_base : F
0133 {
0134     BOOST_HOF_INHERIT_CONSTRUCTOR(fix_adaptor_base, F);
0135
0136     typedef typename compute_indirect_ref<F>::type base_ref_type;
0137     typedef fix_adaptor_base<base_ref_type, Result, N-1> derived;
0138
0139
0140     template<class... Ts>
0141     constexpr const F& base_function(Ts&&... xs) const noexcept
0142     {
0143         return boost::hof::always_ref(*this)(xs...);
0144     }
0145
0146     template<class... Ts>
0147     constexpr derived derived_function(Ts&&... xs) const noexcept
0148     {
0149         return derived(boost::hof::detail::make_indirect_ref(this->base_function(xs...)));
0150     }
0151
0152     struct fix_failure
0153     {
0154         template<class Failure>
0155         struct apply
0156         {
0157             template<class... Ts>
0158             struct of
0159             : Failure::template of<derived, Ts...>
0160             {};
0161         };
0162     };
0163
0164     struct failure
0165     : failure_map<fix_failure, F>
0166     {};
0167
0168
0169     BOOST_HOF_RETURNS_CLASS(fix_adaptor_base);
0170
0171     template<class... Ts>
0172     constexpr BOOST_HOF_SFINAE_RESULT(const F&, id_<derived>, id_<Ts>...)
0173     operator()(Ts&&... xs) const BOOST_HOF_SFINAE_RETURNS
0174     (
0175         BOOST_HOF_MANGLE_CAST(const F&)(BOOST_HOF_CONST_THIS->base_function(xs...))
0176             (
0177                 BOOST_HOF_MANGLE_CAST(derived)(BOOST_HOF_CONST_THIS->derived_function(xs...)),
0178                 BOOST_HOF_FORWARD(Ts)(xs)...
0179             )
0180     );
0181 };
0182
0183 template<class F, class Result>
0184 struct fix_adaptor_base<F, Result, 0> : F
0185 {
0186     BOOST_HOF_INHERIT_CONSTRUCTOR(fix_adaptor_base, F);
0187
0188     template<class... Ts>
0189     const F& base_function(Ts&&...) const noexcept
0190     {
0191         return *this;
0192     }
0193
0194     struct fix_failure
0195     {
0196         template<class Failure>
0197         struct apply
0198         {
0199             template<class... Ts>
0200             struct of
0201             : Failure::template of<fix_adaptor_base, Ts...>
0202             {};
0203         };
0204     };
0205
0206     struct failure
0207     : failure_map<fix_failure, F>
0208     {};
0209
0210
0211     BOOST_HOF_RETURNS_CLASS(fix_adaptor_base);
0212
0213     template<class... Ts>
0214     typename Result::template apply<fix_adaptor_base, Ts...>::type
0215     operator()(Ts&&... xs) const
0216     {
0217         return this->base_function(xs...)(*this, BOOST_HOF_FORWARD(Ts)(xs)...);
0218     }
0219 };
0220 }
0221
0222 template<class F>
0223 struct fix_adaptor : detail::fix_adaptor_base<F, detail::fix_result<F>, BOOST_HOF_RECURSIVE_CONSTEXPR_DEPTH>
0224 {
0225     typedef fix_adaptor fit_rewritable1_tag;
0226     typedef detail::fix_adaptor_base<F, detail::fix_result<F>, BOOST_HOF_RECURSIVE_CONSTEXPR_DEPTH> base;
0227     BOOST_HOF_INHERIT_CONSTRUCTOR(fix_adaptor, base);
0228 };
0229
0230 template<class Result, class F>
0231 struct result_adaptor<Result, fix_adaptor<F>>
0232 : fix_adaptor<result_adaptor<Result, F>>
0233 {
0234     typedef fix_adaptor<result_adaptor<Result, F>> base;
0235     BOOST_HOF_INHERIT_CONSTRUCTOR(result_adaptor, base)
0236 };
0237
0238 BOOST_HOF_DECLARE_STATIC_VAR(fix, detail::make<fix_adaptor>);
0239
0240 }} // namespace boost::hof
0241
0242 #endif