data-structures - Haskell 的代数数据类型

Question

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

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

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

Answer 1

Haskell 的代数数据类型之所以如此命名，是因为它们对应于范畴论中的初始代数，为我们提供了一些法则、一些运算和一些要操作的符号。我们甚至可以使用代数符号来描述常规数据结构，其中:

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

带有一些附加符号:

• X² 代表 X•X

事实上，您可能会说(遵循 Brent Yorgey)，如果 Haskell 数据类型可以用 1、X、 表示，那么它就是常规数据类型+、• 和最小不动点。

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

• 单位:数据 () = ()

  1

• 选项:data Maybe a = Nothing |只是一个

  1 + X

• 列表:data [a] = [] |一个:[a]

  L = 1+X•L

• 二叉树:data BTree a = Empty |节点a(BTree a)(BTree a)

  B = 1 + X•B²

其他操作成立(摘自 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′

<小时/>

引用文献:

• Species and Functors and Types , Oh My!, Brent A. Yorgey, Haskell’10, 2010 年 9 月 30 日，美国马里兰州巴尔的摩
• Clowns to the left of me, jokers to the right (Dissecting Data Structures) , 康纳·麦克布莱德 POPL 2008