To understand the theory of recursive functions you must understand fixed points, but I think there's a simpler way to understand the magic of the Y combinator.<p>Here's how it works. Say we have a recursive function like <i>map</i>:<p><pre><code> map f [] = [] -- We'll ignore the base case since there's no recursion here
map f (x:xs) = f x : map f xs -- This is the interesting part
</code></pre>
We want to write this more primitively, without explicit recursion. How can we do that? Well, if it's possible at all, we obviously need to get rid of the <i>map</i> on the right hand side of the second case.<p>How? Well, let's abstract over the recursive call, replacing it with a function that we'll add as parameter to our definition:<p><pre><code> map' _ f [] = [] -- Still boring
map' g f (x:xs) = f x : g g f xs -- Pay attention for later!
</code></pre>
(Read <i>map'</i> as "map-prime", i.e., a variant of the definition of <i>map</i>.)<p>All we've done so far is replaced <i>map'</i> where it should be on the right-hand side of its own definition with <i>g</i>, and then added <i>g</i> as parameter of the function. We end up with a double <i>g</i> on the right-hand side because of that added parameter.<p>OK, now what? Well, we need somehow to make <i>g</i> be <i>map'</i>, the thing we're defining. which means we need somehow to pass our definition of <i>map'</i> to itself, so that (in the second case) we'd end up with something that evaluates to:<p><pre><code> map' map' f (x:xs) = f x : map' map' f xs
</code></pre>
Then the right hand side would obviously be right; it's what we were shooting for at the start (assuming we can get <i>map' map'</i> to equal <i>map</i>, which is what we're trying to do). The left hand side looks a little strange [0], but it's just saying that we need the first parameter of our definition to be the the thing we're defining.<p>So how do we make this happen? Well, what is <i>map map f (x:xs)</i>? It's <i>map</i> applied to itself, then to some other arguments we need. So the key, it seems, is to figure out how to apply <i>map</i> to itself. Well, in the lambda calculus that's pretty easy [1]:<p><pre><code> why f x y = f f x y
</code></pre>
That is, <i>why</i> is just<p><pre><code> lambda f. lambda x. lambda y. (f f) x) y
</code></pre>
OK, so <i>fix</i> takes a function and applies it to itself (after applying it first to arguments <i>x</i> and <i>y</i>). Great. That's what we needed. Now we can take our defintion of <i>map'</i> (the one marked <i>Pay attention for later!</i> above) and do this:<p><pre><code> map = why map'
</code></pre>
And I've re-used the name <i>map</i> there because we can easily show that this definition is equivalent to our original definition of <i>map</i> by showing that it reduces to the same expression:<p><pre><code> map f (x:xs) = why map' f (x:xs)
== (by def. of `why`)
map' map' f (x:xs)
== (by def. of `map'`
f x : map' map' f xs
</code></pre>
Which, if you keep expanding the expression <i>map' map' f xs</i>, you will see is indeed equal to the definition of <i>map</i>.<p>Voilà. So that wasn't too hard. It's basically two steps: (1) abstract over the recursive call, then (2) figure out how to pass the function you're defining to itself. If you look at the Y combinator, you'll see that that's exactly what's going on there.<p>If this didn't make a lot of sense to you, it's probably because I wrote it on my iPad at 4:30 in the morning. It really is just those two steps: abstract over the recursive call, then self-apply. ...<p>To get deeper into the recursive mindset (if you're not there yet) and to build up deliberately to the Y combinator, take a look at one of my favorite books on functional programming, <i>The Little Schemer</i> [2]. (And watch out for the jelly stains!)<p>------<p>0. And it's ill typed, but never mind that. It's not possible to define the Y combinator (or any other fixed-point combinator) in the simply typed-lambda calculus, so just imagine that my Haskell-style syntax is untyped, like the basic lambda calculus.<p>1. Although, again, there's no way to give <i>fix</i> a good type in the simply typed lambda calculus.<p>2. <a href="http://www.amazon.com/The-Little-Schemer-4th-Edition/dp/0262560992" rel="nofollow">http://www.amazon.com/The-Little-Schemer-4th-Edition/dp/0262...</a>