Как определить функцию Фибоначчи из нерекурсивной версии?

Question

Я изучаю C ++. В качестве упражнения для себя я пытаюсь определить функцию Фибоначчи из нерекурсивной версии, используя Y-комбинатор.

В F # ( или C # ) я бы сделал это так:

let rec Y f n = f (Y f) n
let protoFib f x = if n > 1 then f(n-1) + f(n-2) else n
let fib = Y protoFib

В C ++ я застрял, как определить Y

чтобы работали следующие строки

int protoFib(int f(int), int n) { 
    return (n > 1) ? f(n-1) + f(n-2) : n; 
}

int fib(int n) { return Y(protoFib, n); }

Я попробовал следующее объявление функции (специфичное для функций int, потому что я еще не изучал шаблоны):

#include <functional>
int Y(std::function<int(std::function<int(int)>, int)>, int);

но я застрял при написании определения функции.

Есть предложения?

Answer 1

Сначала напишу плохой, если функциональный, Y-комбинатор.

using fib_f = std::function<int(int)>;
using protofib_f = std::function< int( fib_f, int ) >;

int protofib( std::function<int(int)> f, int n) {
  if (n>1) return f(n-1)+f(n-1);
  return n;
}

auto Y( protofib_f f )->fib_f {
  return [=](int n) { return f( Y(f), n ); };
}

некрасиво, но работает.

Мы можем написать лучший комбинатор Y.

template<class R>
auto Y = [&](auto&& f){
  return [=](auto&&...args)->R {
    return f( Y<R>(f), decltype(args)(args)... );
  };
};

Для простоты необходимо указать тип возвращаемого значения.

auto fib = Y<int>(protofib);

также откладывает стирание типа, что дает производительность.

Мы можем раздеть тип стирания формы протофиб:

auto protofib = [](auto&& f, int n)->int {
  if (n>1) return f(n-1)+f(n-1);
  return n;
};

, превратив его в лямбду.

Для улучшенного Y-комбинатора требуется немного больше шаблонов, потому что лямбды не могут получить к нему доступ:

template<class F>
struct y_combinate_t {
  F f;
  template<class...Args>
  decltype(auto) operator()(Args&&...args)const {
    return f(*this, std::forward<Args>(args)...);
  }
};
template<class F>
y_combinate_t<std::decay_t<F>> y_combinate( F&& f ) {
  return {std::forward<F>(f)};
};

опять же, накладные расходы на стирание нулевого типа, и этот не требует, чтобы возвращаемый тип передавался явно. (украдено у меня за здесь ).

В c ++ 17 хелпер y_combinate может быть исключен:

template<class F>
struct y_combinate {
  F f;
  template<class...Args>
  decltype(auto) operator()(Args&&...args)const {
    return f(*this, std::forward<Args>(args)...);
  }
};
template<class F>
y_combinate(F&& f)->y_combinate<std::decay_t<F>>;

с руководством по удержанию.

y_combinate{ protofib }

- это полная функция Фиббоначи.

Живой пример .

Если пойти еще дальше, вы можете добавить памятку к вашему комбинатору.

Answer 2

из камня Россета https://rosettacode.org/wiki/Y_combinator#C.2B.2B для комбинатора Y:

template <typename F>
struct RecursiveFunc {
    std::function<F(RecursiveFunc)> o;
};

template <typename A, typename B>
std::function<B(A)> Y (std::function<std::function<B(A)>(std::function<B(A)>)> f) {
    RecursiveFunc<std::function<B(A)>> r = {
        std::function<std::function<B(A)>(RecursiveFunc<std::function<B(A)>>)>([f](RecursiveFunc<std::function<B(A)>> w) {
            return f(std::function<B(A)>([w](A x) {
                return w.o(w)(x);
            }));
        })
    };
    return r.o(r);
}

Я рекомендую вам проверить весь код для этого примера, так как он содержит другие способы его реализации (например, использование лямбда-выражений))