程式語言導論/代數資料型別

本章概述瞭如何以更函式式的方式實現一些最流行的抽象資料型別。我們從重要的概念開始代數資料型別 (ADT)。它們是在函式式語言中實現資料結構的主要機制。然後，我們將繼續介紹許多流行資料型別（如堆疊和佇列）的函式式實現。

代數資料型別

大多數程式語言都採用型別的概念。簡而言之，型別就是一個集合。例如，Java 程式語言中的型別 int 是數字的集合 $\{-2147483648,...,-1,0,1,...,2147483647\}$ ，而型別 boolean 只有兩個值：true 和 false。

作為集合，型別可以用數學運算組合起來，以產生新的（也許更復雜的）型別。例如，型別 int $\times$ boolean（其中 $\times$ 表示笛卡爾積）是元組的集合，由下式給出

\{(\mathrm {true} ,-2147483648),...,(\mathrm {true} ,2147483647),(\mathrm {false} ,-2147483648),...,(\mathrm {false} ,2147483647)\}

代數資料型別是一種形式化方法，用於表達這些型別的組合。在 ML 中，這些型別用關鍵字 datatype 宣告。例如，要宣告一個包含七個元素的型別 weekday，在 ML 中，我們寫

 datatype weekday = Monday
                  | Tuesday
                  | Wednesday 
                  | Thursday
                  | Friday
                  | Saturday
                  | Sunday

豎線用於表示並集。實際上，代數資料型別通常是更簡單型別的並集。這些子集中的每一個都有一個唯一的標籤。在上面的例子中，我們有七個不同的標籤。每個標籤都區分了一個單例集。換句話說，我們的 weekday 型別的基數是七，因為此型別是七個基數為一的型別的並集。布林型別可以宣告如下

  datatype Boolean = True 
                   | False

布林值和工作日的並集宣告如下

  datatype BoolOrWeek = Day of Weekday
                      | Bool of Boolean;

而它的笛卡爾積可以宣告如下

  data BoolAndWeek = BoolWeekPair of Boolean * Week;

代數資料型別具有兩個重要的屬性。第一個事實是它們可以進行模式匹配。模式匹配是一種簡單的機制，它允許將函式實現為一系列由宣告左側出現的標籤觸發的 case。例如，我們可以寫一個函式來測試一個工作日是否屬於週末，如下所示

  fun is_weekend Sunday   = True
    | is_weekend Saturday = True
    | is_weekend _        = False

模式從上到下逐個嘗試，直到其中一個匹配。如果沒有匹配，ML 執行時將丟擲一個異常。可以使用萬用字元，就像我們在上面的 _ 中所做的那樣。此模式匹配任何 Weekday。與資料型別每個子集相關聯的標籤對於模式匹配至關重要，因為它區分了不同的子集。

代數資料型別的另一個重要屬性是它們可以具有遞迴定義。這樣一來，就可以非常簡潔地定義二叉樹之類的結構。下面的例子展示了一個整數鍵的樹。

  datatype tree = Leaf
                | Node of tree * int * tree;

代數資料型別也可以是引數化的，因此依賴於其他型別。這使我們能夠定義更通用的結構，從而提高模組化和重用性。例如，可以定義一個通用樹，如下所示

   datatype 'a tree = Leaf
                    | Node of 'a tree * 'a * 'a tree;

其中 ' 符號用於表示 'a 可以是任何型別。例如，工作日的樹的型別為 weekday tree。

代數資料型別可以遞迴定義的事實提供了很大的靈活性。在接下來的部分中，我們將展示代數資料型別如何用於實現一些常見資料結構的示例。

不相交併集

正如我們之前所解釋的，代數資料型別表示更簡單型別的不相交併集。作為一個新的例子，下面的型別 bunch 描述了兩種型別的並集：多型的 'a 型別和多型的列表型別。

datatype 'x bunch = One of 'x
                  | Group of 'x list;

下面的函式 size（型別為 'a bunch -> int）說明了如何使用此型別。此函式返回 bunch 例項中的元素數量

fun size (One _) = 1
  | size (Group x) = length x;

不相交併集也可以在不支援標記型別的語言中實現。例如，我們可以用 C 語言實現型別 bunch，但在這種情況下，編譯器沒有足夠的資訊來檢查程式的正確性

#include <stdio.h>
#include <stdlib.h>

enum bunch_tag {ONE, GROUP};

typedef union {
  int one;
  int* group;
} bunch_element_type;

typedef struct { 
  bunch_element_type bunch_element;
  unsigned tag;
} bunch;

bunch* createOne(int i) {
  bunch* b = (bunch*)malloc(sizeof(bunch));
  b->tag = ONE;
  b->bunch_element.one = i;
  return b;
}

void printBunch(bunch* b) {
  switch(b->tag) {
    case ONE:
      printf("%d\n", b->bunch_element.one);
      break;
    case GROUP:
      {
        int i = 0;
        while (b->bunch_element.group[i] != 0) {
          printf("%8d", b->bunch_element.group[i]);
          i++;
        }
      }
  }
}

int main(int argc, char** argv) {
  while (argc > 1) {
    int i;
    argc--;
    i = atoi(argv[argc]);
    bunch* b1 = createOne(i);
    printBunch(b1);
  }
}

C 語言中的型別並集由 union 結構定義。在此示例中，我們使用此類並集的結構，以及一個表示標籤（即型別識別符號）的整數。程式設計師必須注意不要生成不一致的程式碼，因為語言無法強制執行標籤和型別的正確繫結。例如，下面的函式是有效的，但從邏輯角度來看是錯誤的

bunch* createOne(int i) {
  bunch* b = (bunch*)malloc(sizeof(bunch));
  b->tag = GROUP;
  b->bunch_element.one = i;
  return b;
}

該函式是錯誤的，因為我們正在用常量 GROUP 來標記型別，而該常量最初旨在表示具有多個（而不是隻有一個）整數元素的 bunch 例項。在 ML 或任何其他支援標記不相交併集的語言中，這種錯誤是不可能發生的。

← 名稱空間的作用域 · 函式式資料結構 →