Y組合子要解決的問(wèn)題是如何用純正的lambda表達(dá)式實(shí)現(xiàn)遞歸
以階乘為例，可以采用下面的代碼以遞歸的形式表達(dá)：
f n = if n > 1 then n * f (n-1) else 1
要求一個(gè)自然數(shù)n的階乘只要調(diào)用f n即可
上述代碼包含了一個(gè)賦值語(yǔ)句喉悴，而純正的lambda表達(dá)式是沒(méi)有賦值語(yǔ)句的，那么用純正的lambda表達(dá)式能否實(shí)現(xiàn)遞歸呢疮绷？
可以猜測(cè)能求階乘的函數(shù)有很多個(gè),比如f n = foldl (*) [1..n]就是其中之一.于是我們將能求階乘的函數(shù)f當(dāng)成一個(gè)變量,這樣定義階乘就變成了求f的值
定義
g f = \n -> if n > 1 then n * f (n-1) else 1
先給出結(jié)論: f能求階乘的充分必要條件是g f == f(==表示等效,下同)
下面不嚴(yán)謹(jǐn)?shù)刈C明一下:
必要性
假設(shè)f能計(jì)算階乘,那么將g應(yīng)用于f可得一個(gè)新的函數(shù)g f, 即\n -> if n > 1 then n * f (n-1) else 1, ,f能計(jì)算階乘,由階乘的定義,g f必然也能計(jì)算階乘,也就是g f == f充分性
如果g f == f, 那么通過(guò)代換可以得到f == \n -> if n > 1 then n * f (n-1) else 1,這就是我們?cè)谏厦娼o出的階乘的遞歸定義形式,可以確定這樣的f是能計(jì)算出階乘的,通過(guò)數(shù)學(xué)歸納法可以證明
綜上, 可以知道g f == f是f能計(jì)算階乘的充分必要條件
那么問(wèn)題就變成了"求方程g f == f的解"
很顯然f應(yīng)該是一個(gè)關(guān)于g的函數(shù),那么Y組合子其實(shí)就是這個(gè)函數(shù): f == Y g
但是具體怎么求這個(gè)解就太難了,作為民科的我只能利用前輩們留下的結(jié)論自己慢慢湊
f應(yīng)該是gen gen這樣的形式,gen滿足
gen = \x -> g (x x)
于是gen gen = g gen gen
這樣就找到了g的不動(dòng)點(diǎn)
現(xiàn)在我們開始構(gòu)造Y組合子：
由上面的討論可以知道Y g == f == gen gen == g gen gen
則
Y g = g gen gen
即
Y g = gen gen
即
Y g = (\x -> g (x x)) (\x -> g (x x))
由此便得到了Y組合子
