ycombinator.rkt

#lang racket

;; factorial
(define (fact n)
  (if (= n 1) 1 (* n (fact (- n 1)))))


;; what if we couldnt use define or letrec and still had to define factorial
;; I'm using define to "wrap" the contents and prevent it from leaking, but 
;; the important part is I define fact-int and pass it to itself ... 
;; and internally I "expect" fact-int and do the same thing
(define (fact2 n)
  (let ([fact-int 
         (lambda (g n) 
           (if (= n 1) 1 (* n (g g (- n 1)))))])
       (fact-int fact-int n)))


;; here we curry the previous function
(define (fact3 n)
  (let ([fact-int 
         (lambda (g) 
           (lambda (n) (if (= n 1) 1 (* n ((g g) (- n 1))))))])
       ((fact-int fact-int) n)))

;; here we realise that fact-int does 2 things. factorial and passing fact-int to itself
;; so maybe we could store the intermedeate result in a let binding
(define (fact4 n)
  (let ([fact-int
         (lambda (g)
           (let ([h (lambda (n) ((g g) n))])
             (lambda (n) (if (= n 1) 1 (* n (h (- n 1)))))))])
    ((fact-int fact-int) n)))


;; here we recognise that let x be e1 in e2 is the same as lambda(x) e2 with e1 as
;; a parameter. We basically define a lambda and immedeately execute it.
(define (fact5 n)
  (let ([fact-int
         (lambda (g)
           ((lambda (h)
             (lambda (n) (if (= n 1) 1 (* n (h (- n 1))))))
             (lambda (n) ((g g) n))))])
    ((fact-int fact-int) n)))


;; now it's obvious that the "factorial" code is almost seperate, so we put it in a let
;; binding, the rest is just a "make recursive" function.
(define (fact6 n)
  (let ([fact-int
         (lambda (g)
           (let ([f (lambda (h) (lambda (n) (if (= n 1) 1 (* n (h (- n 1))))))])
           (f (lambda (n) ((g g) n)))))])
    ((fact-int fact-int) n)))

;; we use the same trick we used before. we convert a "let" into a lambda
(define (fact7 n)
  (let ([fact-int
         (lambda (g)
           ((lambda (f) (f (lambda (n) ((g g) n))))
           (lambda (h) (lambda (n) (if (= n 1) 1 (* n (h (- n 1))))))
           ))])
    ((fact-int fact-int) n)))

;; we realise that fact-int is not factorial, and the thing inside it is factorial
(define (fact8 n)
  (let ([recur-thingy
         (lambda (g)
           ((lambda (f) (f (lambda (n) ((g g) n))))
           (lambda (h) (lambda (n) (if (= n 1) 1 (* n (h (- n 1)))))) ;;actual fact
           ))])
    ((recur-thingy recur-thingy) n)))

;; lets lift the actual factorial out. We need a let* binding for this
(define (fact9 n)
  (let* ([fact-int (lambda (h) (lambda (n) (if (= n 1) 1 (* n (h (- n 1))))))]
         [recur-thingy
         (lambda (g)
           ((lambda (f) (f (lambda (n) ((g g) n))))
            fact-int
           ))])
    ((recur-thingy recur-thingy) n)))

;; since we lifted it out, we can actually pass it in as a parameter, now
;; the recursion thing is truly separated out.
(define (fact10 n)
  (let* ([fact-int (lambda (h) (lambda (n) (if (= n 1) 1 (* n (h (- n 1))))))]
         [recur-thingy
         (lambda (g)
           (lambda (f) (f (lambda (n) (((g g) f) n)))))])
    (((recur-thingy recur-thingy) fact-int) n)))


;; one more let binding. we dont care about recur-thingy. we care
;; about something we can pass fact-int into.
(define (fact11 n)
  (let* ([fact-int (lambda (h) (lambda (n) (if (= n 1) 1 (* n (h (- n 1))))))]
         [recur-thingy
         (lambda (g)
           (lambda (f) (f (lambda (n) (((g g) f) n)))))]
         [y (recur-thingy recur-thingy)])
    ((y fact-int) n)))

;; recognising that fact-int and y are truly independent, lets try to switch from
;; a let* binding to a let binding.
(define (fact12 n)
  (let ([fact-int (lambda (h) (lambda (n) (if (= n 1) 1 (* n (h (- n 1))))))]
        [y (let ([recur-thingy (lambda (g)
           (lambda (f) (f (lambda (n) (((g g) f) n)))))])
             (recur-thingy recur-thingy))])
    ((y fact-int) n)))

;; lets write out y
(define y-nonstandard (let ([recur-thingy (lambda (g)
           (lambda (f) (f (lambda (n) (((g g) f) n)))))])
  (recur-thingy recur-thingy)))

(define (fact13 n)
  ((y-nonstandard (lambda (f) (lambda (n) (if (= n 1) 1 (* n (f (- n 1))))))) n)) 

(define (fib13 n)
  ((y-nonstandard (lambda (f) 
            (lambda (n) (if (or (= n 1) (= n 0)) 1 (+ (f (- n 1)) (f (- n 2))))))) n))

;; let to lambda again
(define y ((lambda (g) (lambda (f) 
                         (f (lambda (n) (((g g) f) n)))))
           (lambda (g) (lambda (f) 
                         (f (lambda (n) (((g g) f) n)))))))

(define (fact14 n)
  ((y (lambda (f) (lambda (n) (if (= n 1) 1 (* n (f (- n 1))))))) n)) 

(define (fib14 n)
  ((y (lambda (f) 
            (lambda (n) (if (or (= n 1) (= n 0)) 1 (+ (f (- n 1)) (f (- n 2))))))) n))