抽象資料型態(Abstract data type)著重資料的狀態與操作封裝,僅透露互動時的規格,目的在使資料獨立於各種實作,避免程式受需求更改而變化。

相對地,代數資料型態(Algebraic data type)強調揭露資料的結構與規律性,目的在使得各種處理資料的需求,都可根據結構與規律性分而治之。

抽象資料型態空泛地定義操作規格
抽象資料型態,可舉Java的群集(Collection)框架為例。

對於收集物件的需求,是定義在Collection介面中,其定義的add、remove、clear、size、isEmpty等方法,都是不涉及資料結構及相關實作的規格外觀,使用者基於Collection介面進行操作,可不受Collection實作類別採用的資料結構影響,使用者可專心使用Collection,來滿足空泛的物件收集需求。

如果使用者收集物件時,需要具備順序與索引特性,則由List介面繼承Collection介面,並定義get、set、indexOf等可根據索引進行操作的規格,使用者基於List介面進行操作,不受實作類別採用陣列或鏈結而影響。如果使用者收集物件時需要佇列特性,則定義Queue繼承自Collection,提供offer、peek、poll等基於佇列特性的操作規格。如果收集物件時需要雙向佇列特性,則定義Deque繼承自Queue,提供addFirst、addLast、getFirst、getLast等方法。

抽象資料型態的優點,是令開發者可專心在物件間的互動,而不是處理資料時的複雜細節;然而空泛地針對物件外觀操作進行分類定義,容易因針對特定資料結構而衍生出更多型態。例如繼承自Collection的Set特性是收集的物件不重複,但沒有處理順序的能力,為了能針對物件進行排序,又定義了繼承自Set的SortedSet介面。

有新需求就要定義新類型,隨著需求變化,容易產生複雜型態系統。因為一開始就強調狀態與操作的隱藏,不易觀察資料本身處理時的規律,看似流程迥異的實作程式碼,其實有共用流程而不自知。

代數資料型態優先思考資料的結構與規律性
代數資料型態是思考哪些結構的值是屬於哪個類型。例如「書本資訊」型態的值結構,若定義為「書(ISBN, 名稱, 作者群)」,就不會有其他結構;一個代數資料型態也可能會有多個不同結構的值,例如「付費資訊」型態的值結構,可定義為「信用卡(卡號, 持有者, 有效期限)」與「貨到付款」,此外,其他結構的值都不屬於付費資訊型態。

由於屬於某代數資料型態的值,其結構已定義,因此可輕易分析值的組成元素(Component)。比方說,若有個BookInfo型態的值為Book(9789862763100. "Java SE 7 Technology", "Justin Lin"),取得該值中組成元素的模式(Pattern)則為Book(isbn, title, authors),如此isbn就為9789862763100,title就為"Java SE 7 Technology"等。

在支援代數資料型態的語言中,通常也提供模式匹配(Pattern match)語法,可直接取得值中的組成元素,避免使用複雜的流程語法來拆解組成元素。

上篇專欄「List處理模式」中提到的List資料結構模式,其實就定義了List代數資料型態的值應有的結構,也就是「空List」與「首元素:剩餘資料組」,由於List的值結構已定義,因此可結合模式匹配,將List中的組成元素逐一拆解進行處理,直到遇到空List無法再拆解處理為止,由於處理List資料存在著規律性,因此可以抽取出length、map、filter等通用函式。

以抽象型態實作代數型態來思考兩者差異

實際上,抽象資料型態與代數資料型態並非完全對立。像Scala就提供彌封類別(Sealed class)及案例類別(Case class),直接支援代數資料型態的定義。在其他支援抽象資料型態的語言,可自行實作代數資料型態概念,對兩者的理解與運用都有益。

若以JDK8來實作上篇專欄「List處理模式」中的概念,可使用interface如下定義List介面:

T head() default { return null; }
List tail() default { return null; }

由於Java不支援模式匹配語法,所以在List中定義head與tail方法,以代替值的結構定義。空List沒頭沒尾,可在AlgebraicType類別中定義private static final List Nil = new List() { public String toString() { return "[]"; } };,並以public static List nil()方法傳回(List) Nil。對於x:xs中的「:」,可定義public static List cons(final T x, final List xs)傳回List的匿名內部類別實例,類別實作本體如下:

private T head; private List tail;
{ this.head = x; this.tail = xs; }
public T head(){ return this.head; }
public List tail() { return this.tail; }
public String toString() { return head() + ":" + tail(); }

如此之來,擁有元素2的List,可使用cons(2, nil())取得,呼叫其toString()結果會是2:[],擁有元素1、2的List,可使用cons(3, cons(2, nil()))取得,呼叫其toString()結果會是1:2:[]。為了方便,可設計public static List list(T... elems)方法:

if(elems.length == 0) return nil();
T[] remain = Arrays.copyOfRange(elems, 1, elems.length);
return cons(elems[0], list(remain));

如此一來,可使用list(1)取得代表1:[]的List實例,使用list(1, 2)取得代表1:2:[]的List實例。注意這邊都使用工廠(Factory)模式,AlgebraicType的使用者,不直接以類別實作List並產生實例,而是透過cons、list方法,也不對List進行衍生,如此List的值結構就是固定的。
若要實作上篇專欄「List處理模式」中的filter方法,可以如下定義public static List filter(List lt, F1 f):

if(lt == nil()) return nil();
if(f.apply(lt.head())) return cons(lt.head(), filter(lt.tail(), f));
return filter(lt.tail(), f);

其中F1定義為interface F1 { R apply(P p); },為JDK8中Lambda語法要求的函式介面(Functional interface)。由於Java不支援模式匹配,所以使用if針對Nil的情況作判斷。如此一來,若以list(1, 2, 3, 4, 5)建立代表1:2:3:4:5:[]的List實例並指定給lt,並想過濾出大於3的List,可以呼叫filter(lt, x -> x > 3)以傳回代表4:5:[]的List實例。以類似的概念來進行,map、foldLeft等方法都可以實作出來。

型態系統影響思考方式
程式語言會有預設的型態系統,代表了它面對擅於解決的問題時應有的思考方式。程式語言預設的型態系統,對於採用該語言的開發者,深深影響了他的思考與實作風格,進一步地,對於程式庫與框架等也會有根深蒂固的影響。

程式語言預設型態系統,既然就代表了擅於解決的問題,但對某些問題而言,預設型態系統並不適合。當預設型態系統解決特定問題窒礙難行時,跳脫、重新思考問題的本質,或許就會發現更簡單的思路。當問題的本質是認清資料的結構與規律性時,卻採用了隱藏資料狀態與操作細節的抽象資料型態,或許只會反其道而行,加深解決方式的複雜度。

作者簡介


Advertisement

更多 iThome相關內容