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