(defn Y [r]
((fn [f] (f f))
(fn [f]
(r (fn [x] ((f f) x))))))
There’s few things as iconic as the Y-Combinator in functional programming.
The Y combinator can be thought of as a higher-order function that takes a function (which represents some sort of recursive logic) and returns its fixed point. This fixed point is the recursive function you want to call repeatedly.
What’s a fixed point?
A fixed point of a function is a value that is unchanged by the function’s application.
(= (f x) x)
To see how a Y-Combinator can be used, let’s start with a recursive function:
(defn factorial [n]
(if (zero? n)
1
(* n (factorial (dec n)))))
But this case involves a named self-application, not an anonymous function.
However, you can also define such a function without named recursion by using the Y-Combinator above:
(def factorial-y
(Y (fn [fact]
(fn [n]
(if (zero? n)
1
(* n (fact (dec n))))))))
Notice that factorial-y doesn’t call itself, and that an anonymous function is used within its definition.
This shows quite the connection between finding fixed points (a bit more math-y than my current knowledge, but seems to relate to many kinds of math like differential equations, integral equations, topology, etc) and doing recursion with lambda calculus (the underlying model when dealing with functional languages like Clojure or other lisps) – math and programming concepts meeting up.
I must mention http://www.fatvat.co.uk/2009/04/understanding-y-combinator.html as providing a good explanation. To learn more, check out the wiki.
Also, I liked this topic so much that I made a wallpaper:
