Haskell的代数数据类型

Question

Haskell的代数数据类型

data-structureshaskelltypesfunctional-programmingalgebraic-data-types

63

我正在尝试全面理解Haskell的所有概念。

代数数据类型与C＃和Java中的泛型类型有哪些相似之处？它们又有何不同之处？它们究竟有什么代数意义呢？

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

- marxidad

1

请参见https://dev59.com/FG025IYBdhLWcg3wl3O-#5914867。 - Don Stewart

8个回答

23

在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当然是和类型，构造函数提供字段的乘积/元组]

- olliej

3

泛型已经被用于很多不同的方式，唯一真正的共同点是“我的语言没有（或没有）的那种多态性，但我们计划添加（或已经添加）。 - wnoise

6

这个回答没有解释Haskell数据类型何以“代数”之意义。 - Don Stewart

1

实际上，我认为这个比喻并不完全正确 - data List a 是一个类型构造器，但 Cons 和 Nil 是数据构造器 - 它们表示类型为 List a 的值（这种区别很重要，因为它们存在于不同的命名空间中，所以你可以并且经常会有相同名称的类型和数据构造器）。 - Martin

20

在通用代数学中，一种代数由元素集合（将每个集合想象成一种值的集合）和一些操作组成，这些操作将元素映射到元素。

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

此时，有许多符合描述的代数，因为可能会发生两件不希望发生的事情：

- "列表"集合中可能存在无法从"空列表"和"cons操作"构建的元素，也称为"垃圾"。这可能是从天而降的一些元素开头的列表，没有起点的循环或无限列表。 - 应用于不同参数的"cons"结果可能相等，例如，在非空列表上应用cons将元素与空列表相连可能等于空列表。这有时被称为"混淆"。

具有这些不希望的属性的代数称为初始代数，这是抽象数据类型的预期含义。

"初始"一词来源于以下特性：从初始代数到任何给定代数都存在唯一的同态。基本上，您可以通过在其他代数中应用操作来评估列表的值，并且结果是明确定义的。

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

- starblue

12

它们被称为代数类型的一个简单原因是，它们既有和（逻辑析取）类型，也有积（逻辑合取）类型。求和类型是一种带标签的联合体，例如：

data Bool = False | True

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

data Pair a b = Pair a b

在O'Caml中，“product”更加明确：

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

- Porges

9

Haskell的数据类型被称为“代数”类型，因为它们与范畴论初等代数有关。但这条路会导致疯狂。

@olliej：ADT实际上是“和”类型。元组是乘积。

- Chris Conway

1

抽象数据类型（ADT）不仅仅是和类型（sum types）。 - Richard Simões

抽象数据类型是产品类型。它们在结构上同元组同构，除了它们的成员被标记。 - Mark Cidade

3

@Timbo:

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

ADT（求和类型）也有点像C或C++中的标记联合或变体类型。

- Jared Updike

我对“由于使用树数据类型的策略是…”感到困惑，这就是为什么不能将总和类型建模为继承（子）树的原因。您的操作分布在各个类中（基于类型的切换是模式匹配的子集），因此新节点将具有您在TreeNode类中定义的任何默认行为（或者您的语言定义的行为）-也许是一个错误，指示TreeNode是抽象的，并且您需要实现适当的方法。 - Frank Shearar

你肯定可以将每种类型的节点所需的操作作为（虚拟）成员函数添加到它上面。这就是面向对象编程的本质。 - vonbrand

2

这是一个常见问题，但没有人提到可空性，这是一种代数数据类型中非常重要的方面，也许是最重要的方面。由于每个值都必须是其中的某个选择，因此可以进行详尽的基于情况的模式匹配。

- ja

0

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

看看http://en.wikipedia.org/wiki/Algebraic_data_types中的例子：

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

这可以在C#中实现为一个TreeNode基类，带有一个派生的Leaf类和一个派生的TreeNodeWithChildren类，如果你想甚至还可以有一个派生的EmptyNode类。

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

- Timbo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Don Stewart · Accepted Answer

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

+表示和类型（不相交的联合，例如Either）。 •表示积类型（例如结构体或元组） X表示单例类型（例如data X a = X a） 1表示单位类型() μ表示最小不动点（例如递归类型），通常是隐含的。

还有一些附加符号：

X²表示X•X

实际上，您可以认为（跟随Brent Yorgey的说法），如果Haskell数据类型可以用1、X、+、•和最小不动点表示，则该数据类型是固定的。

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

单位类型：data()=()

Option类型：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在参考文献中列出的论文）：

展开：展开fix point可以帮助我们思考列表。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′

参考文献：

物种、函子和类型，Brent A. Yorgey，Haskell’10，2010年9月30日，美国马里兰州巴尔的摩
左边的小丑，右边的小丑（剖析数据结构），Conor McBride POPL 2008