Typedef for recursive lambda

Question

Is there a way to create a typedef such that the following (a basic "pure" implementation of the y-combinator) would compile?

typedef ??? f;
[](f x){x(x);} ([](f x){x(x);});

This has the effect of creating a "recursive lambda", i.e. one which calls itself by using a second lambda to get a reference to itself. x in the first lambda is a reference to the second lambda, so x(x) calls the second lambda with a reference to itself. Thereafter, the second lambda recurses by calling x(x). This code, when executed, should produce an infinite loop until it hits stack overflow. More sophisticated implementations of the second function can produce arbitrary recursive behaviour.

I have tried typedefing various versions of void(*)(...) but I do not believe that can succeed. My template metaprogramming is not strong enough to handle this kind of thing.

Answer 1

How about this one?

#include <functional>
#include <iostream>

struct X
{
    template<typename F>
    X(F f) : _f(f)
    { }

    void operator () (std::function<void(X)> f)
    {
        std::cout << "Calling myself..." << std::endl;
        _f(f);
    }

    std::function<void(X)> _f;
};

int main()
{
    typedef X f;
    [](f x){x(x);} ([](f x){x(x);});
}