What is y_combinator?

Background

#

This is one of most frequently asked question on my streams.

I first heard about Y Combinator in lambda calculus course I took in my college. At that point I did not expected I will see it in competitive programming.

These days whenever I do recursion, I use it, and sharp eyes catch that something is different with this recursion.

Doing recursion in competitive programming

#

There are multiple ways to do recursion. I will show 3 ways. lets take dfs as an example.

1a: Using vanilla method with extra arguments

#

I call is a vanilla method because its the oldest one, and the first one I learnt. A typical dfs code looks like this -

void dfs(vector<vector<int>> &adj,int u,int par){
    for(auto &x:adj[u]){
        if(x==par)
            continue;
        dfs(adj,x,u);
    }
}

The problem with this approach is it requires passing all the extra variables we need everywhere even if we do not modify them. Often this ends up wasting few minutes. While coding when we realise we need more variables, this requires modifying at few places.

1b: Using vanilla method with global variable

#

Fixing the drawback of previous approach. The easiest was is to make all variables global.

vector<vector<int>> adj;

void dfs(int u,int par){
    for(auto &x:adj[u]){
        if(x==par)
            continue;
        dfs(x,u);
    }
}

This was my preferred approach for quite a few years. The problem with this is often we can forget about clearing adj before reading the new testcase.

Sneak peek: This is how my template used to look back then.

2: Using std::function in local scope

#

Later on I learnt that we can use std::function to define a local function, just like a local variable. A typical dfs code looks like this now.

int main(){
    int T; //read T
    while(T--){
        int n; //read n
        vector<vector<int>> adj(n) //read adj
        std::function<void(int,int)> dfs=[&](int u,int par)->void{
            for(auto &x:adj[u]){
            if(x==par)
                continue;
            dfs(x,u);
        };
        dfs(0,-1);
    }
    return 0;
}

We do not need global variables, neither we have to pass extra variables while doing recursion. This works for most of the cases. The only caveat with this approach is we have to declare function signature twice.

Once while declaring type, std::function<void(int,int)>, and then in lambda function [&](int u,int par)->void

Why can’t we use auto as variable type? We can do it in the following way

auto dfs=[&](auto self,int u,int par)->void{
    for(auto &x:adj[u]){
    if(x==par)
        continue;
    self(self,x,u);
};
dfs(dfs,0,-1)

Here, we need extra variable self and that needs to be passed with every function call.

3: Here comes y_combinator

#

The solution is to paste the following snippet at the top of your boiler plate code.

template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

Now dfs can be done in the following way.

int main(){
    int T; //read T
    while(T--){
        int n; //read n
        vector<vector<int>> adj(n) //read adj
        auto dfs = y_combinator([&](const auto &self,int u,int par)->void{
            for(auto &x:adj[u]){
                if(x==par)
                    continue;
                self(x,u);
            }
        });
        dfs(0,-1);
    }
    return 0;
}

This avoid writing function signature twice, with a tradeoff that we need to wrap the function inside y_combinator(....)

At present, this is my preferred approach to do recursion.

Performance difference between 2nd and 3rd approach.

#

nor claims that std::function is relatively slow.