Fixed point combinators are not only an interesting mental excersise, they also e.g. allow you to implement recursion in programming languages that don’t explicitly support it. This might be slightly academic, but that doesn’t make it less fun.

The most well-known fixed point combinator is probably Haskell B. Curry’s Y combinator, which will be the topic of this post. If you read The Little Schemer – which I whole-heartedly recommend doing by the way – you already implemented it once, but if you are like me chances are you didn’t entirely get it the first time around. So when I found this nice post on Deriving the Y Combinator in 7 Easy Steps, I decided to “translate” it from JavaScript to Clojure.

Step 1

Let’s start with a “classical” recursive factorial function (while we are at it, I think factorial is a way better example for a fold than for recursion, but everybody seems to do this):

Step 2

Now if we wouldn’t have explicit recursion, what could we do? One solution would be to call a function with itself as an argument, then call this argument with itself as an argument and on and on until the stack blows. Not so useful. To avoid this, we write a higher-order function which will return a function taking a numeric argument, which will then be used to calculate the factorial:

Step 3

While the above code works, all that duplicated code is really quite ugly, don’t you think? Let’s write a little helper to avoid that (I was too lazy for a proper refer-clojure statement, so I decided to name the helper “yrecur” instead of “recur”):

Step 4

This is better, but the double function call in the body of “fact” is still kinda ugly. Let’s hide this within another helper function called “g”, which has to be definied inside the closure of “f” in order to be able to call this function:

Step 5

Now we are getting somewhere! To make our factorial function look almost like the original recursive version, we can factor out some code to a separate wrapper:

Step 6

Instead of actually binding our helper from step 4 to “g”, we just inline it since it’s only called once anyway:

Step 7

Last but not least we also inline the wrapper from step 5, et voila, the Y combinator: