Search code examples
lambda-calculusy-combinator

Derivation of the Y-Combinator

While going through this article about Y-combinator (which I highly recommend), I stumbled over this transformation :

(define Y 
    (lambda (f)
      ((lambda (x) (x x))
       (lambda (x) (f (x x))))))

Note that we can apply the inner lambda expression to its argument to get an equivalent version of Y:

  (define Y 
    (lambda (f)
      ((lambda (x) (f (x x)))
       (lambda (x) (f (x x))))))

Could someone please explain me how did we get to the second version of Y? Which steps did we follow to get there?

Solution

  • You are applying (lambda (x) (x x))(lambda (x) (f (x x)))
    Do the application to get (lambda (x) (f (x x))(lambda (x) (f (x x))
    Notice the left lambda creates 2 copies of its argument, which is the right lambda.