Using Y Combinator to create recursive lambda functions in C#
It is often the case that you have to resort to a particular solution due to a specific constraint of the programming language you are using.
That solution it often haunts you for days or weeks since you wish there was a way to accomplish what you wanted to do in the first place.
Today while I was at home resting from an accident I had a couple of days ago, I recall a nifty high-order function called the Y-Combinator which would had solved the problem I had at hand at that time.
Without revealing the specific details of the system I was working on, I will outline a simple data structure that has the following shape:
As you can see, a Node instance can have a parent Node and to find the root Node you need to traverse the Node up the hierarchy chain until you find a Node instance with a Parent property equal to null.
I needed to get the root Node in a specific part of program and I was fine by doing it so using a one-off function just to comply with the interface I was implementing:
Recursive lambda solution
I thought on doing a recursive lambda function inside my GetRootNodeTitle method to get my root Node and then return its Title property, something along these lines:
However, C# doesn’t allow using a variable without initializing it first, hence, our call to rootNode from itself is invalid and throws an error at compile time.
Initializing the lambda before using it
One way to make the previous attempt to work is by initializing the lambda function so we can call it recursively.
That solves our problem but it feels kinda hacky.
A simple definition of what the Y-Combinator enables can be found in this SO answer, for the lazy, here I quote the SO answer:
Long story short, it allows you to implement recursion in a language that doesn’t necessarily support it natively.
Cool, so with that we could overcome C# limitation of using recursion in lambda functions.
First we need to implement the Y-Combinator in C#, I used this SO answer as inspiration.
With that new tool in hand we can implement our service as follows:
There we go, with this handy trick we no longer need to do a dummy initialisation of our lambda variable in order to be able to call it recursively.
As cool as the Y-Combinator is, I kept my original solution as it was since it seemed to be easier to understand and didn’t introduce any new constructs to the system I was working on.
That being said, I think on those C# solutions where a functional programming style is required the Y-Combinator is a handy tool to implement recursion inline without falling back into explicit class methods.
Here is the solution I ended up using: