云风的 BLOG

目前的编译器只能对尾递归进行优化，基本上能消除递归调用。但是像f(n)=f(n-1)+f(n-2)这样的就没有办法了。如果非要用haskell来写迭代式的求f(n)，可以这样
module Fib where

fib_iter' 1 a b = b
fib_iter' 2 a b = b
fib_iter' n a b =
fib_iter' (n - 1) b (a + b)
fib_iter n =
fib_iter' n 1 1

functional programming写出来的代码确实非常简洁，很多时候对函数编程比面向对象编程更有效。在多核时代functional programming的重要性会越来越高。

自动cache函数值不太现实，要cache哪些函数值是算法相关的，编译器不可能知道。像f(n)=f(n-1)+f(n-2)+f(n-3)这个函数可以写成迭代形式来避免重复计算函数值。

今天碰到一个小问题，Haskell 的编译器或者解释器理论上可以在内部 cache 一些函数运行的状态，可以大大加快运算速度。

比如 f(n)=f(n-1)+f(n-2)+f(n-3) 当 n<=1 时， f(n)=2

如果简单的递归的话，每个 f(x) 都会被重复计算很多次。如果语言保证了函数运算无副作用，cache 中间结果就可以大大提高运算速度了。

这个技巧在 C 中我经常用，不过必须人工来实现。刚才试了一下 Winhugs 似乎没有自动做这种优化。