Y组合子
Y組合子
?
Y組合子的用處
作者：王霄池鏈接：https://www.zhihu.com/question/21099081/answer/18830200
來(lái)源：知乎
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
Y組合子的用處是使得 lambda 表達(dá)式不需要名字。
如你所說(shuō)，階乘函數(shù)可以這樣定義：let F = lambda n. n==0 ? 1 : n*(F n-1) 當(dāng)我們需要調(diào)用的時(shí)候，我們只需要這樣寫(xiě)就可以了：
F 4
但你有沒(méi)有想過(guò)，如果我們沒(méi)有 let 這個(gè)關(guān)鍵字怎么辦？沒(méi)有 let，就不能對(duì)一個(gè) lambda 表達(dá)式命名。實(shí)際上，在 lambda 演算里確實(shí)沒(méi)有 let，換句話說(shuō)，let 只是個(gè)語(yǔ)法糖，讓我們寫(xiě)起來(lái)更加舒適而已。沒(méi)有 let，并沒(méi)有對(duì)lambda表達(dá)式造成什么實(shí)質(zhì)性的傷害。
數(shù)學(xué)家們推崇：如無(wú)必要，勿增實(shí)體
是的。所以，你不能對(duì)任何lambda表達(dá)式命名。這就像你中了一個(gè)沉默魔法一樣。
我們先來(lái)看看如果沒(méi)有遞歸，無(wú)名 lambda 表達(dá)式是如何使用的。我們來(lái)寫(xiě)一個(gè)求平方的lambda：
lambda x. x * x 這個(gè)lambda是無(wú)名的。如果要調(diào)用，我們只能這么調(diào)用：
( lambda x. x * x ) 3
結(jié)果自然是返回 9 了。
看來(lái)沒(méi)有名字，lambda 世界還是可以正常運(yùn)轉(zhuǎn)的。且慢，我們不要忘記遞歸。遞歸函數(shù)，似乎真的是個(gè)問(wèn)題——如果沒(méi)有名字，自身如何調(diào)用自身？其實(shí)也不是啥大問(wèn)題。不過(guò)，要解決這個(gè)問(wèn)題，我們先假設(shè)我們可以使用名字。別擔(dān)心，這只是前進(jìn)途中的曲折。最后，我們會(huì)去掉名字的，大家先不要著急。
我們以階乘函數(shù)為例，先看看我們現(xiàn)階段的成果：let F = lambda n. n==0 ? 1 : n*(F n-1) 首先我們先設(shè)法消除掉 lambda 函數(shù)體中的函數(shù)名稱（對(duì)不起，一激動(dòng)就用上了函數(shù)這個(gè)說(shuō)法，如果你不知道什么叫函數(shù)，那么你就可以理解為函數(shù)就是 lambda，二者是等同的）。方法就是將函數(shù)作為參數(shù)傳進(jìn)去。
let F = lambda f. lambda n. n==0 ? 1 : n*((f f) (n-1)) 這個(gè)函數(shù)的接受一個(gè)參數(shù)，返回一個(gè)函數(shù)，這個(gè)返回的函數(shù)才是真正做計(jì)算的階乘函數(shù)。
調(diào)用此函數(shù)的方法如下：
F F 4
將會(huì)返回24。
接下來(lái)的一步將是至關(guān)重要的。我們現(xiàn)在就拋棄let關(guān)鍵字。我們將F的名字換成F的定義，于是調(diào)用階乘函數(shù)的的方式將變成如下的樣子：( 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
看到了沒(méi)，這里的所有 lambda 都沒(méi)有名字，不過(guò)，這絲毫沒(méi)有影響 lambda 表達(dá)式的威力。
如果你看到這里，就會(huì)發(fā)現(xiàn)，我們可以用類似的方法定義所有的遞歸函數(shù)，而用不著Y組合子。是的。你是對(duì)的。上面這種方法叫做窮人的Y組合子。但Y組合子的作用就是提供了一個(gè)通用的方法來(lái)定義遞歸函數(shù)。
讓我們來(lái)看一下Y的定義：lambda f. (lambda x. (f(x x)) lambda x. (f(x x)))
要講清楚Y的來(lái)龍去脈，可是非常難（大家可以去看我的博文重新發(fā)明 Y 組合子 Python 版）。事實(shí)上，連發(fā)現(xiàn)它的哈斯卡大神也感慨不已，覺(jué)得自己撿了個(gè)大便宜，還因此將Y紋在了自己的胳膊上。我現(xiàn)在就只講Y的用處了。
我們用Y來(lái)定義一下遞歸函數(shù)
let F = Y ( lambda f. lambda n. n==0 ? 1 : n*(f n-1) )
大家有沒(méi)有發(fā)現(xiàn)，定義變得比以前的特定方法更加優(yōu)美了。在之前的特定方法中 f 需要應(yīng)用于自身，但現(xiàn)在，f 是由 Y 提供的，是一個(gè)純階乘函數(shù)。
不只是定義更加優(yōu)雅，連調(diào)用也像有名字的lambda一樣優(yōu)美了。我們現(xiàn)在就優(yōu)雅的調(diào)用階乘函數(shù)：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
看，這里沒(méi)有任何名字，但我們定義并且調(diào)用了階乘函數(shù)。再次強(qiáng)調(diào)一下，階乘函數(shù)是個(gè)遞歸函數(shù)哦。
任何一階遞歸函數(shù)都可以用Y來(lái)定義，就像我們定義階乘函數(shù)那樣：Y (lambda f. < 真正的函數(shù)體，在內(nèi)部用f指代自身 >)
多說(shuō)一句，可以在 JavaScript 中實(shí)現(xiàn)Y算子，如果用上 CoffeScript 提供的語(yǔ)法糖，將非常優(yōu)雅（這里我原寫(xiě)錯(cuò)了，感謝 @Liu Martin )：
Y = (g) ->h = (f) ->g(n) -> f(f) nh h
Y算子真是人見(jiàn)人愛(ài)。但除了證明lambda只需要alpha/beta/eta三條規(guī)則而不需要命名之外，它主要用自身的優(yōu)美供大家感嘆。在真實(shí)的世界中，不論是數(shù)學(xué)家，還是函數(shù)式編程的 coder，都需要給事物命名。
====更新：函數(shù)不動(dòng)點(diǎn)在編程中的應(yīng)用 http://www.lfcs.inf.ed.ac.uk/reports/97/ECS-LFCS-97-375/ECS-LFCS-97-375.pdf
?
重新發(fā)明 Y 組合子 JavaScript(ES6) 版
關(guān)于Y組合子的來(lái)龍去脈，我讀過(guò)幾篇介紹的文章，相比之下，還是王垠大神的著作?最易懂。但他原來(lái)所有的語(yǔ)言是scheme，我寫(xiě)一個(gè) JS 版的，來(lái)幫助大家理解吧。
我們首先來(lái)看看如何實(shí)現(xiàn)遞歸。
lambda演算的語(yǔ)法非常簡(jiǎn)潔，一言以蔽之：
x | t t | λx.t其中xx表示變量，t?tt?t?表示調(diào)用，?λx.tλx.t?表示函數(shù)定義。
首先我們來(lái)定義一個(gè)階乘函數(shù)，然后調(diào)用它。
fact = n => n == 1 ? 1 : n * fact(n-1) fact(5)lambda演算中不可以這么簡(jiǎn)單的定義階乘函數(shù)，是因?yàn)樗鼪](méi)有?=?賦值符號(hào) 。
現(xiàn)在我們看到在lambda定義中，存在fact的名字，如果我們想要無(wú)名的調(diào)用它，是不行的。如下
(n => n == 1 ? 1 : n * fact(n-1))(5) # there is still `fact` name我們想要將名字消去，如何消去一個(gè)函數(shù)的名字呢？
首先，沒(méi)有名字是無(wú)法定義一個(gè)遞歸函數(shù)的。
那么，我們不禁要問(wèn)了，哪里可以對(duì)事物命名呢？
對(duì)了，將之變?yōu)閰?shù)，因?yàn)閰?shù)是可以隨意命名的。
fact = (f, n) => n == 1 ? 1 : n * f(f, n-1) fact(fact, 5)嗯，很好，看起來(lái)不錯(cuò)。不過(guò)，要記住在 lambda 演算里面，函數(shù)只能有一個(gè)參數(shù)，所以我們稍微做一下變化。
fact = f => n => n == 1 ? 1 : n * f(f)(n-1) fact(fact)(5)你可能會(huì)說(shuō)我在做無(wú)用功，別過(guò)早下結(jié)論，我們只需要將?fact?代入，就得到了完美的匿名函數(shù)調(diào)用。
(f => n => n == 1 ? 1 : n * f(f)(n-1)) (f => n => n == 1 ? 1 : n * f(f)(n-1)) (5)看，我們成功了，這一坨代碼，是完全可以運(yùn)行的哦。這個(gè)叫做?窮人的Y組合子。可以用，但是不通用，你要針對(duì)每個(gè)具體函數(shù)改造。
于是我們繼續(xù)改造。我們將把通用的模式提取出來(lái)，這個(gè)過(guò)程叫做?抽象。
首先我們看到了?f(f)?兩次，?fact(fact)?一次，這種pattern重復(fù)了3次，根據(jù) DRY 原則，我們可以這么做
w = f => f(f) w(fact) (5) # short version w (f => n => n == 1 ? 1 : n * f(f)(n-1)) (5) # longer version現(xiàn)在，我們就只有一個(gè)重復(fù)的模式了，那就是?f(f)?。但是因?yàn)樗诤瘮?shù)內(nèi)部（也就是在業(yè)務(wù)邏輯內(nèi)部），我們要先把它解耦出來(lái)。也就是 factor out。
我們從?f => n => n == 1 ? 1 : n * f(f)(n-1)?開(kāi)始
f =>n => n == 1 ? 1 : n * f(f)(n-1)我們令?g=f(f)?，然后 可以變成
f =>(g => n => n == 1 ? 1 : n * g(n-1)) ( f(f) )當(dāng)然，?f(f)?在call by value 時(shí)會(huì)導(dǎo)致棧溢出，所以我們就?ηη?化一下
f =>(g => n => n == 1 ? 1 : n * g(n-1)) ( v => f(f)(v) )我們看到了?g => n => n == 1 ? 1 : n * g(n-1)?這個(gè)就是我們夢(mèng)寐以求的階乘函數(shù)的定義啊。
我們將這個(gè)（階乘函數(shù)的定義）提取出來(lái)（再一次的factor out），將之命名為?fact0（更接近本質(zhì)的fact）。上面的可以改寫(xiě)成。
( fact0 => f =>fact0 ( v => f(f)(v) ) ) ( g => n => n == 1 ? 1 : n * g(n-1) )不要忘記最初的w，那么如下：
w((fact0 => f => fact0 ( v => f(f)(v) ))(g => n => n == 1 ? 1 : n * g(n-1)) )(5)很自然我們會(huì)再一次把階乘函數(shù)的定義factor out出來(lái)，當(dāng)然，fact0 => f => fact0 ( v=>f(f)(v) )中的fact0參數(shù)我們也會(huì)換成其他的名字，比如 s，而那個(gè)fact0的實(shí)參，那一大坨更加本質(zhì)的定義我們也會(huì)抽象成一個(gè)參數(shù)，h
(h =>w( (s => f => s ( v => f(f)(v) )) (h)) ) (g => n => n == 1 ? 1 : n * g(n-1)) (5)好，大功告成，上面的那個(gè)括號(hào)里面的就是Y了。我們將之單獨(dú)拿出來(lái)看。
(h =>w((s => f => s ( v => f(f)(v) )) (h)) )最中間一行的?h?可以apply一下，也就是化簡(jiǎn)：
(h =>w((f => h ( v => f(f)(v) ))) )當(dāng)然, w這個(gè)名字也可以去除
(h =>(f => h ( v => f(f)(v) ))(f => h ( v => f(f)(v) )) )這就是最后的結(jié)果了。
名調(diào)用中，可以這么寫(xiě)：
λf.(λu.u?u)(λx.f(x?x))λf.(λu.u?u)(λx.f(x?x))或者使用更經(jīng)典的形式
λf.(λx.f(x?x))(λx.f(x?x))?
?
淺談Y組合子
來(lái)源 http://jjyy.guru/y-combinator
?
這篇文章希望能夠通俗地講清楚Y組合子，如果對(duì)lambda演算感興趣的同學(xué)可以看看最后的相關(guān)資料
在lambda中，如果我們想要遞歸，以斐波那契數(shù)列為例，可以這樣：
let power = lambda n. IF_Else n==0 1 n*power(n-1)然而，在“純”lambda演算中，是沒(méi)有l(wèi)et關(guān)鍵字的，但我們可以暫時(shí)忘記這件事。我們需要換個(gè)方法進(jìn)行遞歸，如果直接的遞歸不可行，那么我們可以嘗試間接的。很容易能想到通過(guò)參數(shù)把自己傳給自己：
let P = lambda self n. If_Else n==0 1 n*self(self, n-1) P(P, 3)如果每次遞歸都要這么寫(xiě)，就顯得很不優(yōu)雅。我們要想一個(gè)辦法，能夠通用的把自己傳給自己。就像上面一樣。我們?cè)囍鴺?gòu)造一下，把斐波那契數(shù)列的邏輯替換為任意函數(shù)：
let gen = lambda self. AnyFunction(self(self)) gen(gen)嘗試寫(xiě)出斐波那契數(shù)列的AnyFunction實(shí)現(xiàn)：
let AnyFunction = lambda self n. If_Else n==0 1 n*self(n-1)經(jīng)過(guò)展開(kāi)之后，發(fā)現(xiàn)任何函數(shù)只要在AnyFunction那個(gè)位置，經(jīng)過(guò)上面的代碼之后，都能夠?qū)崿F(xiàn)遞歸。
其中g(shù)en(gen)展開(kāi)如下：
gen(gen) => AnyFunction(gen(gen))可能你會(huì)疑問(wèn)，gen(gen)為什么能夠表達(dá)自己呢？因?yàn)間en(gen)展開(kāi)為AnyFunction(gen(gen))，它能夠返回AnyFunction自身，這就得到自己了。并且這時(shí)會(huì)把這個(gè)gen(gen)再傳給AnyFunction。而gen(gen)不求值時(shí)是不展開(kāi)的，因此gen(gen)沒(méi)有被調(diào)用時(shí)，沒(méi)有任何作用，但是一旦AnyFunction內(nèi)部調(diào)用了傳進(jìn)來(lái)的gen(gen)，那么就進(jìn)行求值再次得到“自己”。通俗來(lái)講，與其說(shuō)gen(gen)是自身，還不如說(shuō)這是一個(gè)把能夠得到自己，并且把gen(gen)再次傳入的函數(shù)。
在理解這個(gè)機(jī)制之后，通用的遞歸函數(shù)已經(jīng)到手。封裝一下就輕而易舉了，這就是傳說(shuō)中的Y組合子：
let Y = lambda f. let gen = lambda self. f(self(self)) gen(gen)再把let去掉可得到Y(jié)的定義：
lambda f. (lambda x. (f(x x)) lambda x. (f(x x)))接下來(lái)可以試著使用一下：
( ( lambda f. (lambda x. (f(x x)) lambda x. (f(x x))) ) ( lambda f. lambda n. n==0 ? 1 : n*(f n-1) ) ) 4看，完美！證明了lambda只需要alpha/beta/eta三條規(guī)則而不需要命名。
相關(guān)資料，從易到難排序
- g9的lambda calculus系列?有很多l(xiāng)ambda的入門(mén)講解，幽默風(fēng)趣
- The Little Schemer?手把手學(xué)lambda
- The Seasoned Schemer?手把手2
- SICP?不用多說(shuō)，看書(shū)評(píng)
- MIT講SICP?MIT的課，值得一看
其他相關(guān)資料
- 康托爾、哥德?tīng)枴D靈——永恒的金色對(duì)角線?講了圖靈機(jī)的起源--對(duì)角線法
- 對(duì)角線方法之后的故事?關(guān)于對(duì)角線法的誤用
- 計(jì)算的本質(zhì)?手把手用Ruby講圖靈機(jī)，比較有趣，通俗易懂
- 圖靈的秘密?通俗易懂，引用圖靈論文，有理有據(jù)。圖靈機(jī)紙條部分比較枯燥
?
==================?End
?
總結(jié)
- 上一篇： 33、Map简介
- 下一篇： 使用Nexus配置Maven私有仓库