main = do n<-getLine print (fib (read n::Int))
复制代码
首先让我实现一个用简单的条件守卫和递归来实现的斐波那契数
fib n | n <= 2 = 1 | otherwise = fib (n-1) + fib (n-2)
复制代码
n<=2 的条件定义了递归基，余下的情况运行递归步。
很好，最重要的工作已经完成了一大半了！不过我想稍作修改，把 fib 改成顺推如何？不，这样做并不是故意找茬。众所周知，现在的写法性能像是一坨屎。虽然不应该苛责性能，但至少应该改成顺推法来稍微减轻一点栈空间的压力。
fib n = fibLoop n 0 1fibLoop n a b | n <= 1 = b | otherwise = fibLoop (n-1) b (a+b)
复制代码
现在的版本已经非常棒了，fibLoop 成功的实现了尾调用优化，性能和可读性都还不错。但是何不发扬一下风格？我是说，既然决定用 haskell 写，那么为什么不尝试一下 lambda 呢？写 lambda 可是 haskell 不得不品鉴的一环。
fib = \n -> fibLoop n 0 1fibLoop = \n a b -> if n <= 1 then b else fibLoop (n-1) b (a+b)
复制代码
没错，这样写确实 lambda 了，但从这段代码里能够吃出一种为了 lambda 而 lambda 的感觉。难道说，你写的很不情愿？并非如此！只是我对 lambda 的理解就到这个程度了。
那么这段代码还能更进一步吗？
或许可以！
说到底，这段代码是递归的，而递归的终极解答是什么呢？是不动点组合子。
Y=λf.(λx.f(xx))(λx.f(xx))
很好，现在就写一个
y = \f -> (\x->f (x x)) (\x->f (x x))
复制代码
然后就会得到一个报错。cannot construct the infinite type
原来经典的 Y 组合子在 haskell 里不能直接定义啊，那只能曲线救国了。
fix f = let x = f x in xff = \f n -> if n <= 2 then 1 else f (n-1) + f (n-2)fib = fix ff
复制代码
看起来没问题，fix 直接借用了经典的不动点定义，会不断的返回函数的不动点f x，运行结果也是正确的。当然有一个瑕疵，就是这是逆推的，现在把它改回顺推。
fix f = let x = f x in xff = \f n a b->if n <=1 then b else f (n-1) b (a+b)fib = \n -> fix ff n 0 1
复制代码
啊哈，一个需要注意的小细节是 n 的位置。
到此为止，已经可以宣告成功，但是为什么不试试完全写成 lambda 呢？这样做虽然没有什么意义，但确实挺有趣的。
fib = \n -> -- 表示输入一个数n (\f -> let x = f x in x) --以匿名函数的形式定义一个Ycombinator ，暂称为Y (\f nn a b -> if nn<=1 then b else f (nn-1) b (a+b)) -- 以匿名函数的形式定义一个顺推式的斐波那契数列函数 暂称为f n 0 1 -- 将 n 0 1 应用于(Y f)
复制代码
看起来，没有问题！即使脱离 fib，直接写进 main 里也没有问题
main = do n<-getLine print ((\n -> -- 表示输入一个数n (\f -> let x = f x in x) --以匿名函数的形式定义一个Ycombinator ，暂称为Y (\f nn a b -> if nn<=1 then b else f (nn-1) b (a+b)) -- 以匿名函数的形式定义一个顺推式的斐波那契数列函数 暂称为f n 0 1) -- 将 n 0 1 应用于(Y f) (read n::Int))
复制代码
评论