The Y combinator is a somewhat magical aspect of the untyped lambda calculus. Many people tried to explain this magic, but I found them somewhat unsatisfactory.
- Most explanations show the combinator in the beginning and then simply demonstrate that the given combinator is correct.
- Some other explanations contain lines like “Why don’t we try passing it to itself? And look, this turns out to be exactly what we want!”
The problem with these is that they don’t give an intuition for how one could constructively derive the combinator. What on earth makes you think that passing it to itself is a good idea? As such, this post, intended for those who know the Y combinator already but do not satisfy with the existing explanations, attempts to explain how one could constructively derive the Y combinator.