<div dir="ltr"><div><div><div><div><div><div><div><div><div><div><div><div>For me, I didn't fully appreciate the Y combinator until I had had an opportunity to play with and explore other combinators.<br><br></div>The book that made this fun for me was "To Mock a Mockingbird", a puzzle book by Raymond Smullyan.  <br>
<br></div>Chapters 9 and 10 give you all the building blocks you need to appreciate the Y combinator, but if you can make it to chapter 13, you'll then understand several different ways to achieve the same effect.<br>
<br></div>The combinators are described playfully in terms of birds.<br></div>M is the mockingbird, following the rule: Mx = xx<br>(define M (ë (x) (x x)))<br><br></div>L is the lark, following the rule: <br>Lxy = x(yy)<br>
(define L (ë (x) (ë (y) (x (y y)))))<br><br></div>B is the bluebird:<br></div>Bxyz = x(yz)<br>(define B (ë (x) (ë (y) (ë (z) (x (y z))))))<br><br></div><div>Sage birds (<span class="">è) are birds that produce fixed points:<br>
</span><br></div><div><span class="">x(</span><span class="">èx) = </span><span class="">èx</span></div><div><br></div><div>All sage birds can be used to do the recursive trick that you can do with the Y combinator.<br><br>
</div><div>The Y combinator basically corresponds to the following way of creating a sage bird:<br></div><div>Y = BML<br></div><br></div>(define Y ((B M) L))<br><br></div>As others have already pointed out, this doesn't quite work unless you're in a lazy language.  You need to redefine the lark as follows, turning (y y) into the equivalent, but delayed  (ë (z) ((y y) z)):<br>
<br>(define L (ë (x) (ë (y) (x (ë (z) ((y y) z))))))<br><br>Summary:<br>(define M (ë (x) (x x)))<br>(define L (ë (x) (ë (y) (x (ë (z) ((y y) z))))))<br>(define B (ë (x) (ë (y) (ë (z) (x (y z))))))<br><br>(define Y ((B M) L))<br>
<br></div>I find it much easier to think of the Y combinator this way, built up from easy-to-understand components (at least the components are easy to understand after you've played around for hours with puzzles that use them).<br>
<br>Definitely check out the Smullyan book, it's very enjoyable.<br><br></div>Mark<br></div>