什么是"总和产品"数据结构？

Question

一对威廉库克Fusings最近的一篇博客中提到:

关键点在于Ensō中的结构被整体地视为图形,而不是单个值或传统的和产品数据结构.

他所指的传统的产品和产品数据结构是什么？

Answer 1

他所指的传统的产品和产品数据结构是什么？

在类型理论中,可以用求和,乘积和递归类型来描述常规数据结构.这导致代数用于描述数据结构(以及所谓的代数数据类型).这种数据类型在静态类型的函数语言中很常见,例如ML或Haskell.

制品

产品可以被认为是"结构"或"元组"的类型理论视图.

正式地,PFPL,第14章:

两种类型的二进制乘积由有序的值对组成,每种类型按指定的顺序排列.相关的消除形式是投影,它选择一对的第一和第二组成部分.nullary产品或单元类型仅由没有值的唯一"null元组"组成,并且没有相关的消除形式.

总和

和类型表示数据结构的变体之间的选择.有时它们被称为"联合类型"(如在C中).许多语言都没有总和类型的概念.

PFPL,第15章:

大多数数据结构涉及替代方案,例如树中的叶子和内部节点之间的区别,或者抽象语法的最外层形式中的选择.重要的是,选择决定了值的结构.例如,节点有子节点,但叶子没有,等等.这些概念用和类型表示,特别是二元和,它提供了两种选择,而nullary和,它提供了无选择的选择.

递归类型

除了产品和总和之外,我们还可以引入递归,因此可以(部分地)根据自身定义类型.很好的例子包括树和列表.

 data List a = Empty | a : List a

 data Tree a = Nil | Node a (Tree a) (Tree a)

总和,产品和递归的代数

举一个类型,比方说Int,我们可以开始为描述数据结构的代数表达式构建一个表示法:

一个孤独的变量:

Int

两种类型的产品(表示一对):

Int * Bool

两种类型的总和(表示两种类型之间的选择):

Int + Bool

还有一些常数:

1 + Int

1单位类型在哪里().

一旦你能用这种方式描述类型,你就可以免费得到一些很酷的力量.首先,描述数据类型的非常简洁的符号,其次,一些结果从其他代数转移(例如,差异在数据结构上工作).

例子

单位类型, data () = ()

元组,最简单的产品类型:data (a,b) = (a,b)

简单的总和类型,data Maybe a = Nothing | Just a

和它的替代品,

和递归类型,链表的类型:data [a] = [] | a : [a]

鉴于这些,您可以通过组合总和,产品和递归类型来构建相当复杂的结构.例如,产品总和产品列表的简单表示法:[(Maybe ([Char], Double), Integer)]产生一些非常复杂的树:

参考

• 编程语言的实用基础,Robert Harper,2011,http://www.cs.cmu.edu/~rwh/plbook/book.pdf
• 快速介绍数据类型的代数,http://blog.lab49.com/archives/3011 (链接似乎已经死了)
• 物种和函数和类型,Oh My !, Brent Yorgey,http://www.cis.upenn.edu/~byorgey/papers/species-pearl.pdf - 对代数,Haskell数据类型有很好的概述,与数学中的组合物种的联系.

Answer 2

已经给出了非常详细的答案,但不知怎的,他们没有提到这个简单的事实.

调用Sum类型是因为sum类型的可能值的数量是两个基础类型的值的数量的总和.类似地,对于产品类型,可能的值的数量是产品.

这源于类型理论将类型定义为一组值.

data MySumType = Foo Bool | Bar Char
data MyProductType = Baz (Bool, Char)

• Bool是一组2个值.
• Char是一组256个值.
• MySumType是一组2 + 256个值.
• MyProductType是一组2*256个值.

现在你永远不会忘记哪个是哪个.

Answer 3

他指的是函数式编程语言的标准代数数据类型.

例子:

• 如果a是类型A且b属于类型,B则(a, b)属于类型A x B,这是产品类型.

• 与以下形式的值的列表类型Nil或Cons x xs为总和类型.

Ensō显然比这些树状代数类型更重视图形.