What is the type of this self-applying factorial function?

Question

I wrote an anonymous factorial function in C++ and compiled my code with g++4.9.2. It works well. However, I don't know the type of my function.

#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; } 

So, I wonder: what are the types of fac and self? If I just translate the C++ code into Haskell, it won't compile because it involves infinite types:

fac2 self 0 = 1 fac2 self n = n * (self self $ n-1) 

and I have to define some recursive type work around it:

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 

So, why could g++ get exactly the right type of the fac function, and what type does g++ think the fac function is?

Answer 1

The C++ fac isn't really a function, but a struct which has a member function.

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

The overloaded call operator hides some of the trickery that C++ performs in order to implement "lambda functions"

When you "call" fac, what happens is

fac.operator() (fac, 3); 

so the argument to the function isn't the function itself, but an object which has it as a member.
One effect of this is that the function's type (i.e. the type of operator()) does not occur in the type of the operator() function itself.
(The type of self is the struct that defines the function.)

The template part isn't necessary for this to work; this is a non-generic version of the fac "function":

struct F {     int operator()(const F& self, int n) const     {          // ...     } };  F fac; fac(fac, 3); 

If we keep the template and rename operator() to 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); } 

we see that your working Haskell program and your C++ program are very similar - the differences are mainly punctuation.

In contrast, in Haskell

fac2 self 0 = 1 fac2 self n = n * (self self $ n-1) 

self is a function, and fac2's type would have to be

X -> Int -> Int 

for some X.
Since self is a function, and self self $ n-1 is an Int, self's type is also X -> Int -> Int.

But what could X be?
It must be the same as the type of self itself, i.e X -> Int -> Int.
But that means that the type of self is (substituting for X):

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

so the type X must also be

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

so self's type must be

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

and so on, ad infinitum.
That is, in Haskell the type would be infinite.

Your solution for Haskell essentially explicitly introduces the necessary indirection that C++ generates through its structure with a member function.

Answer 2

As others pointed out, the lambda acts as a structure involving a template. The question then becomes: why Haskell can not type the self-application, while C++ can?

The answer lies on the difference between C++ templates and Haskell polymorphic functions. Compare these:

-- 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; } 

While they might look nearly equivalent, they are not really such.

When Haskell type checks the above declaration, it checks that the definition is type safe for any types a,b. That is, if we substitute a,b with any two types, the function must be well-defined.

C++ follows another approach. At template definition, it is not checked that any substitution for a,b will be correct. This check is deferred to the point of use of the template, i.e. at instantiation time. To stress the point, let's add a +1 in our code:

-- 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; } 

The Haskell definition will not type check: there's no guarantee you can perform x+1 when x is of an arbitrary type. The C++ code is fine, instead. The fact that some substitutions of a lead to incorrect code is irrelevant right now.

Deferring this check causes some "infinitely-typed values" to be allowed, roughly. Dynamic languages such as Python or Scheme further defer these type errors until run-time, and of course will handle self-application just fine.