抽象資料型態與代數資料型態

iThome 網站首載：抽象資料型態與代數資料型態

抽象資料型態（Abstract data type）著重資料的狀態與操作封裝，僅透露互動時的規格，目的在使資料獨立於各種實作，避免程式受需求更改而變化。相對地，代數資料型態（Algebraic data type）強調揭露資料的結構與規律性，目的在使得各種處理資料的需求，都可以根據結構與規律性分而治之（Divide and conquer）。

抽象資料型態空泛地定義操作規格

抽象資料型態可舉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>介面：

public interface List<T> {
T head() default { return null; }
List<T> tail() default { return null; }
}

由於Java不支援模式匹配語法，所以在List中定義head與tail方法，以代替值的結構定義。空List沒頭沒尾，可在AlgebraicType類別中如下定義表示：

private static final List<? extends Object> Nil = new List<Object>() {
public String toString() { return "[]"; }
};

AlgebraicType類別中使用nil方法傳回空List實例：

public static <T> List<T> nil() {
return (List<T>) Nil;
}

對於x:xs中的:方法，可如下定義cons方法傳回List<T>的匿名內部類別實例：

public static <T> List<T> cons(final T x, final List<T> xs) {
    return new List<T>() {
        private T head;
        private List<T> tail;
        { this.head = x; this.tail = xs; }
        public T head(){ return this.head; }
        public List<T> 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:[]。為了方便，可設計list方法：

public static <T> List<T> 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 <T> List<T> filter(List<T> lt, F1<T, Boolean> 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<P, R> { 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等方法都可以實作出來。

型態系統影響思考方式

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

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

以下為搭配本篇內容的完整範例程式碼：

import java.util.*;
 
interface F1<P, R> {
    R apply(P p);
}
 
public class AlgebraicType {
    public static interface List<T> {
        T head() default { return null; }
        List<T> tail() default { return null; }
    }
    
    private static final List<? extends Object> Nil = new List<Object>() {
        public String toString() { return "[]"; }
    };
    
    public static <T> List<T> nil() {
        return (List<T>) Nil;
    }
    
    public static <T> List<T> cons(final T x, final List<T> xs) {
        return new List<T>() {
            private T head;
            private List<T> tail;
            { this.head = x; this.tail = xs; }
            public T head(){ return this.head; }
            public List<T> tail() { return this.tail; }
            public String toString() { return head() + ":" + tail(); }
        };
    }
    
    public static <T> List<T> list(T... elems) {
        if(elems.length == 0) return nil();
        T[] remain = Arrays.copyOfRange(elems, 1,  elems.length);
        return cons(elems[0], list(remain));
    }
    
    public static <T> List<T> filter(List<T> lt, F1<T, Boolean> f) {
        if(lt == nil()) return nil();
        if(f.apply(lt.head())) return cons(lt.head(), filter(lt.tail(), f));
        return filter(lt.tail(), f);
    }
    
    public static <T, R> List<R> map(List<T> lt, F1<T, R> f) {
        if(lt == nil()) return nil();
        return cons(f.apply(lt.head()), map(lt.tail(), f));
    }
    
    public static void main(String[] args) {
        // 1:2:3:4:5:[]
        System.out.println(list(1, 2, 3, 4, 5));
        
        // 4:5:[]
        System.out.println(filter(list(1, 2, 3, 4, 5), x -> x > 3));
        
        // 3:6:9:12:15:[]
        System.out.println(map(list(1, 2, 3, 4, 5), x -> x * 3));
    }
}