c++ - 如何从非递归版本定义斐波那契函数？

Question

我正在学习 C++。作为我自己的练习，我尝试使用 Y 组合器从非递归版本定义斐波那契函数。

在 F# ( or 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);

它还推迟了类型删除，从而提高了性能。

我们可以从 protofib 中剥离类型删除:

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

通过将其转换为 lambda。

改进的 Y 组合器需要更多样板，因为 lambda 无法访问它:

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)};
};

同样，零类型删除开销，并且不需要显式传递返回类型。 (在 here 上从我自己那里偷来的)。

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

然后是一个完整的斐波那契函数。

Live example .

更进一步，您可以添加 memoization到你的 y 组合器。