寫在開始
不得不說，當(dāng)我開始學(xué)習(xí)函數(shù)式編程的時候丹弱，我并沒有被匿名函數(shù)感到害怕氮帐，理解它的基本概念是極其容易的。但是當(dāng)你試圖去將你日常所書寫的指令式的代碼轉(zhuǎn)換成函數(shù)式扎阶，特別是純函數(shù)式的時候事富，你會感到這是不可能的。它和你之前的編程思想是完全脫離的乘陪。
所以當(dāng)我第一次見到 Y-Combinator（Y 組合子）的時候统台，我的感覺是懵逼的，這是什么玩意啡邑。然而當(dāng)我一步一步贱勃，了解這個東西是什么，它是怎么工作的之后谤逼，我對函數(shù)式編程的認(rèn)識有了很大的進(jìn)步贵扰。
即使是 C++ 這樣的語言，也在 C++11 標(biāo)準(zhǔn)中引入了匿名函數(shù)流部，使得你有機(jī)會在 C++ 中使用函數(shù)式編程的特性戚绕。在編程中，如果能適當(dāng)?shù)厥褂煤瘮?shù)式語法進(jìn)行編程枝冀，將非常有助于你寫出一些更好理解舞丛、更簡單的代碼耘子。
而在了解一些基本概念之后，了解一下 Y-Combinator 是一個極好的選擇球切，這個東西證明了函數(shù)式編程對遞歸的語義理解谷誓，證明了其在遞歸上和指令式編程的等價之處。你可以通過觀察等價的這兩者的不同的實(shí)現(xiàn)方式吨凑，來加深對這兩者思想的認(rèn)識捍歪。
與指令式編程的根本區(qū)別
大家看下面一段 C 代碼
for (int i = 0; i < 100; i++){
puts("Hello World");
}
顯然這是一個非常常見的循環(huán)。然而這樣的循環(huán)顯然已經(jīng)被抽象過了鸵钝，我們也許可以用一個更原始的方法來實(shí)現(xiàn)糙臼。且讓我引入一個 C 開發(fā)中應(yīng)盡量避免的語句 goto 來解釋。
int i = 0;
loop:
if (i >= 100) goto next;
puts("Hello World");
i++;
goto loop;
next:
這兩段代碼除了變量 i 的作用域有所區(qū)別以外幾乎是等價的恩商。相對的弓摘，第二段代碼非常接近于編譯到匯編時的指令，幾乎是一一映射的痕届。然而你可以發(fā)現(xiàn)韧献，我們的循環(huán)都是依賴于跳轉(zhuǎn)代碼行數(shù)的，不得不說這種寫法非常不函數(shù)式研叫。
第一個函數(shù)
我們可以用一個遞歸來把這個循環(huán)實(shí)現(xiàn)地更像一個函數(shù)：
int loop(int n){
if (n == 0) return 0;
puts("Hello World");
return loop(n - 1);
}
loop(100);
雖然這個函數(shù)是倒過來循環(huán)的锤窑，但我們大可忽略這些細(xì)節(jié)，畢竟要做修改也是相對容易的嚷炉。我們通過一個函數(shù)遞歸的方式來實(shí)現(xiàn)了一個循環(huán)渊啰。需要特別注意的是，如果根據(jù)遞歸的定義申屹，那么這個循環(huán)一旦大起來在今天我們的計(jì)算機(jī)的計(jì)算模型（而不是 Lisp Machine）上是會爆棧的绘证，但好在由于是個尾遞歸，通常是會直接被編譯器優(yōu)化成一個循環(huán)的哗讥。這確保了即使你寫的是函數(shù)式代碼嚷那，也可以最終編譯成適合 CPU 運(yùn)算的形式而不太影響性能。
不過遞歸有一個問題杆煞，我們必須知道函數(shù)的名稱才能這么做魏宽，在真正的 Lambda 運(yùn)算模型上，函數(shù)是匿名的决乎，也就是沒有名字队询，這樣你最后根本就無處調(diào)用你函數(shù)自己。因?yàn)槟銦o法寫出下面的代碼（Ruby）：
lambda { |n|
return if n == 0
puts "Hello World"
what_the_f**k_my_function_name_is(n-1)
}
魔法少女 Lambda 醬
下面我們演示一種黑魔法构诚，來使得你沒有辦法得到自己函數(shù)名時實(shí)現(xiàn)遞歸蚌斩。簡單來說就是把「函數(shù)」當(dāng)成一個「參數(shù)」傳輸。
loop = lambda {|f, n|
return if n == 0
puts "Hello World"
f.call(n-1)
}
loop.call(loop, 100);
我們把函數(shù)本身作為一個參數(shù)傳了進(jìn)去范嘱，達(dá)到了我們的想法送膳。不過這里我們還不是一個完全的匿名函數(shù)员魏，而是通過給匿名函數(shù)起了一個名字 loop，在外面調(diào)用了一下肠缨。不過事到如今逆趋，去掉這個 loop 已經(jīng)很容易了盏阶。由于第一條的匿名函數(shù)定義中沒有任何地方用到 loop 只在第二條指令中用到晒奕。我們只要將第二條指令中的所有 loop 都代換掉就行。我們就能得到下面的代碼：
lambda {|f, n|
return if n == 0
puts "Hello World"
f.call(n-1)
}.call(lambda{|f, n|
return if n == 0
puts "Hello World"
f.call(n-1)
}, 100)
柯里化名斟，最后一步
Amazing脑慧！我們通過一個匿名函數(shù)的調(diào)用成功實(shí)現(xiàn)了一個 100 的循環(huán)。我們現(xiàn)在距離 Haskell Brooks Curry 先生當(dāng)年推出 Y 組合子只差一步砰盐，那就是將我們做的事情「Currying」（柯里化）闷袒。所謂 Currying 就是使用一個高階函數(shù)，將一個函數(shù)的多個參數(shù)精簡成一個岩梳。我們看到我們現(xiàn)在的匿名函數(shù)還有 f 和 n 兩個參數(shù)囊骤，我們打算拿掉它。雖然其實(shí)并不是真正意義上的拿掉冀值∫参铮柯里化，只不過把一個形如 f(x, y) 的函數(shù)寫成了 f(x)(y)列疗，也就是 f(x) 的返回是一個匿名函數(shù)滑蚯，而這個匿名函數(shù)再以 y 為參數(shù)執(zhí)行一次。這么搞一下抵栈，我們就得到了：
lambda {|p|
return lambda { |f|
return f.call(f);
}.call(lambda {|f|
return p.call(lambda {|x|
return f.call(f).call(x)
})
})
}.call(lambda {|f|
return lambda {|i|
return if i == 0;
f.call(i-1)
}
}).call(100)
由于柯里化后匿名函數(shù)和調(diào)用的參數(shù)都單一了告材，我們因此可以保證我們能將任意一個遞歸都表達(dá)成一個匿名函數(shù)的形式。按照 Lambda 演算的形式化表達(dá) Y := λf.(λx.(f (x x)) λx.(f (x x))) 古劲。你只要將自己要遞歸的函數(shù)替換掉里面 f 的位置斥赋，并最后執(zhí)行一下這個匿名函數(shù)就成啦~
折騰半天干什么
你肯定想問，我們把一個循環(huán)寫成這么復(fù)雜是為了什么产艾。事實(shí)上我想展示的不是循環(huán)灿渴，而是遞歸。遞歸在圖靈模型（我們通常 CPU 的計(jì)算模型）和丘奇模型（Lambda 演算）上都不是那么地原生的實(shí)現(xiàn)胰舆。
在圖靈模型上地最終形式是每次遞歸骚露，追加進(jìn)內(nèi)存中，并重新 goto 回函數(shù)開始缚窿，在退出時棘幸，再一步步內(nèi)存推出來，并將遞歸的剩余部分執(zhí)行完倦零。
而在 Lambda 演算中误续，最終表達(dá)為一個?邏輯系統(tǒng)構(gòu)成的嚴(yán)格的數(shù)學(xué)函數(shù)模型的執(zhí)行吨悍。
這兩者便是具體化和形式化的極限，充分表現(xiàn)了兩種模型的特點(diǎn)蹋嵌。從根本加深了對兩種模型差異的認(rèn)知育瓜，從而讓我們在兩種模型上都能通過正確的編程思想來寫代碼，以把代碼寫得更好栽烂。
當(dāng)然也是有一些實(shí)際意義的躏仇，比如在變量作用域嚴(yán)格的語言中，且又必須使用匿名函數(shù)的形式來書寫你所需要的東西的時候腺办，而你正好又需要遞歸才能達(dá)到你的要求焰手，那么使用 Y-Combinator 是一個可選的方法。然而通常怀喉，出現(xiàn)這種情況大多是你寫了錯誤的思想的代碼所導(dǎo)致的书妻，實(shí)際編程中幾乎遇不到這種情況，畢竟將更抽象更容易理解的函數(shù)式編程寫成這么一坨一眼看不懂的代碼是很失敗的躬拢。
