编程语言导论/代数数据类型

本章概述了如何以更函数式的方式实现一些最流行的抽象数据类型。我们从重要的概念开始代数数据类型 (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 或任何其他支持标记不相交并集的语言中，这种错误是不可能发生的。

← 命名空间的作用域 · 函数式数据结构 →