我试图通过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);
};
请注意,此修复实现仍以名称引用,所以任何实现固定点组合器都不会有类型的系统黑客.