• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 9,  comments - 19,  trackbacks - 0
            本人博客地址:http://m.shnenglu.com/pwq1989/ 

            昨天在知乎上看到一個(gè)評論提到了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
            雖然看起來很長,但是容易理解的多,用λ表達(dá)式寫出來就是(wiki
            λf. (λx. f (x x)) (λx. f (x x))
            目的就是能做出 Y f = f (Y f) 這種效果,之所以這么寫,是為了不引入名字(引入了名字是惡!)

            對于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 右席 閱讀(2293) 評論(5)  編輯 收藏 引用 所屬分類: 搬磚之路
            66精品综合久久久久久久| 久久人妻无码中文字幕| 91精品国产9l久久久久| 久久99国产精品一区二区| 久久久久国产亚洲AV麻豆| 一本色道久久88精品综合| 青青草国产精品久久| 一日本道伊人久久综合影| 国内精品久久久久影院一蜜桃| 狠狠色丁香婷婷综合久久来来去 | 成人久久精品一区二区三区| 99久久国产亚洲高清观看2024 | 午夜精品久久久久| 国产成人无码久久久精品一| 天天综合久久一二三区| 狠狠狠色丁香婷婷综合久久俺| 亚洲精品美女久久久久99小说| 精品国产91久久久久久久| 伊人久久大香线蕉亚洲| 国产精品永久久久久久久久久| 亚洲欧美日韩中文久久| 久久久久久精品免费免费自慰| 欧美久久综合性欧美| 久久成人影院精品777| 久久精品卫校国产小美女| 久久伊人亚洲AV无码网站| 青青热久久综合网伊人| 久久精品嫩草影院| 国产精品久久久福利| 色诱久久久久综合网ywww| 污污内射久久一区二区欧美日韩 | 日韩精品无码久久久久久| 久久99九九国产免费看小说| 欧美午夜A∨大片久久 | 国产精品日韩深夜福利久久| 日韩精品久久久久久| 狠狠久久综合伊人不卡| 亚洲午夜福利精品久久| 日韩人妻无码一区二区三区久久99 | 2021国产精品午夜久久| 久久无码国产专区精品|