Y組合子要解決的問題是如何用純正的lambda表達式實現(xiàn)遞歸
以階乘為例，可以采用下面的代碼以遞歸的形式表達：

f n = if n > 1 then n * f (n-1) else 1

要求一個自然數(shù)n的階乘只要調(diào)用f n即可
上述代碼包含了一個賦值語句，而純正的lambda表達式是沒有賦值語句的，那么用純正的lambda表達式能否實現(xiàn)遞歸呢？

可以猜測能求階乘的函數(shù)有很多個,比如f n = foldl (*) [1..n]就是其中之一.于是我們將能求階乘的函數(shù)f當成一個變量,這樣定義階乘就變成了求f的值

定義

g f = \n -> if n > 1 then n * f (n-1) else 1

先給出結(jié)論: f能求階乘的充分必要條件是g f == f(==表示等效,下同)

下面不嚴謹?shù)刈C明一下:

• 必要性
  假設(shè)f能計算階乘,那么將g應(yīng)用于f可得一個新的函數(shù)g f, 即\n -> if n > 1 then n * f (n-1) else 1, ,f能計算階乘,由階乘的定義, g f必然也能計算階乘,也就是g f == f

• 充分性
  如果g f == f, 那么通過代換可以得到f == \n -> if n > 1 then n * f (n-1) else 1,這就是我們在上面給出的階乘的遞歸定義形式,可以確定這樣的f是能計算出階乘的,通過數(shù)學歸納法可以證明

綜上, 可以知道g f == f是f能計算階乘的充分必要條件

那么問題就變成了"求方程g f == f的解"

很顯然f應(yīng)該是一個關(guān)于g的函數(shù),那么Y組合子其實就是這個函數(shù): f == Y g

但是具體怎么求這個解就太難了,作為民科的我只能利用前輩們留下的結(jié)論自己慢慢湊

f應(yīng)該是gen gen這樣的形式,gen滿足

gen = \x -> g (x x)

于是gen gen = g gen gen

這樣就找到了g的不動點

現(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組合子