为什么“代数数据类型”在名称中使用“代数”这个词？

Question

当我学习Scala/Haskell时，我看到了代数数据类型的概念。我已经阅读了维基百科上的解释，但我仍然有一个问题：为什么它在名称中使用“代数”这个词？它与“代数”有什么关系吗？

- Freewind

Answer 1

简单地说，我们必须考虑代数和类型之间的关系。Haskell的代数数据类型被命名为这样，因为它们对应于范畴论中的初始代数。

维基百科说：

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

让我们以Maybe a数据类型为例:

data Maybe a = Nothing | Just a

也许 Maybe a 表示它可能包含某个类型的内容，例如 Just Int，但也可以为空 - Nothing。在 Haskell 中，类型是对象，例如 Int。运算符获取类型并生成新类型，例如 Maybe Int。代数指的是代数数据类型由代数运算（sums 和 product）创建的属性，其中:

• "sum" 是交替（A | B，表示 A 或 B 但不是两者都有）
• "product" 是组合（AB，表示 A 和 B 在一起）

例如，让我们来看看 Maybe a 的 sum。首先，让我们定义一个 Add 类型：

data Add a b = Left a | Right b

在Haskell中，|表示or，因此它可以是Left a或Right b。竖线|告诉我们，我们上面定义的Maybe是一个总和类型（sum type），这意味着我们可以使用Add来编写它：

type Maybe a = Add Nothing (Just a)

Nothing这里是一个unit类型：

在数学逻辑和计算机科学领域中，类型理论中的unit类型是一种只允许一个值的类型。

data Unit = Unit

或者在Haskell中使用()。

Just a是一种单例类型。单例类型是仅有一个值的类型。

data Just a = Just a

在此之后，我们可以将其重写为：

type Maybe a = Add () a

所以我们有单位类型 - 1，和单例类型 - a。现在我们可以说Maybe a与1 + a相同。

如果你想深入了解，请参考数据代数和变异微积分。

- 0xAX

---

链接已经失效。 - corvus_192

Answer 2

考虑类型 Bool。当然，这种类型只能取两个可能的值：True 或 False。

现在考虑。

data EitherBool = Left Bool | Right Bool

这种类型可以取多少个值？有4个： 左假，左真，右假，右真。那么呢？

data EitherBoolInt = Left Bool | Right Int8

这里左分支有2个可能的值，右分支有2^8个可能的值。因此，EitherBoolInt 有2+2^8种可能的取值。很容易看出，对于任何构造函数和类型集合，这种结构都能给你一个数据类型，其可能的取值空间大小等于每个单独构造函数的可能值之和，因此被称为和类型。

考虑以下情况。

data BoolAndInt = BAndI Bool Int8

或者只是简单地

type BoolAndInt = (Bool, Int)

这个可以取多少值？对于每一个可能的Int8，都有两个BoolAndInts，总共有2*2^8=2^9种可能的值。所有可能值的总数是构造函数每个字段值的乘积，因此这被称为乘积类型。

这个想法可以进一步扩展——例如，从a到b的函数是指数数据类型（参见代数数据类型的代数）。你甚至可以创建一个合理的数据类型导数概念。这甚至不是一个纯理论的想法——它是“拉链”功能构造的基础。参见数据类型的导数是其单孔上下文类型和维基百科条目关于拉链。

- Mark Whitfield

---

我阅读了整个答案，但仍不知道为什么代数类型被称为“代数”。你谈到了图像集的基数，但这个名称的由来是什么。 - problemofficer - n.f. Monica

Answer 3

相关问题：https://math.stackexchange.com/questions/50375/whats-the-meaning-of-algebraic-data-type 我的回答（在那里）：这都与代数理论有关。

- Vlad Patryshev