本人博客地址：http://m.shnenglu.com/pwq1989/ 

昨天在知乎上看到一個(gè)評(píng)論提到了Haskell的YC實(shí)現(xiàn)，就去搜了一下，然后就看到了一個(gè)實(shí)現(xiàn)：

嗯，真是別扭

反觀一下其他語(yǔ)言的YC寫法，就貼一個(gè)lua的把
雖然看起來(lái)很長(zhǎng)，但是容易理解的多，用λ表達(dá)式寫出來(lái)就是（wiki）
λf. (λx. f (x x)) (λx. f (x x))
目的就是能做出 Y f = f (Y f) 這種效果，之所以這么寫，是為了不引入名字（引入了名字是惡!）

對(duì)于Haskell這種用HM類型系統(tǒng)的語(yǔ)言來(lái)說(shuō)，最大的問(wèn)題就是不能遞歸的定義類型，同樣是靜態(tài)類型檢查，比如C#，就可以不費(fèi)力的用Func和delegate做出來(lái)，haskell 額，就得扭曲的利用newtype Mu a = Mu (Mu a -> a) 來(lái)繞過(guò)類型檢查（當(dāng)然，這個(gè)在Haskell中是不可能構(gòu)造出一個(gè)實(shí)際的值的）。

看下他是怎么做的，我們來(lái)把他展開一下：
原式子：y f = (\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)
帶進(jìn)去：y f = (\x -> f . (\(Mu g) -> g) x $ x) $ Mu (\x -> f . (\(Mu g) -> g) x $ x)
再來(lái)一遍：y f = f . (\x -> f . (\(Mu g) -> g) x $ x) $ Mu (\x -> f . (\(Mu g) -> g) x $ x)

這樣子，最后那個(gè)式子的f. 后面的那部分，提取 (\x -> f . (\(Mu g) -> g) x $ x) 這個(gè)公因式 就相當(dāng)于是(\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)了（很像數(shù)學(xué)把，但也沒(méi)多大關(guān)系）
最后，就可以做出y f = f . (y f)了。

其實(shí)這個(gè)寫法最關(guān)鍵的是 newtype Mu a = Mu (Mu a -> a)的作用，他是如何繞過(guò)類型檢查，但是又不在運(yùn)行期構(gòu)造一個(gè)值（想構(gòu)造也構(gòu)造不出來(lái)）。

來(lái)看下他的類型推導(dǎo)過(guò)程，y的類型是y :: (a -> a) -> a，所以里面f就是 f :: a -> a，所以f . (\(Mu g) -> g) x $ x 這個(gè)式子可以推出里面的x是 x :: Mu a 然后(\(Mu g) -> g) x 取出里面的 a，這樣就成了
f a $ Mu a，這時(shí)候Mu a = Mu (Mu a -> a) 遞歸定義的作用就發(fā)揮了，為了類型的推導(dǎo)，繼續(xù)將那個(gè)紅色的a 推導(dǎo)成 Mu a -> a，這樣 f (Mu a -> a) 會(huì)返回一個(gè)Mu a -> a，管他叫f'把，這樣 f' (Mu a) 就返回一個(gè) a。有根據(jù)前面的(\h -> h $ Mu h) 繼續(xù)講上面提到的a變成 Mu a -> a。就是把Mu a 喂給了 (Mu a -> a)，最后還是返回一個(gè)a。
(>_< 其實(shí)上面這段是我編出來(lái)的，我編不下去了，我不知道ghc是怎么做這個(gè)事情的，等我有生之年看完slpj-book-1987再想想)

我們來(lái)應(yīng)用一下，返回一個(gè)階乘：