hana/functional/fix.hpp

0001 /*!
0002 @file
0003 Defines `boost::hana::fix`.
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_FIX_HPP
0011 #define BOOST_HANA_FUNCTIONAL_FIX_HPP
0012
0013 #include <boost/hana/config.hpp>
0014 #include <boost/hana/detail/create.hpp>
0015
0016 #include <utility>
0017
0018
0019 namespace boost { namespace hana {
0020     //! @ingroup group-functional
0021     //! Return a function computing the fixed point of a function.
0022     //!
0023     //! `fix` is an implementation of the [Y-combinator][], also called the
0024     //! fixed-point combinator. It encodes the idea of recursion, and in fact
0025     //! any recursive function can be written in terms of it.
0026     //!
0027     //! Specifically, `fix(f)` is a function such that
0028     //! @code
0029     //!     fix(f)(x...) == f(fix(f), x...)
0030     //! @endcode
0031     //!
0032     //! This definition allows `f` to use its first argument as a continuation
0033     //! to call itself recursively. Indeed, if `f` calls its first argument
0034     //! with `y...`, it is equivalent to calling `f(fix(f), y...)` per the
0035     //! above equation.
0036     //!
0037     //! Most of the time, it is more convenient and efficient to define
0038     //! recursive functions without using a fixed-point combinator. However,
0039     //! there are some cases where `fix` provides either more flexibility
0040     //! (e.g. the ability to change the callback inside `f`) or makes it
0041     //! possible to write functions that couldn't be defined recursively
0042     //! otherwise.
0043     //!
0044     //! @param f
0045     //! A function called as `f(self, x...)`, where `x...` are the arguments
0046     //! in the `fix(f)(x...)` expression and `self` is `fix(f)`.
0047     //!
0048     //! ### Example
0049     //! @include example/functional/fix.cpp
0050     //!
0051     //! [Y-combinator]: http://en.wikipedia.org/wiki/Fixed-point_combinator
0052 #ifdef BOOST_HANA_DOXYGEN_INVOKED
0053     constexpr auto fix = [](auto&& f) {
0054         return [perfect-capture](auto&& ...x) -> decltype(auto) {
0055             return forwarded(f)(fix(f), forwarded(x)...);
0056         };
0057     };
0058 #else
0059     template <typename F>
0060     struct fix_t;
0061
0062     BOOST_HANA_INLINE_VARIABLE constexpr detail::create<fix_t> fix{};
0063
0064     template <typename F>
0065     struct fix_t {
0066         F f;
0067
0068         template <typename ...X>
0069         constexpr decltype(auto) operator()(X&& ...x) const&
0070         { return f(fix(f), static_cast<X&&>(x)...); }
0071
0072         template <typename ...X>
0073         constexpr decltype(auto) operator()(X&& ...x) &
0074         { return f(fix(f), static_cast<X&&>(x)...); }
0075
0076         template <typename ...X>
0077         constexpr decltype(auto) operator()(X&& ...x) &&
0078         { return std::move(f)(fix(f), static_cast<X&&>(x)...); }
0079     };
0080 #endif
0081 }} // end namespace boost::hana
0082
0083 #endif // !BOOST_HANA_FUNCTIONAL_FIX_HPP