Haskell代数数据类型

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

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

带有一些附加符号:

• X² 给 X•X

事实上,你可能会说(按照Brent Yorgey的说法),如果Haskell数据类型可以用以下表达式表示,那么它就是正则的 1. , 十、 , + , ,以及一个最不固定的点。

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

• 单位: data () = ()

  1.

• 选项: 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的论文,列于参考文献中):

• 扩展:展开固定点有助于思考列表。 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′

参考文献

• Species and Functors and Types 哦,天哪!,布伦特·约基,哈斯克尔,2010年9月30日,美国马里兰州巴尔的摩
• Clowns to the left of me, jokers to the right (Dissecting Data Structures) 康纳·麦克布赖德2008年流行歌曲

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

在……里面 universal algebra 一 代数 由几组元素组成 (将每组视为一种类型的值集) 以及一些将元素映射到元素的操作。

例如,假设你有一种“列表元素”和一个 “列表”的类型。作为操作,您有一个“空列表”,它是一个0参数 返回“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 但这就是疯狂。

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

@Timbo:

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

ADT(求和类型)也有点类似 tagged unions 或 variant types 在C或C++中。

老问题,但没有人提到可空性,这是代数数据类型的一个重要方面,也许是最重要的方面。由于每个值都是备选值之一,因此可以进行详尽的基于案例的模式匹配。

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

请看以下示例 http://en.wikipedia.org/wiki/Algebraic_data_types :

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

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

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