計算多項式

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 asiterate 的最後一個參數是 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 等標準函數的定義外,我們還用到了這些規則:

  1. map f (iterate f x) = iterate f (f x)
  2. zipWith (⊗) as . map (⊗X) = map (⊗X) . zipWith (⊗) as, 如果 ⊗ 滿足遞移律
  3. sum . map (×X) = (×X) . sum, a special case of foldr ⊕ 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)

Leave a Comment

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *