眾所周知,原以 top-down 方式表達的 Fibonacci 函數可改以 bottom-up 的方式省去重複的計算。合併排序 (mergesort) 通常寫成 top-down 的遞迴函數,但也有一個 bottom-up 的作法:將相鄰的區段倆倆合併,直到剩下一個大區塊為止。是否有個有系統的方式將 top-down 演算法轉換成 bottom-up 演算法呢?我將回顧 Richard Bird 2008 年的一篇論文 — 使用 natural transformation 與 “zip” 的觀念談論這兩類演算法的轉換.
About Shin-Cheng Mu
函數語言研究者。