什么是归纳定义的数据类型？

Question

有哪些归纳数据类型的例子？归纳类型与非归纳类型有何不同？他们能做什么是不可能的呢？什么时候不应该使用它们？

我们非常感谢任何语言的代码片段。

Answer 1

归纳数据类型只是根据其自身定义的数据类型。一个简单的例子是一个列表，我们可以将其定义为：

type List<'a> =
| Empty
| List of 'a * List<'a>

因此，列表是空的，或者它有一个头节点和一个尾部，它本身就是一个列表。这允许我们以非常简单的方式定义列表，而不需要任何其他内置数据结构（除了元组类型，但我们可以在没有它的情况下完成它，它只是简化了示例）。

然后我们可以创建一个简单的函数来添加到列表中，例如：

let add item = function
| Empty -> List (item, Empty)
| List (head, tail) -> List (item, (List (head, tail)))

这将一个项目和一个列表作为输入，并返回一个新列表。如果输入列表为空，则返回一个列表，其中项目为head，Empty列表为尾部。如果列表不为空，则返回一个新列表，其中项目为head，原始列表为tail。

我们可以使用此函数来构建任何类型的列表。对于整数，这看起来像：

Empty 
|> add 1
|> add 2
|> add 3

其中|>是一个运算符，它接受前面的值并将它作为最后一个参数传递给下一个函数。这给我们列表：

List<int> = List (3,List (2,List (1,Empty)))

至于何时不应该使用它们，存在一些情况，其中递归定义的数据结构相对于例如可变状态的数组可能导致性能或存储器损失。这通常是由于底层系统实现基于更接近数组镜像的结构。但是，根据用例，维护可变状态数组可能会导致其他处罚，例如并发应用程序中的锁定管理。如果您对更详细的分析感兴趣，我强烈推荐这本书Purely Functional Data Structures。