本人博客地址：http://m.shnenglu.com/pwq1989/
昨天在知乎上看到一個(gè)評(píng)論提到了Haskell的YC實(shí)現(xiàn)，就去搜了一下，然后就看到了一個(gè)實(shí)現(xiàn)：
1 newtype Mu a = Mu (Mu a -> a)
2
3 y :: (a -> a) -> a
4 y f = (\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)
嗯，真是別扭
反觀一下其他語言的YC寫法，就貼一個(gè)lua的把
1 Y =
function (f)
2 return function(
)
3 return (
function(x)
return x(x) end)
(
function(x)
return f(
function(y)
return x(x)(y) end) end)(
)
4 end
5 end
雖然看起來很長(zhǎng)，但是容易理解的多，用
λ表達(dá)式寫出來就是（wiki）
λf. (λx. f (x x)) (λx. f (x x))
目的就是能做出 Y f = f (Y f) 這種效果，之所以這么寫，是為了不引入名字（引入了名字是惡!）
對(duì)于Haskell這種用HM類型系統(tǒng)的語言來說，最大的問題就是不能遞歸的定義類型，同樣是靜態(tài)類型檢查，比如C#，就可以不費(fèi)力的用Func和delegate做出來，haskell 額，就得扭曲的利用newtype Mu a = Mu (Mu a -> a) 來繞過類型檢查（當(dāng)然，這個(gè)在Haskell中是不可能構(gòu)造出一個(gè)實(shí)際的值的）。
看下他是怎么做的，我們來把他展開一下：
原式子：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)
再來一遍：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é)把，但也沒多大關(guān)系）
最后，就可以做出y f = f . (y f)了。
其實(shí)這個(gè)寫法最關(guān)鍵的是 newtype Mu a = Mu (Mu a -> a)的作用，他是如何繞過類型檢查，但是又不在運(yùn)行期構(gòu)造一個(gè)值（想構(gòu)造也構(gòu)造不出來）。
來看下他的類型推導(dǎo)過程，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í)上面這段是我編出來的，我編不下去了，我不知道ghc是怎么做這個(gè)事情的，等我有生之年看完slpj-book-1987再想想)我們來應(yīng)用一下，返回一個(gè)階乘：
y (\f n -> if n <= 1 then 1 else n * f (n - 1)) 5。
不難看出，最終y的類型被特化成了 ((Int -> Int) -> (Int -> Int)) -> (Int -> Int)
posted on 2014-02-27 00:25
右席 閱讀(2309)
評(píng)論(5) 編輯 收藏 引用 所屬分類:
搬磚之路