List處理模式

如果有一組（List）資料，如何取得資料的長度？開發者容易開始設想程式語言提供哪種資料結構：如果是陣列，使用C語言的開發者，會使用陣列記憶體大小，除以個別元素記憶體大小；而使用Java的開發者，會從length屬性取得陣列長度。

不！現在還沒有要考慮使用哪種程式語言，而是要把這個問題定義為通用語言。

List資料結構模式
思考實體世界中若有一組資料，如何計算該組資料長度？最簡單的方式，就是從資料組開頭計數至尾端，也就是從資料組取得首元素時計數為1，若還可從剩餘資料組取得首元素時計數加1，依此類推至剩餘資料組為空。類似地，如果要把一組資料反過來排列呢？從資料組取得首元素，附加至剩餘資料組尾端，依此類推至剩餘資料組為空。

許多List的問題，解決時都有個固定模式：「取得首元素與剩餘資料組作某些事，直到剩餘資料組為空為止。」如果想將List的問題定義為通用語言，必須先定義何為「空List」，假設定義為[]，再來定義何謂「首元素」與「剩餘資料組」，含有單一元素y的List可定義為y:[]，有x、y兩個元素的List，可表示為x:y:[]，依此類推，如果有個List為x:y:[]，則該List首元素為x，剩餘資料組為y:[]，而y:[]首元素為y，剩餘資料組為[]，[]沒有首元素與剩餘資料組，而[x, y]為x:y:[]撰寫時的簡便形式。

顯然地，如此定義方式，與多數程式語言提供的List結構並不相同，多數程式語言定義List為有順序、具索引的結構，如果從程式語言來思考解決問題，就會受制於程式語言提供的特性，例如思考如何利用變數計算、如何利用索引取得元素等。

想想看，實體世界中處理一組資料，會使用變數嗎？會特地為資料加上索引嗎？基本上不會！那麼如何利用方才定義的List結構解決問題呢？以解決資料組長度來說，可以如下定義：

length [] = 0
length (x:xs) = length xs + 1

若傳入List給length，x表示取得首元素，xs表示剩餘資料組。如果是空List，那長度當然是0，如果可以取得首元素則計數為1，然後持續拆解下去至空List為止，結果讀來就是x:xs的長度，就是xs的長度加1。類似的作法，我們將一組資料反轉排列，可如下定義：

reverse [] = 0
reverse (x:xs) = reverse xs ++ [x]產生新List的map、filter模式

如果想將一組整數都遞增1，可以如下定義：

addOne [] = []
addOne (x:xs) = x + 1 : addOnexs

如果想讓一組整數都減2，其實只要將+1改為-2，如果想讓它們都乘上3，只要將+1改為*3。如果想讓這組整數都作某個運算，也只要將該運算傳入就可以了。將某組資料作某個動作，而成為另一組資料，是處理List的常見模式，因此可以抽象出以下的map定義：

map [] = []
map f (x:xs) = f x : map xs

其中f用來接受傳入的動作，例如map (+1) [1, 2, 3]將會產生[2, 3, 4]的結果，map (*3) [4, 5, 6]會產生[12, 15, 18]。類似地，如果想將一組整數進行過濾，只留下大於3的部份，可以如下定義：

greatThanThree [] = []
greatThanThree (x:xs) = if (x > 3) then (x : greatThanThreexs) else (greatThanThreexs)

如果想從該組整數取得小於10的一組整數，其實只要將>3改為<10，想從該組整數取得等於100的一組整數，只要將>3改為==100。如果想過濾這組整數取得另一組整數，也只要將該過濾運算傳入就可以了。

將某組資料作某個過濾，而得到另一組資料，也是處理List的常見模式，因此可以抽象出以下的filter定義，如此filter (>3) [10, 9, 8, 3, 2, 1]，結果就會是[10, 9, 8]：

filter f [] = []
filter f (x:xs) = if (f x) then (x : filter f xs) else (filter f xs)

對List運算取值的fold處理模式

如果想對一組整數作加總呢？可以如下定義：

sum seed [] = seed
sumseed (x:xs) = sum (seed + x) xs

加總動作就是從0開始，也就是seed為0，接著逐一取出剩餘資料組中的首元素與傳入的seed進行相加，最後得到的就是加總值，例如對[1, 2, 3]加總，可以寫為sum 0 [1, 2, 3]，得到結果就會是6。

如果想得到一組整數的相乘值呢？只要將+改為*，如果想對這組整數作某運算取值，也只要將該運算傳入就可以了。將某組資料作某運算取值，也是處理List的常見模式，因此可以抽象出以下的foldLeft定義：

foldLeft f seed [] = seed
foldLeft f seed (x:xs) = foldLeft f (f seed x) xs

之所以稱為foldLeft，是因為若將List比喻為書本，每個元素就像書頁，逐一取得首元素就像往左翻頁。如果想取得[1, 2, 3]的加總，則可以foldLeft (+) 0 [1, 2, 3]，得到結果就會是6。有些程式庫會提供reduce，實際上就是自動將seed設為首元素，然後進行foldLeft，也就是如下定義，其中空List沒有元素，無法提供seed，因此會得到一個大大的錯誤：

reduce f [] = error "couldn't reduce empty list"
reduce f (x:xs) = foldLeft f x xs

重新思考資料管理問題
由於思考如何解決問題時，都是將問題定義為通用語言，因而實際使用某個程式語言解決問題時，就可套用類似的模式抽取過程。

以未來JDK8版本為例，如果有組方塊，想過濾出藍色積木後取得重量總合，如下撰寫不但直覺，而且隱藏更多細節。可以想像一下，如果直接以程式語言的迴圈及索引來嘗試解決問題，會是多麻煩且曝露過多細節的結果：

blocks.filter(b ->b.getColor() == BLUE)
.map(b ->b.getWeight())
.sum();

有許多程式面對的都是資料管理問題，像是處理關聯式資料庫取得的一組資料，許多開發者以迴圈或索引方式，直接對該組資料撰寫的程式碼，無非都是將資料映射或過濾為另一組資料、對該組資料作某個動作，重複的程式邏輯一再出現，開發者應當思考更高階的資料處理模式，以通用語言先行定義，方可不受程式語言的實現限制。