Haskell 的代数数据类型

Question

我试图完全理解 Haskell 的所有概念。

代数数据类型在哪些方面与泛型类型相似，例如在 C# 和 Java 中？它们有何不同？到底它们有什么代数意义呢？

我熟悉通用代数及其环和域，但我对 Haskell 类型的工作原理只有一个模糊的了解。

Answer 1

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

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

相当于（尽可能多，并忽略非严格评估等）

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

当然 Haskell 的类型系统允许更多......类型参数的有趣使用但这只是一个简单的例子。关于“代数类型”名称，老实说，我从来没有完全确定它们被命名的确切原因，但假设这是由于类型系统的数学基础。我 相信 原因归结为 ADT 的理论定义是“一组构造函数的产物”，但是我从大学毕业已经有几年了，所以我已经不记得具体细节了。

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

Answer 2

哈斯克尔的 代数数据类型 之所以如此命名，是因为它们对应于 初始代数 在范畴论中，给我们一些定律、一些运算和一些可以操纵的符号。我们甚至可以使用代数符号来描述常规数据结构，其中：

• + 表示求和类型（不相交的联合，例如 Either).
• • 代表产品类型（例如结构体或元组）
• X 对于单例类型（例如 data X a = X a)
• 1 对于单位类型 ()
• 和 μ 对于最小固定点（例如递归类型），通常是隐式的。

带有一些附加符号：

• X² 为了 X•X

事实上，您可能会说（遵循 Brent Yorgey），如果 Haskell 数据类型可以用以下形式表示，那么它就是常规数据类型： 1, X, +, •, ，和一个最小不动点。

通过这种表示法，我们可以简洁地描述许多常规数据结构：

• 单位： 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•B²

其他操作成立（摘自 Brent Yorgey 的论文，在参考文献中列出）：

• 扩张：展开固定点有助于思考列表。 L = 1 + X + X² + X³ + ... （也就是说，列表要么是空的，要么有一个元素，或者两个元素，或者三个，或者......）

• 作品， ◦, ，给定类型 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.Yorgey, Haskell’10，2010 年 9 月 30 日，美国马里兰州巴尔的摩
• 我左边是小丑，右边是小丑（剖析数据结构）, 康纳·麦克布莱德 POPL 2008

Answer 3

在 通用代数 一个 代数 由某些元素集（将每个集合视为类型的值集）和一些操作，这些操作将元素映射到元素。

例如，假设您有一种“列表元素”和一种“列表”类型。作为操作，您具有“空列表”，这是一个0-题词函数，返回“列表”，而“ cons”函数，该函数需要两个参数，一个“列表元素”和“列表”，并产生“列表” ”。

在这一点上，有许多代数符合描述，因为可能发生了两个不良的事情：

• “列表”集中可能有元素，这些元素无法从“空列表”和“ Cons操作”（所谓的“垃圾”）中构建。这可能是从从天上掉下来的某些元素开始的列表，或者没有开始或无限列表的循环。

• 应用于不同参数的“缺点”的结果可能是平等的，例如将元素遵守非空列表可以等于空列表。这有时被称为“混乱”。

不具有这些不良性质的代数称为最初的, ，这就是抽象数据类型的本意。

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

对于多态类型来说，情况变得更加复杂......

Answer 4

它们被称为代数的一个简单原因；有和（逻辑或）和积（逻辑合）类型。总和类型是可区​​分联合，例如：

data Bool = False | True

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

data Pair a b = Pair a b

在奥卡米尔中，“产品”变得更加明确：

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

Answer 5

Haskell 的数据类型被称为“代数”，因为它们与 分类初始代数. 。但那样就是疯狂。

@olliej：ADT 实际上是“sum”类型。元组是产品。

Answer 6

@廷博：

您基本上是正确的，它有点像具有三个派生类（Empty、Leaf 和 Node）的抽象 Tree 类，但您还需要强制保证使用您的 Tree 类的人永远不会添加任何新的派生类，因为使用 Tree 数据类型的策略是编写在运行时根据树中每个元素的类型进行切换的代码（并且添加新的派生类型会破坏现有代码）。您可以想象这在 C# 或 C++ 中会变得很糟糕，但在 Haskell、ML 和 OCaml 中，这是语言设计和语法的核心，因此编码风格通过模式匹配以更方便的方式支持它。

ADT（总和类型）也有点像 标记的工会 或者 变体类型 在 C 或 C++ 中。

Answer 7

老问题，但没有人提到可空性，这是代数数据类型的一个重要方面，也许是最重要的方面。由于每个值大多是替代值之一，因此可以进行详尽的基于案例的模式匹配。

Answer 8

对我来说，Haskell 的代数数据类型的概念总是看起来像 C# 等面向对象语言中的多态性。

看一下来自的例子 http://en.wikipedia.org/wiki/Algebraic_data_types:

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

这可以在 C# 中实现为 TreeNode 基类，并带有派生的 Leaf 类和派生的 TreeNodeWithChildren 类，如果您甚至需要派生的 EmptyNode 类。

（好吧，我知道，没有人会这样做，但至少你可以做到。）