FLOLAC ’10 最後一天我有大約 25 分鐘的時間和同學們介紹函數程式演算 (functional program calculation). FLOLAC ’10 的同學少部份學過 Haskell 或其他函數語言,大部份只在一週前學了三小時的 OCaml, 寫了一些程式作業,但對 fold 之類的抽象觀念可能還難以掌握。最大區段和問題很難在 25 分鐘內講完,用到兩次摺疊融合(fold-fusion), 而且這問題也已經講得有點煩了。另一個不錯的小例子「陡數列」問題的基本款大概只用得到五分鐘的時間。因此我得另外想個例子講。
最後想到的例子是這個:給一個數列 a₀, a₁, a₂ ... an
和一個常數 X
, 計算 a₀ + a₁X, + a₂X² + ... + anXn
. 在 Haskell 中可這樣一句搞定:
poly as = sum (zipWith (×) as (iterate (×X) 1))
其中 sum
, zipWith
, iterate
等都是標準的串列函數,定義附在後面。這其實已經是個很好的 Haskell 程式了。只是如果我們還想再省幾個乘法,也許可再化簡一下。
當輸入是空串列,顯然 poly [] = 0
. 考慮輸入是 a : as
的情形:
poly (a : as) = { poly 的定義 } sum (zipWith (×) (a:as) (iterate (×X) 1)) = { iterate 的定義 } sum (zipWith (×) (a:as) (1 : iterate (×X) X)) = { zipWith 的定義 } sum (a : zipWith (×) as (iterate (×X) X)) = { sum 的定義 } a + sum (zipWith (×) as (iterate (×X) X))
不幸地,在 a +
右邊那串式子無法收回成 poly as
— iterate
的最後一個參數是 X
而不是 1
. 一個可能做法是把 poly
擴充一下,改收兩個參數。但這個問題還有更好的解法:
a + sum (zipWith (×) as (iterate (×X) X)) = { iterate f (f b) = map f (iterate f b) } a + sum (zipWith (×) as (map (×X) (iterate (×X) 1))) = { 如果 ⊗ 滿足遞移律, zipWith (⊗) as . map (⊗X) = map (⊗X) . zipWith (⊗) } a + sum (map (×X) (zipWith (×) as (iterate (×X) 1))) = { sum . map (×X) = (×X) . sum } a + (sum (zipWith (×) as (iterate (×X) 1))) × X = { poly 的定義 } a + (poly as) × X
因此我們導出了這個歸納定義:
poly [] = 0 poly (a : as) = a + (poly as) × X
除了 sum
, zipWith
, iterate
等標準函數的定義外,我們還用到了這些規則:
map f (iterate f x) = iterate f (f x)
zipWith (⊗) as . map (⊗X) = map (⊗X) . zipWith (⊗) as
, 如果 ⊗ 滿足遞移律sum . map (×X) = (×X) . sum
, a special case offoldr ⊕ e . map (⊗X) = (⊗X) . foldr ⊕ e
, 如果(a ⊕ b) ⊗ X = (a ⊗ X) ⊕ (b ⊗ X)
, 且e ⊗ X = e
.
這例子的優點是導出了 Horner’s rule, 缺點是最後的程式和原來的一行規格比並沒有快多少。我希望能有個像陡數列問題一樣,能在複雜度上有所改進的程式。大家有好建議嗎?
函數定義
sum 0 = 0 sum (x : xs) = x + sum xs map f [] = [] map f (x : xs) = f x : map f xs zipWith (⊗) [] _ = [] zipWith (⊗) _ [] = [] zipWith (x : xs) (y : ys) = x ⊗ y : zipWith (⊗) xs ys iterate f x = x : iterate f (f x)