[racket] Y combinator

From: Mark Engelberg (mark.engelberg at gmail.com)
Date: Thu Feb 6 18:21:41 EST 2014

For me, I didn't fully appreciate the Y combinator until I had had an
opportunity to play with and explore other combinators.

The book that made this fun for me was "To Mock a Mockingbird", a puzzle
book by Raymond Smullyan.

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.

The combinators are described playfully in terms of birds.
M is the mockingbird, following the rule: Mx = xx
(define M (λ (x) (x x)))

L is the lark, following the rule:
Lxy = x(yy)
(define L (λ (x) (λ (y) (x (y y)))))

B is the bluebird:
Bxyz = x(yz)
(define B (λ (x) (λ (y) (λ (z) (x (y z))))))

Sage birds (θ) are birds that produce fixed points:

x(θx) = θx

All sage birds can be used to do the recursive trick that you can do with
the Y combinator.

The Y combinator basically corresponds to the following way of creating a
sage bird:

(define Y ((B M) L))

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

(define L (λ (x) (λ (y) (x (λ (z) ((y y) z))))))

(define M (λ (x) (x x)))
(define L (λ (x) (λ (y) (x (λ (z) ((y y) z))))))
(define B (λ (x) (λ (y) (λ (z) (x (y z))))))

(define Y ((B M) L))

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

Definitely check out the Smullyan book, it's very enjoyable.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140206/d261ec7b/attachment.html>

Posted on the users mailing list.