是否有可能在C++中创建一个可以自行调用的实际函数类型？

Question

我试图通过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;
}

编译器不能推断出什么是Function,我也不能.然后我尝试了以下内容:

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

这与上面的例子相比,不同之处在于我将工作函数更改为可调用对象,这Function可以很容易地推导出来Factorial,从而导致组合器的以下完整实现:

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

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

问题是,是否可以将结构重写Factorial为普通函数？

Answer 1

在我看来，您所描述的情况类似于无限类型或递归类型。如果您尝试自己手动推导类型，您会发现它是无限的，您也可能自己发现了这一点。为了表明这一点，我想将您的factorial1功能简化为：

template <class T> void foobar(T self) {
    self(self);
}

然后尝试使用函数指针而不是模板来编写此函数，以手动推断其类型。

首先，我们希望它foobar以函数指针作为参数。

void foobar(void (*self)());
            ^^^^^^^^^^^^^^

但这仍然不是我们想要的，这个函数指针应该将指向自身的指针作为参数。

void foobar(void (*self)(void (*)()));
                         ^^^^^^^^^^

但我们还没有完成，因为我们必须再次添加一个指向自身的指针作为参数

void foobar(void (*self)(void (*)(void (*)())));
                                  ^^^^^^^^^^

你可以看到这种模式是如何持续下去的。

void foobar(void (*self)(void (*)(void (*)(void (*)()))));
                                           ^^^^^^^^^^

void foobar(void (*self)(void (*)(void (*)(void (*)(void (*)())))));
                                                    ^^^^^^^^^^

你给出的例子，你设法用一个结构来做到这一点，只是通过模仿它operator()。如果将该函数的名称更改为foobar如下所示：

struct Factorial {
    template<class Function> unsigned long foobar(Function self, unsigned long n) const {
        return n ? n * self.foobar(self, n - 1) : 1;
    }
};

unsigned long factorial(unsigned long n) {
    return Factorial().foobar(Factorial(), n);
}

因此，您基本上foobar在 中 递归地调用foobar，这与您最初的声明相矛盾，即您希望在不知道/引用函数名称的情况下调用该函数。