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

user_742350 0
Viewed 89

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?

template-argument-deduction y-combinator templates functional-programming c++
2 Answers

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?

user_24664310

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.

user_56323160
Related