Какова форма этой самопривлекательной факториальной функции?

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 =, является выражением лямбда, и компилятор автоматически генерирует из него объект замыкания. Тип этого объекта уникален и известен только компилятору.

От N4296, §5.1.2/3[expr.prim.lambda]

Типом лямбда-выражения (который также является тип объекта замыкания) представляет собой уникальный, неназванный тип неединичного класса - называется замыкающим типом - свойства которого описаны ниже. Этот тип класса не является ни агрегатом (8.5.1), ни буквальным типом (3.9). Тип замыкания объявляется в наименьшей области блока, области видимости класса или области пространства имен, которая содержит соответствующее лямбда-выражение.

Обратите внимание, что из-за этого даже два идентичных лямбда-выражения будут иметь разные типы. Например,

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

---

Вашей лямбда-выражение является C++ 14 общей лямбда, и будет переведено компилятором в класс, который напоминает следующее:

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

Я не могу комментировать на части Haskell, но причина, по которой рекурсивное выражение работает в C++, состоит в том, что вы просто передаете копию экземпляра объекта закрытия (fac) в каждом вызове. operator(), являющийся шаблоном, способен выводить тип лямбда, хотя это не тот, который вы можете назвать иначе.

Answer 2

C++ fac на самом деле не функция, а структура, которая имеет функцию-член.

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

Перегруженный оператор вызова скрывает некоторые из жульничества, C++ выполняет для реализации «лямбда-функции»

Когда вы «называют» 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 be?
Он должен быть таким же, как и сам тип self, то есть X -> Int -> Int.
Но это означает, что тип self является (заменяющий X):

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

поэтому тип X также должен быть

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

так self «s тип должен быть

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

и т.д., ad infinitum.
То есть, в Haskell тип был бы бесконечным.

Ваше решение для Haskell по сути явно вводит необходимую косвенность, которую C++ генерирует через свою структуру с помощью функции-члена.

Answer 3

Как указывалось другими, лямбда действует как структура, включающая шаблон.Тогда возникает вопрос: почему 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, откладывают эти ошибки до времени выполнения и, конечно же, отлично справляются с самоприложением.