本人博客地址：http://m.shnenglu.com/pwq1989/
昨天在知乎上看到一個評論提到了Haskell的YC實現，就去搜了一下，然后就看到了一個實現：
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寫法，就貼一個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
雖然看起來很長，但是容易理解的多，用
λ表達式寫出來就是（wiki）
λf. (λx. f (x x)) (λx. f (x x))
目的就是能做出 Y f = f (Y f) 這種效果，之所以這么寫，是為了不引入名字（引入了名字是惡!）
對于Haskell這種用HM類型系統的語言來說，最大的問題就是不能遞歸的定義類型，同樣是靜態類型檢查，比如C#，就可以不費力的用Func和delegate做出來，haskell 額，就得扭曲的利用newtype Mu a = Mu (Mu a -> a) 來繞過類型檢查（當然，這個在Haskell中是不可能構造出一個實際的值的）。
看下他是怎么做的，我們來把他展開一下：
原式子：y f = (\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)
帶進去：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)
這樣子，最后那個式子的f. 后面的那部分，提取 (\x -> f . (\(Mu g) -> g) x $ x) 這個公因式 就相當于是(\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)了（很像數學把，但也沒多大關系）
最后，就可以做出y f = f . (y f)了。
其實這個寫法最關鍵的是 newtype Mu a = Mu (Mu a -> a)的作用，他是如何繞過類型檢查，但是又不在運行期構造一個值（想構造也構造不出來）。
來看下他的類型推導過程，y的類型是y :: (a -> a) -> a，所以里面f就是 f :: a -> a，所以f . (\(Mu g) -> g) x $ x 這個式子可以推出里面的x是 x :: Mu a 然后(\(Mu g) -> g) x 取出里面的 a，這樣就成了
f
a $ Mu a，這時候Mu a = Mu (Mu a -> a) 遞歸定義的作用就發揮了，為了類型的推導，繼續將那個紅色的a 推導成 Mu a -> a，這樣 f (Mu a -> a) 會返回一個Mu a -> a，管他叫f'把，這樣 f' (Mu a) 就返回一個 a。有根據前面的(\h -> h $ Mu h) 繼續講上面提到的a變成 Mu a -> a。就是把Mu a 喂給了 (Mu a -> a)，最后還是返回一個a。
(>_< 其實上面這段是我編出來的，我編不下去了，我不知道ghc是怎么做這個事情的，等我有生之年看完slpj-book-1987再想想)我們來應用一下，返回一個階乘：
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
右席 閱讀(2290)
評論(5) 編輯 收藏 引用 所屬分類:
搬磚之路