Skip to content

Latest commit

 

History

History
193 lines (193 loc) · 4.37 KB

Ycombinator.org

File metadata and controls

193 lines (193 loc) · 4.37 KB
Raw

Y Combinator

Recursive function definition using anonymous functions (λ)

Recursive function that calculates length of list

(define length
  (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 (length (cdr l)))))))

what if we dont have (define…)

We won’t be able to refer to length.

lengthn

length0

λ to calculate length of list equal to 0

(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1 (eternity (cdr l))))))

length1

(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1 (lambda (l)
                  (cond
                    ((null? l) 0)
                    (else (add1 (eternity (cdr l))))))
                (cdr l)))))

length2

(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1 (lambda (l)
                  (cond
                    ((null? l) 0)
                    (else (add1 (lambda (l)
                                  (cond
                                    ((null? l) 0)
                                    (else (add1 (eternity (cdr l))))))
                                (cdr l)))))
                (cdr l)))))

Recursion: Replacing function name with it’s body

Using the Nineth Commandment

Nineth Commandment
Abstract common patterns with a new function

length=0

((lambda (f)
  (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 (f (cdr l)))))))
 eternity)

length\leq1

((lambda (f)
  (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 (f (cdr l)))))))
 (lambda (l)
   (cond
     ((null? l) 0)
     (else (add1 (eternity (cdr l)))))))

length\leq2

((lambda (f)
  (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 (f (cdr l)))))))
 ((lambda (g)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (g (cdr l)))))))
  (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 (eternity (cdr l))))))))

make-length

Too much repetition- try to get rid of them.

length=0

((lambda (mk-length)
  (mk-length eternity))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

length\leq2

((lambda (mk-length)
  (mk-length
    (mk-length
      (mk-length eternity))))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

length∞

Make a new length when required.

((lambda (mk-length)
  (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 ((mk-length mk-length)
                    (cdr l))))))))

length

Let’s abstract out the mk-length to make the function look like length.

((lambda (mk-length)
  (mk-length mk-length))
 (lambda (mk-length)
   (lambda (length)
     (lambda (l)
       (cond
         ((null? l) 0)
         (else (add1 (length (cdr l)))))))
   (mk-length mk-length)))

mk-length no longer returns a function, instead it calls itself. Goes in ∞ recursion.

((mk-length mk-length) x) ;; will be infinite loop
(lambda (x)
  ((mk-length mk-length) x)) ;;will defer execution of mk-length
((lambda (mk-length)
  (mk-length mk-length))
 (lambda (mk-length)
   (lambda (length)
     (lambda (l)
       (cond
         ((null? l) 0)
         (else (add1 (length (cdr l)))))))
   (lambda (x)
     ((mk-length mk-length) x))))

Y Combinator

length doesn’t depend on mk-length. It can be taken out.

((lambda (f)
   ((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (f
       (lambda (x)
         ((mk-length mk-length) x))))))
 (lambda (length)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (add1 (length (cdr l))))))))

Let’s seperate the function that makes length from function which looks like length

(lambda (le)
   ((lambda (f)
      (f f))
    (lambda (f)
      (le (lambda (x)
         ((f f) x))))))

Applicative-order Y Combinator

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