这种自适应因子函数的类型是什么？

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 -> 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 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+1在x任意类型时都可以执行.相反,C++代码很好.a导致错误代码的一些替换现在无关紧要.

延迟此检查会导致一些"无限类型值"被允许,大致.诸如Python或Scheme之类的动态语言进一步将这些类型错误推迟到运行时,并且当然会处理自我应用程序.

Answer 3

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

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

的类型的λ-表达(这也是封闭的对象的类型)是一个独特的,无名不愈合类类型-称为闭合类型 -其特性如下所述.此类类型既不是聚合(8.5.1)也不是文字类型(3.9).闭包类型在包含相应lambda表达式的最小块作用域,类作用域或命名空间作用域中声明.

请注意,因此,即使两个相同的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在每次调用中传递闭包对象instance()的副本.在operator()作为一个模板,能够推导出拉姆达的类型,即使它不是一个你可以以其他方式命名.