c++ - 这个自应用阶乘函数的类型是什么？

Question

我用 C++ 编写了一个匿名阶乘函数，并用 g++4.9.2 编译了我的代码。 它运作良好。但是，我不知道我的函数的类型。

#include<iostream>
#include<functional>
using std::function;
int main()
{
    //tested at g++ 4.9.2
    //g++ -std=c++1y -o anony anony.cpp
    auto fac = [](auto self,auto n)->auto{
        if(n < 1)
            return 1;
        else 
            return n * self(self,n-1);
    };
    std::cout<<fac(fac,3)<<std::endl;//6
    return 0;
}

那么，我想知道:fac 和 self 的类型是什么？ 如果我只是将 C++ 代码翻译成 Haskell，它将无法编译，因为 它涉及无限类型:

fac2 self 0 = 1
fac2 self n = n * (self self $ n-1)

我必须围绕它定义一些递归类型的工作:

data Y a = Y ((Y a)->a->a)
fac2 self 0 = 1
fac2 self n = n * ((applY self self) (n-1))
    where applY (Y f1) f2 = f1 f2
fact2 = fac2 $ Y fac2

那么，为什么 g++ 能得到完全正确的 fac 函数类型，而 g++ 认为 fac 函数是什么类型呢？

Answer 1

C++ fac 并不是真正的函数，而是具有成员函数的结构体。

struct aaaa // Not its real name.
{
    template<typename a, typename b>
    auto operator()(a self, b n) const
    { 
    }
};

重载的调用运算符隐藏了 C++ 为实现“lambda 函数”而执行的一些技巧

当你“调用”fac时，会发生什么

fac.operator() (fac, 3);

所以函数的参数不是函数本身，而是一个将它作为成员的对象。
这样做的一个影响是函数的类型(即 operator() 的类型)不会出现在 operator() 函数本身的类型中。
(self的类型是定义函数的结构体。)

模板部分不是这个工作所必需的；这是 fac “函数”的非通用版本:

struct F
{
    int operator()(const F& self, int n) const
    { 
        // ...
    }
};

F fac;
fac(fac, 3);

如果我们保留模板并将 operator() 重命名为 applY:

// The Y type
template<typename a>
struct Y
{
    // The wrapped function has type (Y<a>, a) -> a
    a applY(const Y<a>& self, a n) const
    { 
        if(n < 1)
            return 1;
        else 
            return n * self.applY(self, n-1);
    }
};

template<typename a>
a fac(a n)
{
    Y<a> y;
    return y.applY(y, n);
}

我们看到您的 Haskell 程序和您的 C++ 程序非常相似 - 主要区别在于标点符号。

相比之下，在 Haskell 中

fac2 self 0 = 1
fac2 self n = n * (self self $ n-1)

self 是一个函数，fac2的类型必须是

X -> Int -> Int

对于一些X。
由于self是一个函数，而self self $ n-1是一个Int，self的类型也是X ->整数 -> 整数.

但是 X 可能是什么？
它必须与self本身的类型相同，即X -> Int -> Int。
但这意味着self的类型是(代替X):

(X -> Int -> Int) -> Int -> Int  

所以类型 X 也必须是

(X -> Int -> Int) -> Int -> Int  

所以self的类型必须是

((X -> Int -> Int) -> Int -> Int) -> Int -> Int

等等，无穷无尽。
也就是说，在 Haskell 中，类型是无限的。

您的 Haskell 解决方案本质上明确地引入了 C++ 通过其具有成员函数的结构生成的必要间接。