本人博客地址: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
右席 阅读(2240)
评论(5) 编辑 收藏 引用 所属分类:
搬砖之路