This is an introductory article to the Y combinator from lambda-calculus
. But we won’t mention the Y combinator
in this article.
This article is the first one of a serie about the Y combinator in clojure
:
- Recursions without names: Introduction to the Y combinator in clojure
- The Y combinator in clojure
- Y combinator real life application: recursive memoization in clojure
In this article, we are going to show how to write recursive functions in clojure
without giving names to any function.
(If you are curious to see it in other languages, there is a version of the code in javascript
, EcmaScript6
and ruby
.)
At first glance it seems impossible: how could we refer to something that we are currently defining without using its name?
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
Begin with the end in mind
The end result of this article is the recursive implementation of the factorial
function without using neither names nor loops.
Here is the code:
(((fn [f]
(f f))
(fn [func]
(fn [n]
(if (zero? n)
1
(* n ((func func) (dec n)))))))
19)
As you can check, no mention of any names.
At first, it feels like magic.
Now, we are going to show the 4 step process that leads to this wonderful piece of code.
(We were inspired by this long but awesome article by Mike Vanier.)
The process
Step 0: recursive function
Let’s start with the recursive implementation of factorial
:
(defn factorial [n]
(if (zero? n)
1
(* n (factorial (dec n)))))
(factorial 10)
Step 1: simple generator
Let’s write a function that is a generator of the factorial
function:
(defn factorial-gen [func]
(fn [n]
(if (zero? n)
1
(* n (func (dec n))))))
One one hand, factorial-gen
is not recursive.
On the other hand, factorial-gen
is not the factorial
function.
But the interesting thing is that if we pass factorial
to factorial-gen
it returns the factorial
function:
((factorial-gen factorial)
19)
Before going on reading make sure you understand why it is true that:
(factorial-gen factorial)
is exactlyfactorial
Step 2: weird generator
Now, we are going to do something very weird: instead of using func
, we are going to use (func func)
. Like this:
(defn factorial-weird [func]
(fn [n]
(if (zero? n)
1
(* n ((func func)(dec n))))))
The funny thing now is that if we apply factorial-weird
to itself we get the factorial
function:
((factorial-weird factorial-weird) 19)
Before going on reading make sure you understand why it is true that:
(factorial-weird factorial-weird)
is exactlyfactorial
Step 3: Recursion without names
Now, let’s write down the application of factorial-weird
to itself, using the body of factorial-weird
instead of its name:
(def factorial-no-names
((fn [func]
(fn [n]
(if (zero? n)
1
(* n ((func func) (dec n))))))
(fn [func]
(fn [n]
(if (zero? n)
1
(* n ((func func) (dec n))))))))
And we got a recursive implementation of factorial
without using any names!
We gave it a name just for the convenience of using it.
As you can check, this is a completely valid implementation of factorial
:
(map factorial-no-names (range 20))
Do you understand why this is equivalent to the code we shown in the beginning of the article?
(((fn [f]
(f f))
(fn [func]
(fn [n]
(if (zero? n)
1
(* n ((func func) (dec n)))))))
19)
Can you write your own implementation of recursive functions without names?
Share in the comments your implementation for:
- Fibonacci
- Quicksort
- max
- min
- …
In our next article, we are going to show the Y combinator in action in clojure
.