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

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函数的类型是什么？

- Alaya

---

这里的fac是通用lambda，它像一个带有模板化operator()的函数对象。请注意，这些是C++14中新增的。 - user657267

顺便提一下，编写Haskell版本的更好方法是将其分成递归部分（即通常和泛化的fix :: (a -> a) -> a与fix f = f(fix f)）和非递归部分。非递归部分是fact1 recur n = if n == 0 then 1 else n * recur (n-1)，你会注意到这个函数(a)不是递归的，(b)有一个有限且可推断的类型fact1 :: (Int -> Int) -> (Int -> Int)，(c)实现了阶乘的单个“步骤”。然后我们只需通过组合递归和非递归部分来“完成”它：fact = fix fact1。 - J. Abrahamson

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - J. Abrahamson

这并不是很相关，但你可以将你的Y类型写成一个newtype而不是data，这会导致更高效的运行时表示。 - dfeuer

哦，是的，我现在记得了：Data.Function 中的定义使 fix (1:) 成为一个循环链表，而不是无限列表，类似于其他一些东西。它可以让你把数据结构打成结，而更明显的 fix f = f (fix f) 则不行。 - dfeuer

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 -> 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++ 通过其具有成员函数的结构体生成的必要间接引用。

- molbdnilo

Answer 2

正如其他人指出的那样，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的结果导致的不正确代码的事实并不重要。

推迟此检查会导致一些“无限类型值”被允许，大致如此。像Python或Scheme等动态语言会进一步延迟这些类型错误直到运行时，并且当然会很好地处理自我应用。

- chi

Answer 3

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

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

lambda-expression 的类型（也是闭包对象的类型）是一个独特的、未命名的非联合类类型——称为闭包类型——其属性如下所述。该类类型既不是聚合体（8.5.1），也不是字面量类型（3.9）。闭包类型在最小的块作用域、类作用域或命名空间作用域中声明，该作用域包含相应的lambda-expression。

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

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

---

您的lambda表达式是一个C++14通用lambda，编译器将把它翻译为类似于以下内容的类：

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

我无法对Haskell部分进行评论，但是C ++中递归表达式工作的原因是在每次调用时仅传递闭包对象实例 (fac) 的副本。 operator() 是一个模板，能够推导出Lambda的类型，即使它不是您可以命名的类型。

- Praetorian