Generalised Horner's Rule
Horner's rule 是用來快速核算多項式代值的方法，AoP 第三章把這個規則推廣到一般的 inductive datatypes。一題練習要我們證明稍微推廣的版本：
不過我們還是先把所有的抽象符號具現化為多項式求值的特例，看看它說了什麼。令
f a = h a = a * x；F (A, X) = 1 + A * X是 cons-lists 的 base functor；g (x, y) = x + y（這裡省略 base case）。
[a0, a1, a2, ..., an]丟進
tri f，就會得到多項式的各項[a0, a1 * x, a2 * x2, ..., an * xn]再經過
([ g ]) 把各項加起來，就得到 a0 + a1 * x + a2 * x2 + ... + an * xnHorner's rule 告訴我們這兩段動作其實可以融為一段，只要
f 0 = 0 * x = 0而且
f (g (a, b)) = (a + b) * x = a * x + b * x = g (f a, f b)就可以改用
a0 + (a1 + (a2 + ... (an + 0) * x ...) * x)這個順序核算。
雖然我目前覺得抽象化之後很難把「前提的意義」和「前提如何使 fusion 成功」說清楚，但至少這提供一條可以套的規則 ─ 不懂沒關係，先用就是了。
--
沒有人想一起玩喔…？保證很好玩啦…
Labels: Program Derivation
請問 那個圖書中 tri f 和 id 是啥咪呀 O_O?
tri f 在 lists 上的非正式的定義是把 [a_0, a_1, a_2, ..., a_n] 變成 [a_0, f a_1, f (f a_2), ... f^n a_n]。這可以寫成一個 fold：如果 input list 是空的就不做任何事；如果可以拆成 head 和 tail 就把 tri f tail 的每個元素再套一次 f，然後和 head 接在一起。用 category theory 的方式寫，就是對資料結構的遞迴處（base functor F 的第二個參數）套 T f，然後用那個資料結構的 constructor \alpha 全部組合起來。
id 就是 identity function。
<< 回到主頁