緣起
第一次聽說Y組合子拉鹃，大概是在19年的時候。當時看到這么個東西的時候鲫忍，就覺得很漂亮毛俏。然后，也不知道薅掉多少根頭發(fā)饲窿，終于在最近頓悟了其中的關(guān)鍵步驟煌寇，遂把思路整理成文章記錄下來。
先簡單說一下Y組合子產(chǎn)生的背景吧逾雄。
上個世紀三十年代阀溶，丘奇發(fā)明了Lambda演算（它是后來很多函數(shù)式變成的理論基礎(chǔ)）腻脏。大概是因為信奉如無必要勿增實體，當年老爺子提出的理論里银锻，函數(shù)是單參的永品、也沒有名字的概念。
之后击纬，柯里先救了一次場鼎姐，證明多參函數(shù)可以用單參函數(shù)等價表示，這就是函數(shù)式編程里大名鼎鼎的柯里化更振。
但是沒有函數(shù)名炕桨，怎么實現(xiàn)遞歸呢？關(guān)鍵時刻肯腕，柯里大神再次救場献宫，證明了不需要名字，也能實現(xiàn)函數(shù)的遞歸实撒。
不過姊途，純數(shù)學的理論證明咱也不會啊，所以知态，下面就用Scheme語言（基于Lambda的一種Lisp方言）以工程的視角推導出一個Y組合子捷兰。
推導過程
(define fact
(lambda (n)
(if (< n 2) 1 (* n (fact (- n 1)))))
)
這是一個遞歸求階乘的函數(shù)。剛才說了负敏，Lambda演算不能存在函數(shù)名贡茅，也就是說不能用define定義fact。但是原在，這里其實有一個變通方案：不能定義函數(shù)名友扰，但是可以給變量命名，比如n庶柿。所以村怪，第一步，我們把fact作為變量傳進來浮庐。
(define some-name
(lambda (fact)
(lambda (n)
(if (< n 2) 1 (* n (fact (- n 1))))))
)
((some-name 'null) 1)
((some-name (some-name 'null)) 2)
((some-name (some-name (some-name 'null))) 3)
針對第一個式子甚负，其實fact傳入的是什么東西都無所謂，因為n = 1审残，所以不會走到(fact 0)梭域，否則fact帶入'null，會報錯
針對第二個式子搅轿，n = 2時病涨，帶入得到 (* 2 (...))，其中...的部分就是第一個式子的內(nèi)容璧坟，即((some-name 'null) 1)
針對第三個式子既穆，n = 3時赎懦，帶入得到 (* 3 (...))，其中...的部分就是第二個式子的內(nèi)容幻工，即((some-name (some-name 'null)) 2)
其實可以看出來励两，只要最后的(fact 0)不要真的執(zhí)行到，就可以算越來越大的n
但是囊颅，我們不想 n = 4式当悔，寫這么長的式子了，((some-name (some-name (some-name (some-name 'null)))) 4)
所以我們試著做以下這2個替換：
第一步：既然'null都可以讓程序跑起來踢代，那替換成some-name是不是也可以盲憎？
((some-name some-name) 1)
((some-name (some-name some-name)) 2)
((some-name (some-name (some-name some-name))) 3)
第二步：既然程序最后終止在(fact 0)，用some-name帶入fact后奸鬓，實際上是終止在(some-name 0)
那是不是把(fact 0)改寫成((fact fact) 0)焙畔，程序就不會終止了掸读？
(define some-name
(lambda (fact)
(lambda (n)
(if (< n 2) 1 (* n ((fact fact) (- n 1))))))
)
((some-name some-name) 1)
((some-name some-name) 2)
; = (* 2 ((some-name some-name) 1))
((some-name some-name) 3)
; = (* 3 ((some-name some-name) 2))
; = (* 3 (* 2 ((some-name some-name) 1)))
((some-name some-name) 4)
; = (* 4 ((some-name some-name) 3))
; = (* 4 (* 3 ((some-name some-name) 2)))
; = (* 4 (* 3 (* 2 ((some-name some-name) 1))))
(((lambda (g) (g g)) some-name) 4)
可以看到這時候串远，其實要不要some-name已經(jīng)沒有關(guān)系了，完全可以把some-name用它真正的定義塞進去
(
; 這其實是一個函數(shù)儿惫，接受一個參數(shù)n澡罚，計算n的階乘
(
(lambda (g) (g g))
; 這其實是剛才的some-name
(lambda (fact)
(lambda (n)
(if (< n 2) 1 (* n ((fact fact) (- n 1))))))
)
4)
上面的那個函數(shù)成為“窮人的Y組合子”，因為它指針對特定的遞歸函數(shù)生效肾请，在這個例子里是fact
我們希望把fact提出去留搔，讓這個函數(shù)更通用一些
首先把fact代換為f（這一步實際上只是為了好看）
(
; 這其實是一個函數(shù)，接受一個參數(shù)n铛铁，計算n的階乘
(
(lambda (g) (g g))
; 這其實是剛才的some-name
(lambda (f)
(lambda (n)
(if (< n 2) 1 (* n ((f f) (- n 1))))))
)
4)
接著我們把(f f)提出去
(
(
(lambda (g) (g g))
(lambda (f)
(
; 這是最初的階乘函數(shù)
(lambda (fact)
(lambda (n)
(if (< n 2) 1 (* n (fact (- n 1))))))
; 用lambda包一下隔显，本質(zhì)上就是剛才的 (f f)
; 這一步主要是因為Scheme是應(yīng)用序求值
; 因此，如果不用lambda讓它延遲求值的話饵逐，就會提前遞歸下去
(lambda (x) ((f f) x))
)
)
)
4)
再把fact相關(guān)的提出去
(define some-name
(lambda (fact)
(lambda (n)
(if (< n 2) 1 (* n (fact (- n 1))))))
)
(
(
(lambda (g) (g g))
(lambda (f) (some-name (lambda (x) ((f f) x))))
)
4)
(
(
; This is Y !!!
(lambda (fn)
(
(lambda (g) (g g))
(lambda (f) (fn (lambda (x) ((f f) x))))
)
)
some-name
)
4)
最終我們得到Y(jié)組合子
(define Y
(lambda (fn)
((lambda (g) (g g))
(lambda (f) (fn (lambda (x) ((f f) x)))))))
拿階乘函數(shù)先測試下
((Y some-name) 5)
試試斐波那契數(shù)列
(define meta-fib
(lambda (fib)
(lambda (n)
(if (< n 3) 1 (+ (fib (- n 1)) (fib (- n 2)))))))
((Y meta-fib) 10)
