# 計算多項式

FLOLAC ’10 最後一天我有大約 25 分鐘的時間和同學們介紹函數程式演算 (functional program calculation). FLOLAC ’10 的同學少部份學過 Haskell 或其他函數語言，大部份只在一週前學了三小時的 OCaml, 寫了一些程式作業，但對 fold 之類的抽象觀念可能還難以掌握。最大區段和問題很難在 25 分鐘內講完，用到兩次摺疊融合(fold-fusion), 而且這問題也已經講得有點煩了。另一個不錯的小例子「陡數列」問題的基本款大概只用得到五分鐘的時間。因此我得另外想個例子講。

``` poly as = sum (zipWith (×) as (iterate (×X) 1)) ```

``` 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 + 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 ```

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`.

### 函數定義

``` 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) ```