data-structures - "sums-and-products"数据结构是什么？

Question

一个recent blog post on William Cook's Fusings提及:

The key point is that structures in Ensō are viewed holistically as graphs, not as individual values or traditional sums-and-products data structures.

他指的传统的和与积数据结构是什么？

Answer 1

What are the traditional sums-and-products data structures he is referring to?

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

产品

乘积可以被认为是“结构”或“元组”的类型论 View 。

正式，PFPL，第 14 章:

The binary product of two types consists of ordered pairs of values, one from each type in the order specified. The associated eliminatory forms are projections, which select the first and second component of a pair. The nullary product, or unit, type consists solely of the unique “null tuple” of no values, and has no associated eliminatory form.

求和

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

PFPL，第 15 章:

Most data structures involve alternatives such as the distinction between a leaf and an interior node in a tree, or a choice in the outermost form of a piece of abstract syntax. Importantly, the choice determines the structure of the value. For example, nodes have children, but leaves do not, and so forth. These concepts are expressed by sum types, specifically the binary sum, which offers a choice of two things, and the nullary sum, which offers a choice of no things.

递归类型

除了乘积和和之外，我们还可以引入递归，因此类型可以(部分)根据其自身来定义。很好的例子包括树和列表。

 data List a = Empty | a : List a

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

和、乘积和递归的代数

给定一个类型，例如Int，我们就可以开始构建描述数据结构的代数表达式的符号:

孤立变量:

整数

两种类型的乘积(表示一对):

Int * Bool

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

整数+ bool <​​

还有一些常量:

1 + 整数

其中 1 是单位类型，()。

一旦您能够以这种方式描述类型，您就可以免费获得一些很酷的功能。首先，用于描述数据类型的非常简洁的符号，其次，一些结果从其他代数转移(例如 differentiation works on data structures )。

示例

单位类型，data () = ()

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

一个简单的求和类型，data Maybe a = Nothing |只是一个

及其替代方案，

还有一个递归类型，链表的类型:data [a] = [] |一个:[a]

鉴于这些，您可以通过组合求和、乘积和递归类型来构建相当复杂的结构。 例如。乘积和的乘积列表的简单表示法:[(Maybe ([Char], Double), Integer)] 产生了一些相当复杂的树:

<小时/>

引用文献

• 编程的实用基础 语言，罗伯特·哈珀，2011，http://www.cs.cmu.edu/~rwh/plbook/book.pdf
• 数据类型代数快速介绍，http://blog.lab49.com/archives/3011 (链接似乎已失效。互联网文件链接:http://web-old.archive.org/web/20120321033340/http://blog.lab49.com/archives/3011)
• 物种、仿函数和类型，天哪!，Brent Yorgey，http://www.cis.upenn.edu/~byorgey/papers/species-pearl.pdf -- 对代数、Haskell 数据类型以及与数学中的组合物种的联系有很好的概述。