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

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

auto fac =后面的表达式是一个lambda表达式，编译器会自动从中生成一个闭包对象。该对象的类型是唯一的，只有编译器知道。

来自 N4296，§5.1.2/3 [expr.prim.lambda]

The type of the lambda-expression (which is also the type of the closure object) is a unique, unnamed non-union class type — called the closure type — whose properties are described below. This class type is neither an aggregate (8.5.1) nor a literal type (3.9). The closure type is declared in the smallest block scope, class scope, or namespace scope that contains the corresponding lambda-expression.

请注意，因此，即使两个相同的 lambda 表达式也将具有不同的类型。例如，

auto l1 = []{};
auto l2 = []{}; // l1 and l2 are of different types

您的 lambda 表达式是 C++14 泛型 lambda，将由编译器转换为类似于以下内容的 class：

struct __unique_name
{
    template<typename Arg1, typename Arg2>
    auto operator()(Arg1 self, Arg2 n) const
    { 
        // body of your lambda
    }
};

我无法评论 Haskell 部分，但递归表达式在 C++ 中起作用的原因是因为您只是在每次调用中传递闭包对象实例 (fac) 的副本. operator() 作为模板能够推断出 lambda 的类型，即使它不是您可以命名的类型。

Answer 2

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

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

重载调用运算符隐藏了 C++ 为实现 "lambda functions"

而执行的一些技巧

当你"call"fac时，会发生什么

fac.operator() (fac, 3);

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

模板部分不是这个工作所必需的；这是 fac "function":

的非通用版本

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 -> Int -> Int.

但是 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++ 通过其结构和成员函数生成的必要间接。

Answer 3

正如其他人指出的那样，lambda 充当涉及模板的结构。那么问题就变成了：为什么Haskell不能打字自应用，而C++可以呢？

答案在于 C++ 模板和 Haskell 多态函数之间的区别。比较这些：

-- valid Haskell
foo :: forall a b. a -> b -> a
foo x y = x

// valid C++
template <typename a, typename b>
a foo(a x, b y) { return x; }

虽然它们看起来几乎相同，但实际上并非如此。

当 Haskell 对上述声明进行类型检查时，它会检查定义对于任何类型 a,b 都是类型安全的。也就是说，如果我们将 a,b 替换为任意两种类型，则该函数必须定义明确。

C++ 采用了另一种方法。在模板定义时，不会检查 a,b 的任何替换是否正确。此检查延迟到模板的使用点，即在实例化时。为了强调这一点，让我们在代码中添加一个+1：

-- INVALID Haskell
foo :: forall a b. a -> b -> a
foo x y = x+1

// valid C++
template <typename a, typename b>
a foo(a x, b y) { return x+1; }

Haskell 定义不会进行类型检查：当 x 是任意类型时，无法保证您可以执行 x+1。相反，C++ 代码很好。 a 的某些替换导致错误代码的事实现在无关紧要。

推迟此检查会导致一些 "infinitely-typed values" 大致被允许。 Python 或 Scheme 等动态语言将这些类型错误进一步推迟到运行时间，当然会很好地处理自应用程序。

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

What is the type of this self-applying factorial function?

c++

haskell

types

generic-lambda

c++14