posts - 9,  comments - 19,  trackbacks - 0
本人博客地址:http://www.cppblog.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 右席 阅读(2183) 评论(5)  编辑 收藏 引用 所属分类: 搬砖之路

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理