26

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

4

3 回答 3

27

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's 的类型必须是

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

soself的类型必须是

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

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

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

于 2015-01-07T09:00:19.320 回答
15

正如其他人指出的那样，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+1时执行。x相反，C++ 代码很好。某些替换导致错误代码的事实a现在无关紧要。

推迟这个检查会导致一些“无限类型的值”大致被允许。Python 或 Scheme 等动态语言进一步将这些类型错误推迟到运行时，当然也可以很好地处理自应用程序。

于 2015-01-07T10:40:07.067 回答
6

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

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

lambda 表达式的类型（也是闭包对象的类型）是唯一的、未命名的非联合类类型——称为闭包类型——其属性如下所述。此类类型既不是聚合（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 的类型，即使它不是你可以以其他方式命名的类型。

于 2015-01-07T08:00:27.107 回答