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):