1 /*! 2 @file 3 Defines `boost::hana::fix`. 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_FIX_HPP 11 #define BOOST_HANA_FUNCTIONAL_FIX_HPP 12 13 #include <boost/hana/config.hpp> 14 #include <boost/hana/detail/create.hpp> 15 16 #include <utility> 17 18 19 BOOST_HANA_NAMESPACE_BEGIN 20 //! @ingroup group-functional 21 //! Return a function computing the fixed point of a function. 22 //! 23 //! `fix` is an implementation of the [Y-combinator][], also called the 24 //! fixed-point combinator. It encodes the idea of recursion, and in fact 25 //! any recursive function can be written in terms of it. 26 //! 27 //! Specifically, `fix(f)` is a function such that 28 //! @code 29 //! fix(f)(x...) == f(fix(f), x...) 30 //! @endcode 31 //! 32 //! This definition allows `f` to use its first argument as a continuation 33 //! to call itself recursively. Indeed, if `f` calls its first argument 34 //! with `y...`, it is equivalent to calling `f(fix(f), y...)` per the 35 //! above equation. 36 //! 37 //! Most of the time, it is more convenient and efficient to define 38 //! recursive functions without using a fixed-point combinator. However, 39 //! there are some cases where `fix` provides either more flexibility 40 //! (e.g. the ability to change the callback inside `f`) or makes it 41 //! possible to write functions that couldn't be defined recursively 42 //! otherwise. 43 //! 44 //! @param f 45 //! A function called as `f(self, x...)`, where `x...` are the arguments 46 //! in the `fix(f)(x...)` expression and `self` is `fix(f)`. 47 //! 48 //! ### Example 49 //! @include example/functional/fix.cpp 50 //! 51 //! [Y-combinator]: http://en.wikipedia.org/wiki/Fixed-point_combinator 52 #ifdef BOOST_HANA_DOXYGEN_INVOKED __anonedc5e6d90102(auto&& f) 53 constexpr auto fix = [](auto&& f) { 54 return [perfect-capture](auto&& ...x) -> decltype(auto) { 55 return forwarded(f)(fix(f), forwarded(x)...); 56 }; 57 }; 58 #else 59 template <typename F> 60 struct fix_t; 61 62 constexpr detail::create<fix_t> fix{}; 63 64 template <typename F> 65 struct fix_t { 66 F f; 67 68 template <typename ...X> 69 constexpr decltype(auto) operator()(X&& ...x) const& 70 { return f(fix(f), static_cast<X&&>(x)...); } 71 72 template <typename ...X> 73 constexpr decltype(auto) operator()(X&& ...x) & 74 { return f(fix(f), static_cast<X&&>(x)...); } 75 76 template <typename ...X> 77 constexpr decltype(auto) operator()(X&& ...x) && 78 { return std::move(f)(fix(f), static_cast<X&&>(x)...); } 79 }; 80 #endif 81 BOOST_HANA_NAMESPACE_END 82 83 #endif // !BOOST_HANA_FUNCTIONAL_FIX_HPP 84