What type is this lambda's parameter?

Question

I was experimenting with functional programming, and I wrote this.

[=](auto p) { 
    return [=](auto q) { 
        return p(q)(p); 
    }; 
})

I started wondering how this is possible, what is the type of p?

So, I wrote something like this.

template<class Type>
using LambdaType = std::function<std::function<Type(Type)>(Type)>;

and

[=](LambdaType<int> p) {
    return [=](LambdaType<int> q) {
        return p(q)(p);
    };
}

When compiling it, the compiler would give me errors.

error C2664: 'std::function<Type (int)> std::_Func_class<_Ret,int>::operator ()(int) const': cannot convert argument 1 from 'std::function<std::function<Type (int)> (int)>' to 'int'
error C2664: 'main::<lambda_cec7eb77d9cd29f3c40710200090f154>::()::<lambda_b8db28542cb51159223ad8d89c63d794>::()::<lambda_224126017af42fcee190e88f299089fc>::()::<lambda_415db9fd88f1008b25af42ccb33b1c77> main::<lambda_cec7eb77d9cd29f3c40710200090f154>::()::<lambda_b8db28542cb51159223ad8d89c63d794>::()::<lambda_224126017af42fcee190e88f299089fc>::operator ()(std::function<std::function<Type (std::function<std::function<int (int)> (int)>)> (std::function<std::function<int (int)> (int)>)>) const': cannot convert argument 1 from 'main::<lambda_cec7eb77d9cd29f3c40710200090f154>::()::<lambda_b8db28542cb51159223ad8d89c63d794>::()::<lambda_fa72c454c823301ba6dfa9cba6f558e0>' to 'std::function<std::function<Type (std::function<std::function<int (int)> (int)>)> (std::function<std::function<int (int)> (int)>)>'

But that's when I realized that p only takes in ints, but p needs to be a LambdaType<LambdaType<int>> to take in q but when you change p to a LambdaType<LambdaType<int>>, then p only takes in LambdaType<int> but p is not a LambdaType<int>, and it needs to be a LambdaType<LambdaType<LambdaType<int>>> to take in p.

So, what type is p?

Oh by the way, this is my first question on stackoverflow

Answer 1

Well, we're looking for four types P, Q, R, S such as:

• P(Q) -> R
• R(P) -> S

Q and S are no more than placeholder argument and return types, so we don't need anything from them:

struct Q { };
struct S { };

P and R are more interesting, because there's a loop in the specification of the signatures they need: R is both the result of an invocation of P, and able to be called with another P. That makes it impossible to declare with a function type or a lambda type, which are only defined by their (here infinitely recursive) signature.

But C++ can sort it out easily with functors -- just give the thing a name, and with the help of a simple forward-declaration you can create your loopy functor just fine:

struct P;

struct R {
    S operator()(P) const;
};

struct P {
    R operator()(Q) const { return {}; }
};

inline S R::operator()(P) const { return {}; }

Live demo on Coliru

---

Lastly, C++ has templates, and that gives us the power to solve this with the most boring solution ever:

struct O {
    template <class T>
    O const &operator()(T) const { return *this; }
};

Such an O will just swallow whatever you call it with, even an instance of itself, and not even care.

Live demo on Coliru