Y組合子的用處是使得 lambda 運算式 不需要名字 。
如你所說,階乘函式可以這樣定義:
let F = lambda n. n==0 ? 1 : n*(F n-1)
當我們需要呼叫的時候,我們只需要這樣寫就可以了:
F 4
但你有沒有想過,如果我們沒有 let 這個關鍵字怎麽辦?沒有 let,就不能對一個 lambda 運算式命名。實際上, 在 lambda 演算裏確實沒有 let ,換句話說,let 只是個語法糖,讓我們寫起來更加舒適而已。沒有 let,並沒有對lambda運算式造成什麽實質性的傷害。
數學家們推崇:
如無必要,勿增實體是的。所以,你不能對任何lambda運算式命名。這就像你中了一個沈默魔法一樣。
我們先來看看如果沒有遞迴,無名 lambda 運算式是如何使用的。
我們來寫一個求平方的lambda:
lambda x. x * x
這個lambda是無名的。如果要呼叫,我們只能這麽呼叫:
( lambda x. x * x ) 3
結果自然是返回 9 了。
看來沒有名字,lambda 世界還是可以正常運轉的。且慢,我們不要忘記遞迴。遞迴函式,似乎真的是個問題——如果沒有名字,自身如何呼叫自身?其實也不是啥大問題。不過,要解決這個問題,我們先假設我們可以使用名字。別擔心,這只是前進途中的曲折。最後,我們會去掉名字的,大家先不要著急。
我們以階乘函式為例,先看看我們現階段的成果:
let F = lambda n. n==0 ? 1 : n*(F n-1)
首先我們先設法消除掉 lambda 函式體中的函式名稱(對不起,一激動就用上了函式這個說法,如果你不知道什麽叫函式,那麽你就可以理解為函式就是 lambda,二者是等同的)。方法就是將函式作為參數傳進去。
let F = lambda f. lambda n. n==0 ? 1 : n*((f f) (n-1))
這個函式的接受一個參數,返回一個函式,這個返回的函式才是真正做計算的階乘函式。
呼叫此函式的方法如下:
F F 4
將會返回24。
接下來的一步將是至關重要的。我們現在就拋棄let關鍵字。我們將F的名字換成F的定義,於是呼叫階乘函式的的方式將變成如下的樣子:
( lambda f. lambda n. n==0 ? 1 : n*((f f) (n-1)) ) ( lambda f. lambda n. n==0 ? 1 : n*((f f) (n-1)) ) 4
看到了沒,這裏的所有 lambda 都沒有名字,不過,這絲毫沒有影響 lambda 運算式的威力。
如果你看到這裏,就會發現,我們可以用類似的方法定義所有的遞迴函式,而用不著Y組合子。是的。你是對的。上面這種方法叫做 窮人的Y組合子 。但Y組合子的作用就是提供了一個通用的方法來定義遞迴函式。
讓我們來看一下Y的定義:
lambda f. (lambda x. (f(x x)) lambda x. (f(x x)))
要講清楚Y的來龍去脈,可是非常難(大家可以去看我的博文
重新發明 Y 組合子 Python 版)。事實上,連發現它的哈斯卡大神也感慨不已,覺得自己撿了個大便宜,還因此將Y紋在了自己的胳膊上。我現在就只講Y的用處了。
我們用Y來定義一下遞迴函式
let F = Y ( lambda f. lambda n. n==0 ? 1 : n*(f n-1) )
大家有沒有發現,定義變得比以前的特定方法更加優美了。在之前的特定方法中 f 需要套用於自身,但現在,f 是由 Y 提供的,是一個純階乘函式。
不只是定義更加優雅,連呼叫也像有名字的lambda一樣優美了。我們現在就優雅的呼叫階乘函式:
F 4
而去掉F的名字,我們有:
( Y ( lambda f. lambda n. n==0 ? 1 : n*(f n-1) ) ) 4
再去掉Y的名字:
( ( lambda f. (lambda x. (f(x x)) lambda x. (f(x x))) )
( lambda f. lambda n. n==0 ? 1 : n*(f n-1) )
) 4
看,這裏沒有任何名字,但我們定義並且呼叫了階乘函式。再次強調一下,階乘函式是個遞迴函式哦。
任何一階遞迴函式都可以用Y來定義,就像我們定義階乘函式那樣:
Y (lambda f. < 真正的函式體,在內部用f指代自身 >)
多說一句,可以在 JavaScript 中實作Y算子,如果用上 CoffeScript 提供的語法糖,將非常優雅(這裏我原寫錯了,感謝
@Liu Martin):
Y = (g) ->
h = (f) ->
g(n) -> f(f) n
h h
Y算子真是人見人愛。但除了證明lambda只需要alpha/beta/eta三條規則而不需要命名之外,它主要用自身的優美供大家感嘆。在真實的世界中,不論是數學家,還是函數語言程式設計的 coder,都需要給事物命名。
====
更新:函式不動點在編程中的套用
http://www. lfcs.inf.ed.ac.uk/repor ts/97/ECS-LFCS-97-375/ECS-LFCS-97-375.pdf