lang racket

;階乘函數(shù)最初版本

(define (fact-i1 n)
  (if(= n 0)
     1
     (* n (fact-i1 ( - n 1)))))

;調(diào)用很正常

;尾遞歸版本(但是這里不深入探討)
(define (fact-i2 n result)
   (if (= n 1)
       result
       (fact-i2 (- n 1) (* n result))))

;調(diào)用方式為(fact-i2 6 1)result必須傳入1

;傳入自己的版本
(define (fact self n)
  (if(= n 0)
     1
     (* n (self self (- n 1)))))

;調(diào)用方式為:(fact fact 5),但是此時(shí)函數(shù)中已經(jīng)沒(méi)有自己的名字了皿哨。

;將fact柯里化后
(define fact2
 (lambda (self)
   (lambda (n)
     (if (= n 0)
         1
         (* n ((self self) (- n 1)))))))

;柯里化后的調(diào)用約定是((f x) y)

;因此為了和函數(shù)頭調(diào)用相對(duì)應(yīng),遞歸的第二次調(diào)用應(yīng)該是(selfself)

;調(diào)用方式為((fact2 fact2)5)

;將fact2的參數(shù)互換位置后
(define fact3
 (lambda (n)
   (lambda (self)
     (if (= n 0)
         1
         (* n ((self (- n 1)) self))))))

;調(diào)用方式為:((fact3 5)fact3)

;非自身情況的調(diào)用1
(define fact4
 (lambda (n)
   (lambda (self)
     (if (= n 0)
         1
         (* n (self self (- n 1)))))))

;調(diào)用方式為:((fact4 6)fact)

;非自身情況的調(diào)用2
(define fact5
 (lambda (self)
   (lambda (n)
     (if (= n 0)
         1
         (* n (self (- n 1)))))))

;self n時(shí),((fact5 fact-i1) 5)

;n self時(shí),((fact5 5) fact-i1)

;超級(jí)版本
;實(shí)際上是fact2的展開(kāi),fact2要去掉fact2后的產(chǎn)物,是窮人版的Y組合子。
(define factorial
 ((lambda (self1)
    (lambda (n)
      (if (= n 0)
          1
          (* n ((self1 self1)(- n 1))))))
  (lambda (self2)
    (lambda (n)
      (if (= n 0)
          1
          (* n ((self2 self2)(- n 1))))))))

;調(diào)用方式:(factorial 6)

;Y 組合子
(define Y1
 (lambda (F)
   ((lambda (self)
      (F (lambda (x) ((self self) x))))
    (lambda (self)
      (F (lambda (x) ((self self) x)))))))
(define Y2
 (lambda (F)
   ((lambda (x) (x x))
    (lambda (self)
      (F (lambda (x) ((self self) x)))))))

;Y2就是Y1的展開(kāi)

(define (Fib-maker f)
 (lambda (n)
   (if (<= n 1)
       1
       (+ (f (- n 1))
          (f (- n 2))))))
(define (A f)
 (lambda (x)
   (lambda (y)
     (cond [(= y 0) 0]
           [(= x 0) (* 2 y)]
           [(= y 1) 2]
           [else ((f (- x 1)) ((f x) (- y 1)))]))))
;A需要這樣寫(xiě)

(define fib (Y1 Fib-maker))
(fib 5)
(define aa (Y2 A))
((aa 3) 2)

;尾遞歸版本的
(define fact
  (lambda (f)
    (lambda (n)
      (lambda ([result 1])
        (if (= n 1)
            result
            (((f f) (- n 1)) (* n result)))))))
(((fact fact) 6) 1)

(define fac
  ((lambda (f)
     (lambda (n [result 1])
         (if (= n 1)
             result
             ((f f) (- n 1) (* n result)))))
   (lambda (f)
     (lambda (n [result 1])
         (if (= n 1)
             result
             ((f f) (- n 1) (* n result)))))))

(fac 6)