Haskell的代数数据类型

Haskell's algebraic data types

我试图充分理解Haskell的所有概念。

代数数据类型在哪些方面类似于通用类型，例如在C＃和Java中？它们有什么不同？无论如何，它们的代数是什么？

我熟悉通用代数及其环和域，但是对Haskell的类型如何工作只有一个模糊的想法。

Haskell的代数数据类型之所以这样命名，是因为它们与类别理论中的初始代数相对应，从而为我们提供了一些定律，一些运算和一些要操纵的符号。我们甚至可以使用代数符号来描述常规数据结构，其中：

+表示总和类型(不相交的并集，例如Either)。
?代表产品类型(例如结构或元组)
X用于单例类型(例如data X a = X a)
1用于单位类型()
和μ表示最小固定点(例如，递归类型)，通常是隐式的。

带有一些附加的符号：

X?X的X2

实际上，如果可以用1，X，+，?和最小固定点表示，您可能会说(遵循Brent Yorgey)Haskell数据类型是规则的。

使用这种表示法，我们可以简明地描述许多常规数据结构：

单位：data () = ()

1
选项：data Maybe a = Nothing | Just a

1 + X
列表：data [a] = [] | a : [a]

L = 1+X?L
二叉树：data BTree a = Empty | Node a (BTree a) (BTree a)

B = 1 + X?B2

还有其他操作(摘自参考文献中列出的Brent Yorgey的论文)：

扩展：展开定点可以帮助您考虑列表。 L = 1 + X + X2 + X3 + ...(也就是说，列表为空，或者具有一个或两个元素，或者三个或...)
组成?，给定类型F和G，组成F ? G是一种构建"由G结构组成的F结构"的类型(例如R = X ? (L ? R)，其中L是列表，是一棵玫瑰树。
差分，数据类型D的导数(给定为D')是具有单个"孔"的D结构的类型，即，不包含任何数据的可分辨位置。令人惊讶地满足了与微积分相同的规则：

1′ = 0

X′ = 1

(F + G)′ = F' + G′

(F ? G)′ = F ? G′ + F′ ? G

(F ? G)′ = (F′ ? G) ? G′

参考文献：

物种，函子和类型，《我的天哪》，布伦特·A·约基，Haskell’10，2010年9月30日，美国马里兰州巴尔的摩
我左边的小丑，右边的小丑(解剖数据结构)，Conor McBride POPL 2008

Haskell中的"代数数据类型"支持完整的参数多态性，这是泛型在技术上更正确的名称，作为简单的示例，列表数据类型为：

1	data List a = Cons a (List a) \| Nil

等效于(尽可能，忽略非严格评估等)

1
2
3
4
5
6
7

class List {
class Cons : List {
a head;
List tail;
}
class Nil : List {}
}

当然，Haskell的类型系统允许更多...有趣地使用类型参数，但这只是一个简单的示例。关于"代数类型"的名称，老实说，我从来没有完全确定将其命名的确切原因，但是假设它是由于类型系统的数学基础所致。我认为，其原因可以归结为ADT是"一组构造函数的产品"的理论定义，但是距我大学毕业已经过去了两年，所以我不再记得具体细节了。

[编辑：感谢克里斯·康威(Chris Conway)指出了我的愚蠢错误，ADT当然是求和类型，构造函数提供了字段的乘积/元组]

在通用代数中
代数由几组元素组成
(将每个集合视为一种类型的值的集合)
以及一些将元素映射到元素的操作。

例如，假设您有一种"列表元素"和
"列表"的类型。作为操作，您具有"空列表"，它是一个0参数
函数返回一个"列表"和一个带有两个参数的" cons"函数，
一个"列表元素"和一个"列表"，并产生一个"列表"。

此时，有许多适合描述的代数，
因为可能发生两种不良情况：

"列表"集中可能存在无法构建的元素
来自"空列表"和" cons操作"，即所谓的"垃圾邮件"。
这可能是一些从天而降的元素开始的列表，
或没有开头的循环或无限列表。
应用于不同参数的"缺点"结果可能相等，
例如将元素限制为非空列表
可能等于空列表。有时称为"混乱"。

没有这些不良性质的代数称为
首字母缩写，这是抽象数据类型的预期含义。

名称的初始名称来自该属性，即确切地存在
从初始代数到任何给定代数的同态
本质上，您可以通过应用以下操作来评估列表的值
在另一个代数中，结果是明确的。

对于多态类型，它变得更加复杂...

他们之所以称为代数的简单原因；有和(逻辑析取)和乘积(逻辑合取)两种类型。总和类型是有区别的联合，例如：

1	data Bool = False \| True

产品类型是具有多个参数的类型：

1	data Pair a b = Pair a b

在O'Caml中，"产品"变得更加明确：

1	type 'a 'b pair = Pair of 'a * 'b

Haskell的数据类型由于与分类初始代数的联系而被称为"代数"。但这就是疯狂。

@olliej：ADT实际上是"求和"类型。元组是产品。

@Timbo：

您基本上是对的，就像一个抽象的Tree类，带有三个派生类(Empty，Leaf和Node)，但是您还需要强制保证使用Tree类的某个人永远不会添加任何新的派生类，因为使用Tree数据类型的策略是编写基于树中每个元素的类型在运行时切换的代码(添加新的派生类型将破坏现有代码)。您可以想象一下在C＃或C ++中这种讨厌的情况，但是在Haskell，ML和OCaml中，这对于语言设计和语法至关重要，因此编码样式可以通过模式匹配以更加方便的方式支持它。

ADT(和类型)也类似于C或C ++中的带标记的联合或变量类型。

这是一个古老的问题，但没有人提到可空性，这是代数数据类型的重要方面，也许是最重要的方面。由于每个值都是替代值之一，因此基于穷举案例的模式匹配是可能的。

对我来说，Haskell的代数数据类型的概念在C＃之类的OO语言中总是看起来像多态。

请参阅http://en.wikipedia.org/wiki/Algebraic_data_types中的示例：

1
2
3

data Tree = Empty
| Leaf Int
| Node Tree Tree

这可以在C＃中作为TreeNode基类实现，具有派生的Leaf类和派生的TreeNodeWithChildren类，并且甚至需要派生的EmptyNode类。

(好的，我知道，没有人会这样做，但至少您可以这样做。)