程式語言入門/構造型別

構造型別

程式語言通常只為開發者提供很少的原始型別。如果程式設計師想要增加可用的型別，他們可以定義新的複合型別。如果一個型別是一個集合，那麼一個構造型別就是一個由其他型別構建的新集合。

列舉

列舉是最簡單的原始型別。在一些程式語言中，列舉是另一種型別的子集。在其他語言中，列舉是元素的獨立集合。在C中，我們有前者，而在SML中，我們有後者來定義列舉。下面的程式說明了如何在C中使用列舉

#include <stdio.h>
enum coin { penny = 1, nickel = 5, dime = 10, quarter = 25 };
int main() {
  printf("%d\n", penny);
  printf("%d\n", penny + 1);
  printf("%d\n", penny + 4 == nickel);
}

正如我們在這張圖中所看到的，C的列舉是整數的子集。因此，任何可以應用於整數的操作也可以應用於列舉的元素。這些列舉甚至不是封閉集合。換句話說，對同一個列舉的兩個元素進行求和，可能會得到一個不屬於該型別的結果，例如：便士 + 1不在硬幣列舉中，在我們之前的例子中。

在一些程式語言中，列舉不是現有型別的子集。相反，它們本身就是一個集合。例如，在SML中，列舉是這樣定義的

datatype day = M | Tu | W | Th | F | Sa | Su;
fun isWeekend x = (x = Sa orelse x = Su);

例如，這樣的操作1 + Tu在SML中，將無法進行型別檢查，因為列舉不是整數。在這種情況下，唯一可能的操作是比較，正如我們在函式的實現中所展示的：isWeekend.

元組

元組為我們提供了最重要的構造型別之一。從概念上講，元組是其他型別的笛卡爾積。一個$\scriptstyle n$-元組是有序元素的序列。如果一個元組$\scriptstyle T=T1\times T2$是兩種型別$\scriptstyle T1$和$\scriptstyle T2$的乘積，那麼$\scriptstyle T$的元素數量與$\scriptstyle |T1|\times |T2|$一樣多，其中$\scriptstyle |T1|$和$\scriptstyle |T2|$是集合$\scriptstyle T1$和$\scriptstyle T2$的基數。例如，下面我們有型別宣告a在 SML 中

- val a = (1.2, 3, "str");
val a = (1.2,3,"str") : real * int * string

我們可以對元組應用的典型操作是對其元素進行索引。在SML中，我們透過以下方式對元組進行索引#運算子

- val a = (1.2, 3, "str");
val a = (1.2,3,"str") : real * int * string
- #1 a;
val it = 1.2 : real
- val a = (1.2, ("string", true));
val a = (1.2,("string",true)) : real * (string * bool)
- #1 (#2 a);
val it = "string" : string

元組作為構建聚合資料結構的快捷方式非常有用。這些型別是許多程式語言提供的唯一選擇，用於構建返回多個元素的函式。例如，下面的函式，用Python編寫，對於每個實際引數，輸出包含引數本身及其向上取整值的對，即其向上取整的值

>>> def logMap(n): return (n, math.ceil(n))
... 
>>> logMap(3.14)
(3.1400000000000001, 4.0)

在 SML 中，以及在任何更嚴格遵循 lambda 演算 的語言中，每個函式都只接收一個引數。在這種情況下，元組提供了模擬函式呼叫多個引數的另一種方法。

- fun sum(a, b) = a + b;
val sum = fn : int * int -> int
- sum(2, 4);
val it = 6 : int
- val a = (2, 4);
val a = (2,4) : int * int
- sum a;
val it = 6 : int

記錄

一些程式語言支援具有命名元件的元組。具有命名元件的元組通常被稱為記錄或結構型別。

type complex = {
  rp:real,
  ip:real
};
fun getip (x : complex) = #ip x;

C 語言有一個名為struct的結構，可用於表示元組。下面的示例說明了它的使用。

#include <stdio.h>

struct complex {
  double rp;
  double ip;
};

int main() {
  struct complex c1;
  c1.rp = 0;
  printf("%d\n", c1.rp);
  printf("%d\n", c1.ip);
}

複數結構用其實部和虛部表示複數。struct中的每個元素都有一個名稱。此外，struct中的每個元素都與一個型別相關聯，該型別具有內部表示。一些語言，例如 SML，會將此表示隱藏在程式設計師面前。但是，有一些語言，例如 C，使此表示對程式設計師可見。在這種情況下，語言規範允許程式設計師確切地瞭解元組的表示方式。它定義了表示中哪些部分必須在所有 C 系統中相同，哪些部分可以在不同實現中不同。由於 C 中記錄的內部表示的可見性，可以建立一個程式來遍歷元組的欄位。例如，下面的程式定義了一個 $\scriptstyle 5$-元組（mySt）並使用 指標 操作遍歷其元素。

#include <stdio.h>

struct mySt {
  int i1, i2, i3, i4, sentinel;
};

int main(int argc, char** argv) {
  struct mySt s;
  int *p1, *p4;
  s.i1 = 1;
  s.i2 = 2;
  s.i3 = 3;
  s.i4 = 4;

  p1 = ( (int*) &s);
  p4 = &(s.sentinel);
  do {
    printf("field = %d\n", *p1);
    p1++;
  } while (p1 != p4);
}

列表

列表是函數語言程式設計語言中最普遍的構造型別之一。與元組相比，列表有兩個重要區別。

• 型別宣告不會預定義元素數量。
• 列表中的所有元素必須具有相同的型別。

此外，通常只允許對列表進行以下操作。

• 讀取頭部元素。
• 讀取列表的尾部。

下面的程式說明了在 SML 中使用列表。

- val a = [1,2,3];
val a = [1,2,3] : int list
- val x = hd a;
val x = 1 : int
- val y = tl a;
val y = [2,3] : int list

陣列

向量是儲存具有相同資料型別的容器。儲存在陣列中的元素被索引。許多程式語言使用整數作為索引，而其他語言則更加靈活，允許陣列使用多種型別進行索引，例如整數、字元、列舉等等。有一些程式語言，例如 Pascal，允許開發人員選擇陣列的最小和最大索引。例如，下面在 Pascal 中編寫的程式碼片段可用於計算文件中出現的字母的頻率。

type
  LetterCount = array['a'..'z'] of Integer;

Pascal 中採用的方法使定義陣列大小變得不必要，它由編譯器自動定義。與 Pascal 相反， C 中的每個陣列都從零開始索引。上面的陣列，如果用 C 編寫，將類似於

int LetterCount[26];

在某些程式語言中，陣列具有固定大小。一旦它們被宣告，此大小就無法更改。但是，也存在提供可變長度陣列的程式語言。 Python 就是一個例子。

>>> a = [1,2,3,4]
>>> a
[1, 2, 3, 4]
>>> a[1:1] = [5,6,7]
>>> a
[1, 5, 6, 7, 2, 3, 4]

一些程式語言支援多維陣列。 C 就是一個例子。下面的程式聲明瞭一個二維陣列，用整數填充它，然後找到每個單元格的總和。

#include "stdio.h"
int main() {
  const int M = 5000;
  const int N = 1000;
  char m[M][N];
  int i, j;
  int sum = 0;
  // Initializes the array:
  for (i = 0; i < M; i++) {
    for (j = 0; j < N; j++) {
      m[i][j] = (i + j) & 7;
    }
  }
  // Sums up the matrix elements, row major:
  for (i = 0; i < M; i++) {
    for (j = 0; j < N; j++) {
      sum += m[i][j];
    }
  }
  printf("The sum is %d\n", sum);
}

與列表相反，陣列為開發人員提供了隨機訪問。也就是說，可以 $\scriptstyle O(1)$ 讀取或更新陣列的 $\scriptstyle n^{th}$ 元素。請注意，此操作通常不允許在列表上進行。在這種情況下，讀取 $\scriptstyle n^{th}$ 元素的操作為 $\scriptstyle O(n)$。通常，此限制不會限制可以在無陣列語言中開發的演算法的效率；但是，也有一些演算法無法在這些語言中如此高效地實現。例如，判斷兩個字串是否為異位詞的問題。在提供隨機訪問陣列的程式語言中，可以 $\scriptstyle O(n)$ 實現此函式，其中 $\scriptstyle n$ 是最長字串的大小。否則，最有效的實現將是 $\scriptstyle O(ln{\mbox{ }}n)$。下面的程式用 Java 編寫，線上性時間內解決了異位詞問題。

public class Anagrams {
  public static void main(String args[]) {
    if (args.length != 2) {
      System.err.println("Syntax: java Anagrams s1 s2");
    } else {
      boolean yes = true;
      String s1 = args[0];
      String s2 = args[1];
      if (s1.length() != s2.length()) {
        yes = false;
      } else {
        int table[] = new int [128];
        for (int i = 0; i < s1.length(); i++) {
          table[s1.charAt(i)]++;
        }
        for (int i = 0; i < s2.length(); i++) {
          if (table[s2.charAt(i)] == 0) {
            yes = false;
            break;
          } else {
            table[s2.charAt(i)]--;
          }
        }
      }
      System.out.println("Are they anagrams? " + yes);
    }
  }
}

關聯陣列

一些程式語言提供了一種特殊的陣列型別，字典，也稱為關聯陣列，它允許將任意物件對映到任意值。關聯陣列在動態型別語言中更常見。下面的程式用 Python 編寫，說明了字典的使用。

>>> d = {"Name":"Persival", "Age":31}
>>> d["Name"]
'Persival'
>>> d["Gender"] = "Male";
>>> d
{'Gender': 'Male', 'Age': 31, 'Name': 'Persival'}
>>> d[0] = "Secret Info"
>>> d
{0: 'Secret Info', 'Gender': 'Male', 'Age': 31, 'Name': 'Persival'}

類

類是一種特殊的表格，它包含對自身的引用。換句話說，類是一種“看到”自己的型別。在實現方面，類可以實現為記錄或關聯陣列。例如，在 Java 或 C++ 中，類實現為記錄，具有固定數量的元素。下面的程式展示了類實現的一個例子。

public class ConsCell<E> {
  private E head;
  private ConsCell<E> tail;
  public ConsCell(E h, ConsCell<E> t) {
    head = h;
    tail = t;
  }
  public E getHead() {
    return head;
  }
  public ConsCell<E> getTail() {
    return tail;
  }
  public void print() {
    System.out.println(head);
    if (tail != null) {
      tail.print();
    }
  }
  public int length() {
    if (tail == null) {
      return 1;
    } else {
      return 1 + tail.length();
    }
  }
  public static void main(String argc[]) {
  ConsCell<Integer> c1=new ConsCell<Integer>(1, null);
  ConsCell<Integer> c2=new ConsCell<Integer>(2, c1);
  ConsCell<Integer> c3=new ConsCell<Integer>(3, c2);
  ConsCell<Integer> c4=new ConsCell<Integer>(4, c3);
    System.out.println(c4.length());
    System.out.println("Printing c4");
    c4.print();
    System.out.println("Printing c2");
    c2.print();
  }
}

在 Java 中，類的佈局是不可修改的。一旦宣告，就不能新增新的欄位。這種限制使得在該語言中高效地實現類變得更容易。呼叫在類中宣告的函式，也稱為“方法”，是一種高效的操作。呼叫的目標可以在 $\scriptstyle O(1)$ 時間內找到。一般來說，靜態型別語言，如 C++、C# 和 Ocaml。

實現類的另一種方式是關聯陣列。動態型別語言，如 Python、JavaScript 和 Lua 以這種方式實現類。這種方法的主要優勢在於靈活性：鑑於類是一個可變表，可以在執行時向其新增新的屬性，或從中刪除屬性。下面的程式展示瞭如何在 Python 中宣告和使用類

INT_BITS = 32

def getIndex(element):
  index = element / INT_BITS
  offset = element % INT_BITS
  bit = 1 << offset
  return (index, bit)

class Set:
  def __init__(self, capacity):
    self.capacity = capacity
    self.vector = range(1 + self.capacity / INT_BITS)
    for i in range(len(self.vector)):
      self.vector[i] = 0

  def add(self, element):
    (index, bit) = getIndex(element)
    self.vector[index] |= bit

  def delete(self, element):
    (index, bit) = getIndex(element)
    self.vector[index] &= ~bit

  def contains(self, element):
    (index, bit) = getIndex(element)
    return (self.vector[index] & bit) > 0

s = Set(60)
s.add(59)
s.add(60)
s.add(61)

在 Python 中，類不是剛性結構。因此，可以將新的屬性插入這些型別，也可以從中刪除新的屬性。下面的程式說明了如何在原始的 Python 示例中新增新的方法。新方法處理了向該位集新增未被位集範圍支援的元素的可能性。

def errorAdd(self, element):
  if (element > self.capacity):
    raise IndexError(str(element) + " is out of range.")
  else:
    (index, bit) = getIndex(element)
    self.vector[index] |= bit
    print element, "added successfully!"

Set.errorAdd = errorAdd

s = Set(60)
s.errorAdd(59)
s.add(60)
s.errorAdd(61)

聯合

許多集合 $\scriptstyle A_{1},A_{2},\ldots ,A_{n}$ 的並集是至少在一個基集中的所有元素的集合。 $\scriptstyle \cup$ 符號用於表示這個概念 $\scriptstyle (A_{1}\cup A_{2}\cup \ldots \cup A_{n})$。在程式語言中，這種並集的概念應用於型別：幾種型別 $\scriptstyle T_{1},T_{2},\ldots ,T_{n}$ 的並集是一種新的型別 $\scriptstyle T$，它包含每個基型別中的所有元素。一些程式語言強制開發人員在使用並集時顯式區分每個基型別。其他語言，如 C，相信程式設計師能正確地使用並集的每個元素。下面的程式碼展示瞭如何在 C 中宣告和使用聯合。

#include <stdio.h>
union element {
  int i;
  float f;
};

int main() {
  union element e;
  e.f = 177689982.02993F;
  printf("Int = %d\n", e.i);
  printf("Float = %f\n", e.f);
  e.f = 0.0F;
}

這個例子表明，可以將多種表示形式或格式與單個變數關聯起來。上面的 C 程式碼將 int 和 float 與同一個 element 關聯。因此，聯合元素 e 包含一個可以儲存 int 或 float 的變數。請注意，在上面的程式中，我們已經初始化了欄位f，它是聯合e的一部分；但是，我們使用了它的欄位i。 C 不要求程式設計師使用在聯合中宣告的基型別。在 C 中，聯合只是儲存在記憶體中的一塊資料。如何解釋這塊資料取決於程式設計師想要對其應用的哪種操作。如果聯合 $\scriptstyle U$ 由多個基型別 $\scriptstyle T_{1},T_{2},\ldots ,T_{n}$ 組成，那麼編譯器會在記憶體中為任何 $\scriptstyle U$ 例項保留最大的基型別的大小。

有些程式語言強制程式設計師顯式區分聯合的每個基型別。 SML 屬於這類語言。在 SML 中，聯合是帶標籤的，如果程式設計師想宣告聯合的某個特定子型別，他們需要顯式地提及標籤

datatype element =
  I of int | F of real;
fun getReal (F x) = x
  | getReal (I x) = real x;

標籤使我們能夠在執行時知道儲存在變數中的資料的型別。因為 C 沒有與聯合相關的標籤的概念，所以無法在該語言中進行執行時型別檢查。標籤也確保聯合中的所有集合都是不相交的。因此，聯合 $\scriptstyle U=T_{1},T_{2},\ldots ,T_{n}$ 的基數是每個基集 $\scriptstyle T_{i}$ 基數的總和。

函式型別

函式將給定的集合（即定義域）對映到另一個集合（即值域或像集）。因此，函式的型別指定了函式的定義域和值域。這個概念類似於數學符號 $\scriptstyle A\rightarrow B$，它指的是所有輸入來自集合 A、輸出來自集合 B 的函式的集合。許多程式語言都具有這種構造。下面我們展示了 C 中函式宣告的示例。函式的定義域是實數對，值域是實數，例如，$\scriptstyle F\times Float\rightarrow Float$.

float sum(float a, float b) {
  return a + b;
}

• 多型性*

它指的是變數、函式或物件能夠採用多種形式的能力。