编程语言入门/构造类型

构造类型

编程语言通常只为开发者提供很少的原始类型。如果程序员想要增加可用的类型，他们可以定义新的复合类型。如果一个类型是一个集合，那么一个构造类型就是一个由其他类型构建的新集合。

枚举

枚举是最简单的原始类型。在一些编程语言中，枚举是另一种类型的子集。在其他语言中，枚举是元素的独立集合。在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;
}

• 多态性*

它指的是变量、函数或对象能够采用多种形式的能力。