復用＝高階函數和多態
高階函數
假設現在有一個計算銷售額的函數，輸入年份n，返回該年的銷售額。
我們可以這樣定義一個計算總銷售額的函數
定義高階函數
得到如下totalSales
如果要定義一個新的銷售額計算函數的話，這樣就可以
同樣的方法，如果要對list中的所有數字取整，可以這麼玩
通過map的思路可以這樣定義
因此 roundList = mapNum round
以上的mapNum和total通過higher-order實現了reuse。
多態
先來一個計算列表長度的函數
從定義可以看出函數(#)是類型無關的。
就是說(#)可以是
像(#)這樣的函數就是所謂的多態。
有一個特別的函數--也是多態的。[Num]得到整數列表，[String]得到字元串列表。
還有比如swap函數
可以衍生出
由此可見多態也是實現reuse的一種方法。
高階函數和多態的混合使用
前面談到高階函數的時候提到了mapNum函數，結合多態可以實現一個general的map函數。
類似於map這樣的函數，統稱為general函數。
從兩個維度可以認識map函數的generality：一是f的輸入list類型是任意的；二是一旦輸入輸出類型確定，那麼操作f的類型以及整個函數的類型也就確定了
那麼問題來了，怎麼抽象出一個general函數？
現在有一個求和函數定義如下：
首先，我們把(+)函數和初值0抽象出來，可以得到
因此sum = foldr (+) 0
然後，進行多態化
通過多態的foldr，可以這麼實現concat函數
事實上，更加general的foldr可以定義如下:
也就是說，摺疊在foldr中的函數的返回值類型不必和list中的元素類型相同，譬如利用foldr來實現確定list長度的函數(#)現在是這樣的：
list的本質
結合通過上面的介紹，我們進一步來探討列表類型list的本質。
list的構造子定義：
所以[1, 2]等價於1 : (2 : [])
假設現在有個列表操作函數g，定義如下：
那麼通過這樣的模式，對foldr進一步抽象得到
通過fold，可以定義諸如tail
再進一步，假設有一個類型家族t *(例如tree)，提供這樣的操作
那麼理論上就可以對t *類型族的對象實現list操作。
譬如對t *的map操作就可以是這樣的
Tree as lists
相對應的empty/cons/fold定義如下
cons操作圖例：
圖一 插入節點 Node b前
圖二 插入節點Node b之後
把tree當做list,實現fold操作
定義splitTree如下
Tree-like types
一種典型的針對tree的操作形如：
定義h = (treeRec f st)得到treeRec：
用(t *)替代(tree *)，定義操作：
通過這幾個介面定義tree sort：
mVal實現了兩個sorted list排序並且插入val節點。這是其中一種實現：
遞歸訪問一棵樹的過程本質上用的是分制（divide and conquer）的思想，因此把任意的數據類型當做tree其實原理都是一樣的。
Lists as trees
把list定義成tree
得到
這裡的listToTree通過不斷的二分製作子樹，並且把每次二分前的list的第一個元素當做新的子樹的根節點。
另一種listToTree定義：
利用第二種listToTree定義，定義flatten函數：
此時flatten函數等價於quicksort。
總結
文章展示了通過高階函數和多態，實現一個list，在一個scope下即可以當列表實現不同的列表操作，也可以當做tree實現各種樹的操作。
軟體的重用完全體現在了類型的定義上，而定義類型的過程事實上就是設計演算法的過程，這也是所謂的"algorithm oriented" stype。
原文：Simon Thompson. Higher-order + Polymorphic = Reusable Computing Laboratory. University of Kent Canterbury, CT2 7NF, U.K.
TAG:牛頓一號 |