Fibonacci 使用惰性评估

延迟评估意味着 Haskell 将仅评估其值需要的列表项。

基本的递归定义是：

f (0)  <-  0
f (1)  <-  1
f (n)  <-  f (n-1) + f (n-2)

如果直接评估，它将非常慢。但是，假设我们有一个记录所有结果的列表，

fibs !! n  <-  f (n) 

然后

                  ┌──────┐   ┌──────┐   ┌──────┐
                  │ f(0) │   │ f(1) │   │ f(2) │
fibs  ->  0 : 1 : │  +   │ : │  +   │ : │  +   │ :  .....
                  │ f(1) │   │ f(2) │   │ f(3) │
                  └──────┘   └──────┘   └──────┘

                  ┌────────────────────────────────────────┐
                  │ f(0)   :   f(1)   :   f(2)   :  .....  │ 
                  └────────────────────────────────────────┘
      ->  0 : 1 :               +
                  ┌────────────────────────────────────────┐
                  │ f(1)   :   f(2)   :   f(3)   :  .....  │
                  └────────────────────────────────────────┘

这被编码为：

fibn n = fibs !! n
    where
    fibs = 0 : 1 : map f [2..]
    f n = fibs !! (n-1) + fibs !! (n-2)

甚至是

GHCi> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
GHCi> take 10 fibs
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

zipWith 通过将给定的二元函数应用于给定的两个列表的相应元素来生成列表，因此 zipWith (+) [x1, x2, ...] [y1, y2, ...] 等于 [x1 + y1, x2 + y2, ...]。

编写 fibs 的另一种方法是使用 scanl 函数 ：

GHCi> let fibs = 0 : scanl (+) 1 fibs
GHCi> take 10 fibs
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

scanl 构建了 foldl 将产生的部分结果列表，沿着输入列表从左到右工作。也就是说，scanl f z0 [x1, x2, ...] 等于 [z0, z1, z2, ...] where z1 = f z0 x1; z2 = f z1 x2; ...。

由于延迟评估，两个函数都定义了无限列表，而没有完全计算出来。也就是说，我们可以编写一个 fib 函数，检索无界 Fibonacci 序列的第 n 个元素：

GHCi> let fib n = fibs !! n  -- (!!) being the list subscript operator
-- or in point-free style:
GHCi> let fib = (fibs !!)
GHCi> fib 9
34