Skip to content

Instantly share code, notes, and snippets.

@nickknw
Created October 1, 2012 09:15
Show Gist options
  • Save nickknw/3810499 to your computer and use it in GitHub Desktop.
Save nickknw/3810499 to your computer and use it in GitHub Desktop.
Attempt at understanding the Y combinator
; http://www.dreamsongs.com/Files/WhyOfY.pdf
(define Y (lambda (f)
(let ((g (lambda (h)
(lambda (x) ((f (h h)) x)))))
(g g))))
; I understand it up to here.
; But then we have this:
; http://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combinator
(define Y
(lambda (f)
((lambda (x) (f (lambda (v) ((x x) v))))
(lambda (x) (f (lambda (v) ((x x) v)))))))
; I haven't yet convinced myself these two are the same thing. Given the
; explanation in The Why of Y, I'd expect it to look like this instead:
(define Y
(lambda (f)
((lambda (x) (lambda (v) ((f (x x)) v)))
(lambda (x) (lambda (v) ((f (x x)) v))))))
; But maybe these are the same thing? It's hard to see how.
; EDIT: I've run a couple of rudimentary tests and they appear to both function
; correctly. So it turns out they probably mean the same thing, but I'm still not
; convinced. How can both be valid?
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment