boost/hana/functional/fix.hpp

   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
  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