How to make a SFINAE-based Y combinator in C++?

I was thinking about the implicit templates of C++14, and I'm trying to declare a function to match an specific argument type (SFINAE and traits still give me headaches). I'm not sure how to explain what I want, but I'm trying to make a Y combinator (just to see if it's possible, not intended for production).

I'm trying to declare a function:

template<typename T>
my_traits<T>::return_type Y(T t) {
  // ...
};

Such that T is a function (or a functor) that matches

std::function<R(F, Args...)>

// where F (and above return_type) will be
std::function<R(Args...)>

Which would take any number of arguments, but the first should be a function with the same return type and the same arguments (except this function itself). The first parameter to the operator () of the functor is a template.

The usage I want to achieve:

auto fib = [](auto myself, int x) {
  if(x < 2)
    return 1;
  return myself(x - 1) + myself(x - 2);
};

// The returned type of fib should be assignable to std::function<int(int)>

I wasn't able to take the return type of the T type (because of the overloaded operator ()). What I'm trying to make is possible? How could I make it?

Edit:

Seeing it from a different angle, I'm trying to make this work:

struct my_functor {
  template<typename T>
  char operator () (T t, int x, float y) { /* ... */ };
};

template<typename T>
struct my_traits {
  typedef /* ... */ result_type;

  /* ... */
};

// I want this to be std::function<char(int, float)>, based on my_functor
using my_result =
my_traits<my_functor>::result_type;

Solution

It is not possible in C++14 return type deduction to deduce int(int) out of int(T, int) as OP desires.

However, we can mask the first parameter of the result using the following approach. The struct YCombinator is instantiated with a non-recursive function object member, whose first argument is a version of itself without the first argument. YCombinator provides a call operator that receives the arguments of the non-recursive function and then returns its function object member after substituting itself for the first argument. This technique allows the programmer to avoid the messiness of myself(myself, ...) calls within the definition of the recursive function.

template<typename Functor>
struct YCombinator
{
    Functor functor;

    template<typename... Args>
    decltype(auto) operator()(Args&&... args)
    {
        return functor(*this, std::forward<Args>(args)...);
    }
};

A make_YCombinator utility template allows for a streamlined usage pattern. This compiles run runs in GCC 4.9.0.

template<typename Functor>
decltype(auto) make_YCombinator(Functor f) { return YCombinator<Functor> { f }; }

int main()
{
    auto fib = make_YCombinator([](auto self, int n) -> int { return n < 2 ? 1 : self(n - 1) + self(n - 2); });

    for (int i = 0; i < 10 ; ++i)
        cout << "fib(" << i << ") = " << fib(i) << endl;

    return 0;
}

Since the non-recursive function is not defined at time that the recursive function is defined, in general the recursive function must have an explicit return type.

Edit:

However, it may be possible for the compiler to deduce the return type in certain cases if the programmer takes care to indicate the return type of the recursive function before use of the non-recursive function. While the above construction requires an explicit return type, in the following GCC 4.9.0 has no problem deducing the return type:

    auto fib = make_YCombinator([](auto self, int n) { if (n < 2) return 1; return self(n - 1) + self(n - 2); });

To pin this down just a bit further, here is a quote from the draft C++14 standard on return type deduction [7.1.6.4.11]:

If the type of an entity with an undeduced placeholder type is needed to determine the type of an expression, the program is ill-formed. Once a return statement has been seen in a function, however, the return type deduced from that statement can be used in the rest of the function, including in other return statements. [ Example:
auto n = n; // error, n’s type is unknown
auto f();
void g() { &f; } // error, f’s return type is unknown
auto sum(int i) {
if (i == 1)
    return i; // sum’s return type is int
else
    return sum(i-1)+i; // OK, sum’s return type has been deduced
}
—end example ]