时间戳

首页 > 解决方案 > 如何从非递归版本定义斐波那契函数？

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

问题描述

我正在学习 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);

但我坚持编写函数定义。

有什么建议么？

标签： c++y-combinator

解决方案

首先，我将编写一个糟糕的、功能性的 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 组合器需要更多样板，因为 lambdas 无法访问：

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

再次，零类型擦除开销，并且这个不需要显式传递返回类型。（从我这里偷来的）。

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

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

活生生的例子。

更进一步，您可以将记忆添加到您的 y 组合器中。

推荐阅读