如果有一組(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();

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

 

作者簡介


Advertisement

更多 iThome相關內容