title: What is the type of this self-applying factorial function?
body: <p>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.</p>
  
  <pre><code>#include&lt;iostream&gt;
  #include&lt;functional&gt;
  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)-&gt;auto{
          if(n &lt; 1)
              return 1;
          else 
              return n * self(self,n-1);
      };
      std::cout&lt;&lt;fac(fac,3)&lt;&lt;std::endl;//6
      return 0;
  }
  </code></pre>
  
  <p>So, I wonder: what are the types of <code>fac</code> and <code>self</code>?
  If I just translate the C++ code into Haskell, it won't compile because
  it involves infinite types:</p>
  
  <pre><code>fac2 self 0 = 1
  fac2 self n = n * (self self $ n-1)
  </code></pre>
  
  <p>and I have to define some recursive type  work around it:</p>
  
  <pre><code>data Y a = Y ((Y a)-&gt;a-&gt;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
  </code></pre>
  
  <p>So, why could g++ get exactly the right type of the <code>fac</code> function, and what type does g++ think the <code>fac</code> function is?</p>