Fibonacci，想试试用Haskell写，没想到有很多有很多有意思的东西。一步一步来，首先是定义：

定义：Fibonacci数列是这样0,1,1,2,3,5,8...一串满足F(0)=0,F(1)=1并且当n>=2时有F(n)=F(n-1)+F(n-2)的数列。能算出F(n)的算法有很多，但速度却差别很大：

最慢的递归

fibs 0 = 0
fibs 1 = 1
fibs n = fib (n-1) + fib (n-2)

想象一下展开的树，自顶向下有很多重复的分支，我试了一下，算fibs 40都有明显的迟钝了。空间复杂度为$\Theta(n)$，时间复杂度为$\Theta(\phi^n)$，其中$\phi = \frac{\sqrt{5}+1}{2}$，呈指数型增长。

快一点的迭代

上来肯定想到的就是动态规划（DP）了。如果已经有F(k-2)和F(k-1)，那么直接加一起就是F(k)，然后重复此过程把F(k-1)和F(k)加一起得到F(k+1)直到k=n：

int fib(int n) {
  int a = 0;
  int b = 1;
  while (n-- > 1) {
    int t = a;
    a = b;
    b += t;
  }
  return b;
}

自底向上，没有重复的计算，没有膨胀的堆栈，空间、时间复杂度分别为$\Theta(1)$，$\Theta(n)$。这个在Haskell中借助iterate有个很有意思的实现。首先要知道Haskell是惰性求值的，比如有个tuple，(2 + 3, 4)在其他语言中存在内存里一般就是(5, 4), 而在Haskell里不会计算2 + 3，只有访问第一个元素的时候（实际是pattern matching的时候）才会计算，可以把第一个元素想象成一个没有参数的lambda，在访问的时候才会求值：(<thunk 2 + 3>, 4)。借助iterate我们能生成一个存有所有Fibonacci数的List，用的时候拿就行了。

回头看上面c程序，每次循环会算出下一对a和b，类比成下面的过程，x就是a和b的tuple，f负责算出下一个tuple：

x           = (0, 1)
f x         = (1, 1)
f $ f x     = (1, 2)
f $ f $ f x = (2, 3)
...

f 就是一个简单的lambda： f = \(a, b) -> (b, a + b)

这是Haskell中的iterate：

iterate f x == [x, f x, f (f x), …]

借助iterate就能算出所有的tuple：

iterate (\(a, b) -> (b, a + b)) (0, 1) ==> [(0,1),(1,1),(1,2),…]

最后就简单了，只要把每个tuple的一个元素拿出来就是所有的Fibonacci数了：

fibs = map fst $ iterate f x

看起来很正常，但其实有点问题. 可以看这里，总结下来就是Full Laziness会用更多内存，并带来性能问题，这也就是问什么wiki里尾递归版本使用了Bang Patterns，而iterate借助fold/build避免了构建list和pattern matching所带来的性能消耗。

按照这个思路，我试着用ruby实现了一下：

iterate = -> (x, &block) do
  Enumerator.new do |yielder|
    loop do
      yielder << x
      x = block.call(x)
    end
  end.lazy
end

x = [0, 1]
f = -> (ab) { [ab[1], ab[0]+ab[1]] }
fibs = iterate.call(x, &f).map(&:first)

但很快就stack too big了…, 实际上f可以很灵活，比如：

f = \(a, b) -> (a + b, a + 2 * b)

这样product列表就是这样[(1,1),(2,3),(5,8),...](从1开始)，正是所有的Fibonacci数，接下来flatmap就行了。 还有一个很fancy的方法是这个：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Stackoverflow上有两个答案解释的比较清楚：

当你把它塞到point free converter里，得到的是这坨WTF的东西：

fib = fix ((0 :) . (1 :) . ap (zipWith (+)) tail)

首先ap (zipWith (+)) tail其实是\xs -> zipWith (+) xs (tail xs)（可以看这里）。ok，这个fix看名字应该是不动点，根据不动点的定义应该是这样的fix f = f (fix f)，但Haskell实际是这么实现的fix f = let x = f x in x。查了一下，这样写会快一些。让我奇怪的不是这个，而是：

我知道你又要说惰性求值，但是似乎无论用iterate还是zipWith，无论用Haskell还是Ruby，我感觉这些好像都有某种内在的联系，某种无穷数据类型和递归直接的联系。以前看SICP时没深究，只知道迭代需要多加点变量来记录计算的状态。现在看了这篇文章，才知道它们都是Corecursion。

有关Corecursion的东西可以看Wikipedia，我没大看懂，不过圈一下重点：

往下好像涉及到范畴论什么的，真是让人头大，有时间再看吧。

搞了这么多都是迭代，时间复杂度还是$\Theta(n)$，算第1000000个会很久。想更快就要用数学了。

Faster!!

\[\begin{align*} F(n+1) &= 1\,F(n) + 1\,F(n-1)\\ F(n) &= 1\,F(n) + 0\,F(n-1)\\ \\ \begin{bmatrix} F(n+1) \\ F(n) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F(n) \\ F(n - 1) \end{bmatrix} \\ \begin{bmatrix} F(n+1) \\ F(n) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F(1) \\ F(0) \end{bmatrix} \\ \\ \text{并且} \\ \begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F(0) \\ F(-1) \end{bmatrix} \\ \\ \text{于是得到}\\ \begin{bmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F(1) & F(0) \\ F(0) & F(-1) \end{bmatrix} \\ \\ \text{其中} \\ F(1) &= 1 \\ F(0) &= 0 \\ F(-1) &= 1 \end{align*}\]

右边的矩阵是个单位矩阵，于是就得出结论啦：

\[\begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n\\ F_{n} & F_{n-1} \end{pmatrix}\]

于是算第n个Fibonacci数的问题就简化成了求矩阵n次方的问题，注意这里要用矩阵快速幂算法才能达到\(\Theta(logN)\)（可参考TAOCP卷二4.63节），不然就会退化成动态规划。

Haskell的实现利用Num的特性，只需实现*就行了：

newtype Mat a =
  Mat [[a]]
  deriving (Eq, Show)

instance Num a =>
 Num (Mat a) where
  Mat x * Mat y =
    Mat
      [ [ sum $ zipWith (*) xs ys
	| ys <- transpose y ]
      | xs <- x ]
  negate = undefined
  (+) = undefined
  abs = undefined
  fromInteger _ = undefined
  signum = undefined

fib_matrix 0 = 0
fib_matrix n = l $ Mat [[1, 1], [1, 0]] ^ n
  where l (Mat a) = head a !! 1

这里还有个据说更快的方法Fast doubling，利用上面的矩阵能推导出来，时间复杂度同样是$\Theta(logN)$，似乎快那么一点。

嗯，Fibonacci就这样了，茴香豆的茴字有很多种写法。

有空还是要看看范畴论，不然总感觉缺了点啥。