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

Answer 2

Implementation level

In c++, Lambda is implemented with a struct with operator(), whose name is unknown. Because the keyword auto here means type is generic, so template is required. You must explicitly instantiate the struct by giving the arguments for the struct templates, then what 'a and 'b stand for can be determined.

Abstract level

p(q)(p);
  ↑

Assume the type of p is 'a->'b

• 'a is the type of parameter
• 'b is the return type

---

p(q)(p);
     ↑

We can see the return type('b) can receive a p, whose type is 'a->'b, so we can replace 'b with 'a->'b. Is the the problem resolved? No!

Unlike trival recursive function like factorial:

std::function<int(int)> factorial = [&](int a) {return a == 1 ? 1 : a*factorial(a-1);};

• For Factorial: its return type still is not relying on the type(Factorial) itself.
• For p: its return type relies on ps type. So the type is infinite.

Just like @molbdnilo's comment:

It has an infinite type and can't be instantiated.