Why do I need to specify a return value for a function I'm passing to a Y combinator

Question

I wrote a Y combinator like such:

template <class F>
struct Y{
  F f;
  Y(F _f) : f{_f} {}
  template<class...arg_t>
  auto operator()(arg_t&&...arg) {return f(*this,std::forward<arg_t>(arg)...);}
};

It works, but when I tried to define a factorial

auto fact = Y{[](auto&& self, int n) {
                if (n<=1) return 1;
                return n*self(n-1);}};

it would compile, but when I called it like f(3) clang got stuck on deducing the return type. With an explicit return type, it all worked fine. Is this a limitation of the template deduction? Is there a work-around?

Answer 1

I don't believe there is a way around it. You create a lambda with the following definition:

[](auto&& self, int n) {
            if (n<=1) return 1;
            return n*self(n-1);
 }

This translates to:

struct lambda
 {
  template <typename T1>
  constexpr auto operator()(T1&&self, int n) const
   {
            if (n<=1)
                  return 1;
            return n*self(n-1);
    }
};

Given that code, your compiler should deduce the return type as the common type of the 2 return statements.

With your template instation, it first needs to know the return type of your instantiation before it calculate the answer of that instantiation.

For this specific case, it might still be possible to deduce it correctly. What happens if you add extra indirections in between and recourse back to your type?

Answer 2

Type deduction is applied to the two return statements of the Y combinator, unconditionally, because the information held by the variable n is not a constant expression (an expression that is known by the compiler at compilation time). So the fixed point is not found by type deduction.

If n's value is known at compilation time, type deduction will succeed, example:

struct fact_overloads{
  template<class Self,int n>
  constexpr auto 
  operator()(Self&& self, std::integral_constant<n>){
    if constexpr (n<=1) return 1;
    else return n * self(std::integral_constant<n-1>{});
    };
  };

auto fact = Y{fact_overloads{}};

But such a function has a limited set of use cases because the value of n must be know at compil time.