問題
遞歸函數(shù)换帜，比如求階乘:
f = ->(n){ n==0? 1 : n*f[n-1] }
這里右邊引用了f，可以不引用自身實(shí)現(xiàn)遞歸么？
show me the money
答案如下:
# proc[x] === proc.call(x)
y = ->(f){->(x){x[x]}[->(x){f[->(g){x[x][g]}]}]}
_fact = ->(f){->(n){n==0?1:n*f[n-1]} }
fact = y[_fact]
puts (1..10).map(&fact)
分析
以上的關(guān)鍵在于神奇y函數(shù)，它是啥？
首先着茸，對于任何一個(gè)引用自己的遞歸函數(shù)r，我們都能寫出一個(gè)不引用自己的almost版本函數(shù)：
例如:
r = (*args) -> {...r...}
almost_r = (f)->(*args)->{...f...}
然后會(huì)發(fā)現(xiàn): almost_r(r) === r
r是almost_r的不動(dòng)點(diǎn)
而y函數(shù)叫做y combinator琐旁，它能夠?qū)τ谝粋€(gè)給定函數(shù)涮阔，求出它的不動(dòng)點(diǎn)。
因此y(almost_r) == r, 這里y和almost_r都不引用自身灰殴。
所以澎语，對于任何一個(gè)遞歸函數(shù)r，我們都能把它寫成y(almost_r)的形式验懊，一個(gè)沒有自我引用的形式擅羞。（y是已知的，almost_r是從r推導(dǎo)的义图，也是已知的）
Y combinator （Y不動(dòng)點(diǎn)組合子）
y函數(shù)是怎么得到的?
r:=real, a:=almost, p:=part
假設(shè):
r = (arg)->...r...
a = (f)->(arg)->...f...
p = (f)->(arg)->...ff...
y = (a)->r
(a(r) == r)
這里只有r引用了自己减俏，a和p都沒有引用自己
于是:
p == (f)->a(ff)
所以, pp = a(pp) = (arg)-> ...pp...
所以，pp == r
所以, y(a) = r = pp = ((x)->xx)p = ((x)->xx)((f)->a(ff))
y = (a)->((x)->xx)((f)->a(ff)) = (a)->((x)->xx)((f)->a((g)->(ff)g))
大概就是這樣吧碱工，哦吼吼吼娃承，請不要太在意細(xì)節(jié)...
