Haskell的代数数据类型

我正在努力完全理解Haskell的所有概念.

代数数据类型在哪些方面类似于泛型类型,例如在C#和Java中？它们有何不同？无论如何,他们有什么代数呢？

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

Haskell的代数数据类型被命名为,因为它们对应于类别理论中的初始代数,给出了一些定律,一些操作和一些操作符号.我们甚至可以使用代数表示法来描述常规数据结构,其中:

+表示总和类型(例如,不相交的联合Either).

• 代表产品类型(例如结构或元组)

X对于单身人士类型(例如data X a = X a)

1 对于单位类型 ()

并且?对于最不固定的点(例如递归类型),通常是隐含的.

用一些额外的表示法:

X² 对于 X•X

事实上,你可能会说(以下布伦特Yorgey)是一个Haskell数据类型是有规律的,如果它可以在来表示1,X,+,•,和至少一个动点.

使用这种表示法,我们可以简明地描述许多常规数据结构:

单位: 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?

参考文献:

种类和函数和类型,哦我的!,Brent A. Yorgey,Haskell'10,2010年9月30日,美国马里兰州巴尔的摩

我左边的小丑,右边的笑话(Dissecting Data Structures),Conor McBride POPL 2008

Haskell中的"代数数据类型"支持完整的参数多态,这是泛型的技术上更正确的名称,作为列表数据类型的一个简单示例:

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

是等价的(尽可能多,并忽略非严格的评价等)

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

data Bool = False | True

data Pair a b = Pair a b

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