Haskell的代数数据类型

Haskell支持中的“代数数据类型” 全参数多态性 ,这是更准确的泛型名称,作为一个简单示例,list数据类型:

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

相当于(尽可能多,忽略不严格的评估等)

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

当然,哈斯克尔的类型系统允许更多…类型参数的使用很有趣,但这只是一个简单的例子。关于“代数类型”的名称,老实说,我从来没有完全确定它们被命名为“代数类型”的确切原因,但我认为这是由于类型系统的数学基础。我 相信 原因可以归结为ADT的理论定义是“一组建设者的产品”,然而,我从大学毕业已经有几年了,所以我再也记不起细节了。

[编辑:感谢ChrisConway指出了我的愚蠢错误,ADT当然是SUM类型,构造函数提供了字段的产品/元组]

哈斯克尔 代数数据类型 因为它们对应于 初始代数 在范畴论中,给我们一些规律,一些操作和一些符号来操纵。我们甚至可以使用代数符号来描述规则数据结构,其中:

• + 表示总和类型(不相交的联合,例如 Either )
• • 表示产品类型(例如结构或元组)
• X 对于单件类型(例如 data X a = X a )
• 1 对于机组类型 ()
• 和 μ 对于最不固定的点(例如递归类型),通常是隐式的。

加上一些附加符号:

• X² 对于 X•X

事实上,您可能会说(遵循布伦特·约尔基),如果haskell数据类型可以表示为 一 , X , + , 以及一个最不固定的点。

使用这个符号,我们可以简明地描述许多常规数据结构:

• 单位: data () = ()

  一

• 选项: 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²

其他业务保留(摘自布伦特·约基的论文,见参考文献):

• 扩展:展开固定点有助于思考列表。 L = 1 + X + X² + X³ + ... (也就是说,列表要么是空的,要么有一个元素,要么有两个元素,要么有三个,要么……)

• 构图, ◦ 给定类型 F 和 G ,组成 F ◦ G 是一种构建由G结构(例如 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 哦,我的天哪!,Brent A.Yorgey,Haskell10,2010年9月30日,美国马里兰州巴尔的摩
• Clowns to the left of me, jokers to the right (Dissecting Data Structures) ,Conor McBride Popl 2008年

在 universal algebra 安 代数 由若干组元素组成 (将每一组都视为一个类型的值集) 以及一些将元素映射到元素的操作。

例如,假设您有“list elements”类型和 “列表”的类型。作为操作,您有“空列表”,这是一个0参数 返回“list”和接受两个参数的“cons”函数的函数, 一个“列表元素”和一个“列表”,并生成一个“列表”。

此时有许多代数符合描述, 因为可能会发生两件不受欢迎的事情:

• “list”集合中可能有无法生成的元素 从“空列表”和“cons操作”中,所谓的“垃圾”。 这可能是一些从天空落下的元素开始的列表, 或者没有开始的循环,或者无限列表。

• 应用于不同论点的“反对”结果可能是相等的, 例如,将元素考虑到非空列表中 可能等于空列表。这有时被称为“困惑”。

一个既没有这些不良性质的代数叫做 最初的 ,这是抽象数据类型的预期含义。

名称的初始值来自 从初等代数到任何给定代数的同态。 本质上,您可以通过应用操作来评估列表的值。 在另一个代数中,结果是明确的。

对于多态类型来说,它变得更加复杂…

它们被称为代数的一个简单原因;有和(逻辑析取)和积(逻辑合取)两种类型。求和类型是一个有区别的联合,例如:

data Bool = False | True

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

data Pair a b = Pair a b

在O'Caml中,“产品”更加明确:

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

由于haskell的数据类型与 categorical initial algebras . 但这就是疯狂。

@奥利:ADT实际上是“求和”类型。元组是产品。

@ Timbo:

你基本上是对的,它有点像一个抽象的树类,有三个派生类(空类、叶类和节点类),但是你也需要强制保证使用树类的人永远不能添加任何新的派生类,因为使用树数据类型的策略是写代码,在运行时基于n树中每个元素的类型(添加新的派生类型将破坏现有代码)。你可以想象这在C语言或C++中变得很讨厌,但是在Haskell、ML和OcAML中,这是语言设计和语法的核心,所以编码风格通过模式匹配更方便地支持它。

ADT(SUM类型)也有点像 tagged unions 或 variant types 在C或C++中。

旧问题,但没有人提到空性,这是代数数据类型的一个重要方面,也许是最重要的方面。由于每个值都是可选的,因此完全基于案例的模式匹配是可能的。

对我来说,haskell的代数数据类型的概念在像c_这样的OO语言中总是看起来像多态性。

看看下面的例子 http://en.wikipedia.org/wiki/Algebraic_data_types :

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

这可以在C中实现为TreeNode基类,具有派生的Leaf类和派生的TreeNodeWithChildren类,如果您甚至想要派生的EmptyNode类。

(好吧,我知道,没人会这么做,但至少你能做到。)