Haskell的代数数据types

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

与通用types类似的代数数据types是什么方式，例如，在C＃和Java中？ 他们有什么不同？ 他们有什么代数的呢？

我熟悉通用代数及其环和领域，但我只是对Haskelltypes的工作有一个模糊的概念。

Answer 1

Haskell中的“代数数据types”支持全参数多态 ，这是generics中技术上更加正确的名称，作为列表数据types的一个简单示例：

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的types系统允许更多…有趣的使用types参数，但这只是一个简单的例子。 关于“代数types”这个名字，我从来没有完全确定他们被命名的确切原因，但是认为这是types系统的math基础。 我相信这个理由归结为一个ADT的理论定义是“一组构造者的产物”，然而，自从我逃离大学已经过了几年，所以我不能再记得具体的东西了。

[编辑：感谢克里斯·康威指出我的愚蠢的错误，ADT当然是总和types，构造提供产品/字段的元组]

Answer 2

Haskell的代数数据types被命名为这样，因为它们对应于类别理论中的初始代数 ，给我们一些规则，一些操作和一些符号来操纵。 我们甚至可以使用代数符号来描述常规的数据结构，其中：

• +表示总和types（不相交的联合，例如Either ）。
• •表示产品types（例如结构或元组）
• X为单例types（例如data X a = X a ）
• 1为单位types()
• 和μ为最不动点（例如recursiontypes），通常是隐含的。

附加一些符号：

• X•X

实际上，如果可以用1 ， X ， + ， •和最不固定的点来表示一个Haskell数据types，那么您可能会说（按照Brent Yorgey的说法）。

用这个表示法，我们可以简洁地描述许多常规的数据结构：

• 单位： data () = ()

  1

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

  1 + X

• 列表： data [a] = [] | a : [a] data [a] = [] | a : [a]

  L = 1+X•L

• 二叉树： data BTree a = Empty | Node a (BTree a) (BTree a) data BTree a = Empty | Node a (BTree a) (BTree a)

  B = 1 + X•B²

其他行动持有（摘自Brent Yorgey的论文，在参考文献中列出）：

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

• 成分◦给定typesF和G ，成分F ◦ G是一种构build“由G结构构成的F结构”的types（例如R = X • (L ◦ R) ，其中L是列表，是玫瑰树。

• 微分，数据typesD的导数（以D'给出）是具有单个“洞”的D结构的types，即不包含任何数据的区别位置。 这惊人地满足与微积分中的分化相同的规则：

  1′ = 0

  X′ = 1

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

  (F • G)′ = F • G′ + F′ • G

  (F ◦ G)′ = (F′ ◦ G) • G′

---

参考文献：

• 物种和函数和types ，哦，我！，布伦特A. Yorgey，哈斯克尔2010年9月30日，美国马里兰州巴尔的摩
• 小丑在我左边，笑话在右边（解剖数据结构） ，Conor McBride POPL 2008

Answer 3

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

例如，假设你有一个“列表元素”types和一个“列表”types。 作为操作，你有“空列表”，它是一个返回“列表”的0参数函数和一个带有两个参数“列表元素”和“列表”的“cons”函数，并产生一个“列表”。

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

• 在“列表”中可能有元素不能从“空列表”和“缺点操作”，即所谓的“垃圾”build立。 这可能是从一些从天而降的元素开始的列表，或者是没有开始的循环，或者是无限的列表。

• 应用于不同参数的“cons”的结果可以是相等的，例如，将元素包含到非空列表可以等于空列表。 这有时被称为“混乱”。

既不具有这些不良特性的代数称为初始 ，这是抽象数据types的预期含义。

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

对于多态types它变得更复杂

Answer 4

他们被称为代数的一个简单的理由; 有sum（逻辑分离）和product（逻辑连接）两种types。 总和types是一个有区别的联盟，例如：

 data Bool = False | True 

产品types是具有多个参数的types：

 data Pair ab = Pair ab 

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

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

Answer 5

Haskell的数据types被称为“代数”，因为它们连接到分类的初始代数 。 但那样就是疯狂。

@olliej：ADT实际上是“和”types。 元组是产品。

Answer 6

@Timbo：

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

ADT（求和types）也有点像C或C ++中的带标签的联合体或变体types 。

Answer 7

老问题，但没有人提到可空性，这是代数数据types的一个重要方面，也许是最重要的一个方面。 由于每个值最可能是其中一种select，因此可以使用详尽的基于案例的模式匹配。

Answer 8

对我来说，Haskell的代数数据types的概念总是看起来像OO语言（如C＃）中的多态。

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

 data Tree = Empty | Leaf Int | Node Tree Tree 

这可以在C＃中作为TreeNode基类实现，具有派生的Leaf类和派生的TreeNodeWithChildren类，如果你想要一个派生的EmptyNode类。

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