Lambda Calculus: The Y combinator in clojure
In a previous article, we have shown how one can write recursive functions without using names.
Now, we are going to present the Y combinator.
The Y combinator is one of the most aesthetic idea of computer science. It might not be so practical, but it is really beautiful. (It has some practical usages like recursive memoization.)
The Y combinator is a function that allows to generate recursive functions without using names.
Many articles have been written about the Y combinator. The particularity of the current article is that you  the reader  are going to feel the magic of the Y combinator with your hand.
All the code snippets of this page are live and interactive powered by the klipse plugin:
 Live: The code is executed in your browser
 Interactive: You can modify the code and it is evaluated as you type
The Y combinator in action
The Ycombinator takes the idea presented in our previous article one step further and makes it applicable to any function.
Here is the code of the Ycombinator in clojure
:
(def Y (fn [f]
((fn [x]
(x x))
(fn [x]
(f (fn [y]
((x x) y)))))))
So much power in just 83 characters, with no other concepts than function definition and function execution!
Let’s see the Y combinator in action with the factorial
function. For that purpose, we need to write the factorial
function with a tweak: the recursive call is going to be parameterised. Like this:
(def factorialgen (fn [func]
(fn [n]
(if (zero? n)
1
(* n (func (dec n)))))))
And now, it’s time for magic:
((Y factorialgen) 19)
Obviously, we can write exactly the same code without names, by replacing Y
and factorialgen
with their bodies:
(((fn [f]
((fn [x]
(x x))
(fn [x]
(f (fn [y]
((x x) y))))))
(fn [func]
(fn [n]
(if (zero? n)
1
(* n (func (dec n))))))) 19)
Please take the time to play with the code above: modify the values, rename the arguments….
Then, please take a pause for a few minutes to contemplate this amazing piece of code.
After that, you have two options:

Read more about the Y combinator: Long but awesome article, Practical applications of the Y combinator, wikipedia.

Write your own recursive function without names using the Y combinator, for instance: fibonacci, quicksort, max, min…

Take a look at a real life application of the Y Combinator.
If you go for option #2, please be kind and share your code in the comments below. You might find it useful to use the KLIPSE web repl.