Y combinator (Little Schemer)

ycombinator.ss

; function to find the length of a list
(define length
  (lambda (l)
    (cond
     ((null? l) 0)
     (else (+ 1 (length (cdr l)))))))

; function that recurs infinitely
(define eternity
  (lambda (l)
    (eternity l)))

; function application that finds length of lists of size 0
((lambda (l)
  (cond
   ((null? l) 0)
   (else (+ 1 (eternity (cdr l)))))) ())

; function application for longer lists that does not complete
((lambda (l)
  (cond
   ((null? l) 0)
   (else (+ 1 (eternity (cdr l)))))) '(1 2 3))

; function that finds length of lists of size 0 using define
(define length0
  (lambda (l)
    (cond
     ((null? l) 0)
     (else (+ 1 (eternity (cdr l)))))))

(length0 ())

; function that finds length of lists of size 1 using define
((lambda (l)
   (cond
    ((null? l) 0)
    (else (+ 1
             (length0 (cdr l)))))) '(1))

; function that finds length of lists of size 1 without using define
((lambda (l)
   (cond
    ((null? l) 0)
    (else (+ 1
             ((lambda (l)
                (cond
                 ((null? l) 0)
                 (else (+ 1 (eternity (cdr l))))))
              (cdr l)))))) '(1))

; function that finds length of lists of size 2 using define
(define length1
  (lambda (l)
    (cond
     ((null? l) 0)
     (else (+ 1
              ((lambda (l)
                 (cond
                  ((null? l) 0)
                  (else (+ 1 (eternity (cdr l))))))
               (cdr l)))))))

(length1 '(1))

((lambda (l)
   (cond
    ((null? l) 0)
    (else
     (+ 1
        (length1 (cdr l)))))) '(1 2))

; function that finds length of lists of size 2 without using define
((lambda (l)
   (cond
    ((null? l) 0)
    (else
     (+ 1
        ((lambda (l)
          (cond
           ((null? l) 0)
           (else (+ 1
                    ((lambda (l)
                       (cond
                        ((null? l) 0)
                        (else (+ 1
                                 (eternity (cdr l))))))
                     (cdr l))))))
         (cdr l)))))) '(1 2))

; function that creates function length for lists of size 0
(
 ((lambda (length)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (+ 1
                (length (cdr l)))))))
  eternity)
 ())

; function that creates function length for lists of size 1
(
 ((lambda (f)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else
        (+ 1
           (f (cdr l)))))))
  ((lambda (g)
     (lambda (l)
       (cond
        ((null? l) 0)
        (else
         (+ 1
            (g (cdr l)))))))
   eternity))
 '(1))

; function that creates function length for lists of size 2
(
 ((lambda (length)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else
        (+ 1
           (length (cdr l)))))))
  ((lambda (length)
     (lambda (l)
       (cond
        ((null? l) 0)
        (else
         (+ 1
            (length (cdr l)))))))
  ((lambda (length)
     (lambda (l)
       (cond
        ((null? l) 0)
        (else
         (+ 1
            (length (cdr l)))))))
   eternity)))
 '(1 2))

; extracting function that makes length to make function length for lists of size 0
(
 ((lambda (mk-length)
    (mk-length eternity))
  (lambda (length)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (+ 1
                (length (cdr l))))))))
 ())

; make function length for lists of size 1
(
 ((lambda (mk-length)
    (mk-length 
     (mk-length eternity)))
  (lambda (length)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (+ 1
                (length (cdr l))))))))
 '(1))

; make function length for lists of size 3
(
 ((lambda (mk-length)
    (mk-length 
     (mk-length
      (mk-length
       (mk-length eternity)))))
  (lambda (length)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (+ 1
                (length (cdr l))))))))
 '(1 2 3))

; the function works until recursion reaches eternity. For finite recursion it doesn't matter what eternity is
; replacing eternity with mk-length to make function length for lists of size 0
(
 ((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (+ 1
                (mk-length (cdr l))))))))
 '())

; make function length for lists of size 1
(
 ((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (+ 1
                ((mk-length eternity) (cdr l))))))))
 '(1))

; Pass mk-length to itself for infinite recursion
(
 ((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (+ 1
                ((mk-length mk-length)
                 (cdr l))))))))
 '(1 2 3 4 5 6 7 8 9))

; Application of mk-length to itself is what makes infinite recursion or the definition of length possible. Extracting (mk-length mk-length) as length
(
 ((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    (lambda (l)
      ((lambda (length)
         (cond
          ((null? l) 0)
          (else (+ 1
                   (length
                    (cdr l))))))
       (mk-length mk-length)))))
 '(1 2 3 4 5 6 7 8 9))

; if f is a function of one argument x, (lambda (x) (f x)) is again a funciton of one argument x

(define square
  (lambda (x)
    (* x x)))

(square 5)

(lambda (x)
  (square x))

((lambda (x)
   (square x)) 5)

; Replacing (mk-length mk-length) with lambda form
(
 ((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (+ 1
                ((lambda (x)
                   ((mk-length mk-length) x))
                 (cdr l))))))))
 '(1 2 3 4 5 6 7 8 9))

; Extracting out (lambda (x) ((mk-length mk-length) x)) as length
(
 ((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    ((lambda (length)
       (lambda (l)
         (cond
          ((null? l) 0)
          (else (+ 1
                   (length (cdr l)))))))
     (lambda (x)
       ((mk-length mk-length) x)))))
 '(1 2 3 4 5 6 7 8 9))

; This gives the structure of the original length function
; Extracting the structure of the length function
(
 ((lambda (le)
    ((lambda (mk-length)
       (mk-length mk-length))
     (lambda (mk-length)
       (le (lambda (x)
             ((mk-length mk-length) x))))))
  (lambda (length)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (+ 1
                (length (cdr l))))))))
  '(1 2 3 4 5 6 7 8 9))

; Replacing mk-length with f
(
 ((lambda (le)
    ((lambda (f)
       (f f))
     (lambda (f)
       (le (lambda (x)
             ((f f) x))))))
  (lambda (length)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (+ 1
                (length (cdr l))))))))
 '(1 2 3 4 5 6 7 8 9))

; The function that makes length is called the Y-combinator
; Separating the function that looks like length from the function that makes length
(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

((Y
  (lambda (length)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (+ 1
                (length (cdr l))))))))
 '(1 2 3 4 5 6 7 8 9))

; Comparing with define method
(define length
  (lambda (l)
    (cond
     ((null? l) 0)
     (else (+ 1
              (length (cdr l)))))))

(length '(1 2 3 4 5 6 7 8 9))