Каков тип этой самоприменимой факториальной функции?
Я написал анонимную факториальную функцию в 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 функция есть?
Решение
Выражение следующее 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() будучи шаблоном, можно определить тип лямбды, хотя это не тот тип, который вы можете назвать иначе.
Другие решения
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 ++ очень похожи — различия в основном в пунктуации.
Напротив, в Хаскеле
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 по существу явно вводит необходимую косвенность, которую C ++ генерирует через свою структуру с помощью функции-члена.
Как отмечали другие, лямбда действует как структура, включающая шаблон. Тогда возникает вопрос: почему 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 с любыми двумя типами, функция должна быть четко определена.
С ++ следует другому подходу. При определении шаблона не проверяется, что любая замена 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, дополнительно откладывают эти ошибки типов до времени выполнения и, конечно же, прекрасно справятся с самостоятельным применением.