]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Defines `boost::hana::fix`. | |
4 | ||
b32b8144 | 5 | @copyright Louis Dionne 2013-2017 |
7c673cae FG |
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 | ||
1e59de90 | 19 | namespace boost { namespace hana { |
7c673cae FG |
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 | ||
1e59de90 | 62 | BOOST_HANA_INLINE_VARIABLE constexpr detail::create<fix_t> fix{}; |
7c673cae FG |
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 | |
1e59de90 | 81 | }} // end namespace boost::hana |
7c673cae FG |
82 | |
83 | #endif // !BOOST_HANA_FUNCTIONAL_FIX_HPP |