代数数据类型

在计算机编程中，特别是函数式编程和类型理论中，代数数据类型（ADT）是一种复合类型，即由其他类型组合而成的类型。

两类常见的代数类型是乘积类型（即图元和记录）和总和类型（即标记的或不相交的联合体、共产品类型或变体类型）。一个产品类型的值通常包含几个值，称为字段。该类型的所有值都有相同的字段类型组合。一个乘积类型的所有可能值的集合是其字段类型的所有可能值的集合的集合论乘积，即笛卡尔乘积。一个总和类型的值通常被分组为几个类别，称为变体。

一个变体类型的值通常是用一个叫做构造器的准功能实体创建的。每个变体都有自己的构造函数，它接受指定数量的参数，并具有指定的类型。和类型的所有可能值的集合是其变体的所有可能值的集合的集合论之和，即不相连的联合。枚举类型是和类型的一个特例，其中构造函数不需要参数，因为每个构造函数只定义一个值。

代数类型的值是用模式匹配来分析的，它通过构造函数或字段名来识别一个值，并提取它所包含的数据。

代数数据类型是在Hope中引入的，Hope是20世纪70年代在爱丁堡大学开发的一种小型函数式编程语言。

代数数据类型最常见的例子之一是单链表。列表类型是一种和类型，有两个变体，Nil表示空列表，Consxxs表示新元素x与列表xs的组合，以创建一个新列表。下面是一个用Haskell声明单链表的例子。Cons是construct的缩写。

许多语言对以这种方式定义的列表有特殊的语法。例如，Haskell和ML分别用[]表示无，用:或:表示Cons，用方括号表示整个列表。所以Cons1(Cons2(Cons3Nil))在Haskell中通常写成1:2:3:[]或[1,2,3]，或者在ML中写成1::2::3:[]或[1,2,3]。对于一个稍微复杂的例子，二叉树可以在Haskell中实现如下。这里，Empty代表一棵空树，Leaf包含一段数据，Node将数据组织成分支。

在大多数支持代数数据类型的语言中，都可以定义参数化类型。本文后面会给出一些例子。

与函数有点类似，数据构造函数被应用于适当类型的参数，产生一个类型构造函数所属的数据类型的实例。例如，数据构造函数Leaf在逻辑上是一个Int->Tree的函数，意味着给Leaf一个整数作为参数会产生一个Tree类型的值。

由于Node需要两个Tree类型本身的参数，该数据类型是递归的。对代数数据类型的操作可以通过使用模式匹配来检索参数来定义。

例如，考虑一个查找Tree深度的函数，这里用Haskell给出。因此，给定深度的Tree可以使用Empty、Leaf或Node中的任何一种来构造，并且必须分别匹配其中的任何一种来处理所有情况。

在Node的情况下，该模式会提取子树l和r进行进一步处理。代数数据类型非常适用于实现抽象语法。例如，下面的代数数据类型描述了一种代表数字表达的简单语言。为这种语言编写一个评估函数是一个简单的练习；然而，更复杂的转换也变得可行。

例如，编译器中的优化通道可以写成一个函数，将抽象表达式作为输入，并返回一个优化形式。

发生的情况是，有一个数据类型，它可以是几种类型的事物之一。每种类型的事物都与一个叫做构造函数的标识符相关联，它可以被看作是该种数据的一种标签。

每个构造函数可以携带不同类型的数据。一个构造函数可以不携带任何数据（例如，上面的例子中的Empty），或者携带一个数据（例如，"Leaf"有一个Int值），或者携带多个数据（例如，"Node"有两个Tree值）。