Fixed point combinator (tools/fix.hpp)

template <typename G>
(see below) fix(G g);

It returns a fixed point of its argument function. When f(args...) is invocable and g(f, args...) is invocable, tools::fix(g)(args...) returns f(args...).

Usage

tools::fix([&](auto&& fib, const int n) -> int {
  return n >= 2 ? fib(n - 2) + fib(n - 1) : n;
})(10);

Constraints

g(f, args...) is invocable.
f(args...) is invocable.

Time Complexity

It depends on g.

References

C++のラムダで再帰する - koturnの日記

License

According to the source, “ブログ上のコードはコピペ自由です．”

Author

koturn

Required by

Verified with

Code

#ifndef TOOLS_FIX_HPP
#define TOOLS_FIX_HPP

#include <utility>
#include <type_traits>

namespace tools {
  template <typename F>
  struct fix : F {
    template <typename G>
    fix(G&& g) : F({::std::forward<G>(g)}) {
    }

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const {
      return F::operator()(*this, ::std::forward<Args>(args)...);
    }
  };

  template <typename F>
  fix(F&&) -> fix<::std::decay_t<F>>;
}

#endif

#line 1 "tools/fix.hpp"



#include <utility>
#include <type_traits>

namespace tools {
  template <typename F>
  struct fix : F {
    template <typename G>
    fix(G&& g) : F({::std::forward<G>(g)}) {
    }

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const {
      return F::operator()(*this, ::std::forward<Args>(args)...);
    }
  };

  template <typename F>
  fix(F&&) -> fix<::std::decay_t<F>>;
}