6 摺

6.4 自然數的摺

自然數可以視為有兩個建構元 Zero 和 Suc 的歸納資料結構。 我們也可為自然數定義一個摺：

foldN :: (a -> a) -> a -> Nat -> a
foldN f e Zero     = e
foldN f e (Suc n)  = f (foldN f e n)

和串列的情況類似，函數 foldN f e 拿一個自然數，將其中的 Zero 代換成 e, Suc 代換成 f. 留意型別：Zero 與 Suc 的型別分別是 Nat 與 Nat -> Nat, foldN 要將一個型別為 Nat 的值轉變為型別為 a 的值, 因此 e 的型別為 a, 而 f 的型別為 a -> a. 為方便稱呼，我們也將 e 與 f 分別稱為基底值與步驟函數。

許多我們定義過的、自然數上的函數都可寫成自然數的摺：

  • exp b = foldN (b*) 1,

  • (+n) = foldN (Suc) n,

  • (*n) = foldN (n+) 0.

自然數上的 id :: Nat -> Nat 也可寫成摺：id = foldN (Suc) 0.

自然數的摺也有一個融合定理：

定理 6.18 摺融合定理(自然數版)

給定 f :: a -> a, e :: a, h :: a -> b. 如果對所有在 foldN f e 值域中的 x :: a, 融合條件 h (f x) = g (h x) 成立, 則

h . foldN f e = foldN g (h e)
例 6.19

判斷一個自然數是否為偶數的述語 even :: Nat -> Bool 可寫成一個摺:

  even = foldN not True

函數 even . (+n) 判斷一個數值加上 n 之後是否為偶數。 由於 (+ n) = foldN (Suc) n, 我們可以嘗試把 even 融入 (+n), 變成一個摺。 根據定理6.18 , 基底值為 even n; 而由於 even (Suc n) = not (even n), 步驟函數為 not. 因此：

even . (+n) = foldN not (even n)
練習 6.12

回顧第2.11 節中提到的費氏數定義：

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

若直接將上述定義當作演算法，我們得做許多重複的計算。 定義 fib2 n = (fib (1+n), fib n). 請將 fib2 融合進 id :: Nat -> Nat, 以便得到一個遞迴呼叫次數為 $O(n)$ 的演算法。

答案

回顧 id = foldN (Suc) 0. 欲將 fib2 融入 id, 基底值為 fib2 0 = (fib 1, fib 0) = (1,0). 為得到步驟函數，我們演算如下：

   fib2 (Suc n)
=  (fib (Suc (Suc n)), fib (Suc n))
=    {- fib 之定義 -}
   (fib (Suc n) + fib n, fib (Suc n))
=  (\(x,y) -> (x+y,x)) (fib2 n)

因此我們得到

fib2 = foldN (\(x,y) -> (x+y,x)) (1,0)