因为有人提到，所以复习了一下.. 1. Y combinator in Haskell Y combinator 在 untyped lambda calculus 中是 \f -> (\x -> f (x x)) (\x -> f (x x)) 试着写成 Haskell: y :: (a -> a) -> a y f = (\x -> f (x x)) (\x -> f (x x)) f 的型别是 a -> a, 而 y 取 f 的 fixed-point， 所以 y 的型别是 (a -> a) -> a. 但是这个型别一看就有问题：把 type 看成逻辑的话， 这个 type 若有证明就会有 inconsistency. 果然， Haskell 不让这个程式 typecheck: Occurs check: cannot construct the infinite type: t = t -> a Probable cause: `x' is applied to too many arguments In the first argument of `f', namely `(x x)' In the expression: f (x x) 操作上的理由是：在 (x x) 之中，x 的型别又是 t -> a, 又是 t, 而 t = t -> a 递回定义。 解决方法也很简单，就头痛医头脚痛医脚，做一个 t 与 t -> a 同构的递回型别罗。 data Fix a = Rec (Fix a -> a) -- Fix a 和 Fix a -> a 同构 有了 Fix 就可以写 Y combinator 了。 y :: (a -> a) -> a y f = (\(Rec x) -> f (x (Rec x))) (Rec (\(Rec x) -> f (x (Rec x)))) 和前一个版本比较，这里多了很多 Rec，其实是在告诉 typechecker 何时要把 Fix 展开。 2. 用 Y 定义递回函数 假设 Haskell 不允许递回定义（正确地说，允许递回资料型别，但 不允许递回的 term），那要怎麽写递回函数呢？ 递回版本的阶层是这麽写的: fact :: Int -> Int fact 0 = 1 fact (n+1) = (n+1) * fact n 没有递回的话，就用 Y 取 fixed-point 罗。首先定义这个 factF: factF :: (Int -> Int) -> (Int -> Int) factF g 0 = 1 factF g (n+1) = (n+1) * g n 和 fact 的差别是 factF 只做 fact 的第一层。注意 factF 的型别。 然後 fact 就是 factF 的 fixed-point: fact :: Int -> Int fact = y factF 由此可知一个语言如果有提供 closure, 就可以不用把递回当作 primitive. 3. Mutual Recursion Mutual recursion 其实也是一样的，只是同时定义一组东西。 比如说一般 even 和 odd 可以这样定: even, odd :: Int -> Bool even 0 = True even (n+1) = odd n odd 0 = False odd (n+1) = even n 如果没有递回，就定义一个从「一对」函数到一对函数的函数: evenOddF :: (Int -> Bool, Int -> Bool) -> (Int -> Bool, Int -> Bool) evenOddF (ev, od) = (\n -> if n == 0 then True else od (n-1), \n -> if n == 0 then False else ev (n-1)) evenOddF 拿一对函数 (ev,od)，产生一对函数，各自只做 even 和 odd 的第一层。本来该是递回的地方分别呼叫 od 和 ev. （如果该语言没有 pair, 就用 lambda 来模拟。） 然後我们也用 Y 取 evenOddF 的 fixed-point: evenOdd :: (Int -> Bool, Int -> Bool) evenOdd = y evenOddF even 就是第一个，odd 就是第二个: even = fst evenOdd odd = snd evenOdd 只是还有一点小问题：在 Haskell 中 y evenOddF 不会终止。 简单的解决方法是把 evenOddF (ev, od) = ... od .. ev ... 改成 evenOddF evod = ... snd evod ... fst evod ... 看起来比较漂亮，其实一样的方法是用 lazy pattern: evenOddF ~(ev, od) = ... od .. ev ... 这样就可以罗！ *Main> even 10 True *Main> odd 10 False --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 123.192.160.134