我试图通过Y-combinator在C中引用函数名来写递归.但是,我无法在以下尝试中找出函数的类型：
- #include <iostream>
- using std::cin;
- using std::cout;
- template<class Function> unsigned long factorial1(Function self,unsigned long n) {
- return n ? n * self(self,n - 1) : 1;
- }
- unsigned long factorial(unsigned long n) {
- return factorial1(factorial1,n);
- }
- int main() {
- unsigned long n;
- cin >> n;
- cout << factorial(n) << '\n';
- return 0;
- }
编译器不能推断什么是功能,我也不能.然后我尝试了以下：
- #include <iostream>
- using std::cin;
- using std::cout;
- struct Factorial {
- template<class Function> unsigned long operator()(Function self,unsigned long n) const {
- return n ? n * self(self,n - 1) : 1;
- }
- };
- unsigned long factorial(unsigned long n) {
- return Factorial()(Factorial(),n);
- }
- int main() {
- unsigned long n;
- cin >> n;
- cout << factorial(n) << '\n';
- return 0;
- }
这与上面的例子相比,我将工作函数改为可调用对象,这个函数容易被推导为Factorial,导致以下组合器的完整实现：
- #include <iostream>
- using std::cin;
- using std::cout;
- struct Factorial {
- template<class Function> unsigned long operator()(Function self,n - 1) : 1;
- }
- };
- template<class Function> auto y(Function f) {
- return [f](auto n) {
- return f(f,n);
- };
- }
- int main() {
- unsigned long n;
- cin >> n;
- cout << y(Factorial())(n) << '\n';
- return 0;
- }
问题是,是否可以将struct Factorial重写为一个简单的函数？
解决方法
你这样做稍微有些错误：factorial1的第一个参数应该是具有类型unsigned long(*)(unsigned long)的factorial1的固定点,而不是factorial1本身,因此不需要为自己提供自己的参数：
- unsigned long factorial1(unsigned long(*self)(unsigned long),unsigned long n) {
- return n ? n * self(n - 1) : 1;
- }
C不允许作为函数指针传递闭包,所以我们必须：
>传递std ::函数或其他一些包装器作为自我.不太有意思的海事组织
>使用模板魔术在编译时生成固定点函数.
第二个选择可以轻松完成：
- template<class X,X(*Fn)(X(*)(X),X)>
- struct Fix {
- static X Function(X x) {
- return Fn(Fix<X,Fn>::Function,x);
- }
- };
现在,Fix< unsigned long,factorial1> :: Function is a fixed point of factorial1：
- unsigned long factorial(unsigned long n) {
- return Fix<unsigned long,factorial1>::Function(n);
- };
请注意,此修复实现仍以名称引用,所以任何实现固定点组合器都不会有类型的系统黑客.
