聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

Haskell扭曲的Y-Combinator

2014-02-27 05:25 浏览: 1869134 次 我要评论(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


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复