什麼是「和 - 產品」數據結構？

Question

甲recent blog post on William Cook's Fusings提到：

的關鍵點是，在ENSO結構整體上看作是曲線圖，而不是作爲單獨的數值或傳統總和和產品數據結構。

他指的是什麼傳統的總和和產品數據結構？

Answer 1

他指的傳統總和和產品數據結構是什麼？

在類型理論，常規數據結構可以在求和，產品和遞歸類型來描述。這導致用於描述數據結構的代數（以及所謂的代數數據類型）。這種數據類型在靜態類型函數語言中很常見，例如ML或Haskell。

產品

產品可被認爲是「結構」或「元組」的類型的理論圖。

形式上，PFPL，14章：

二進制產物兩種類型的由有序對值，一個來自 每種類型的順序SPECI音響版的。相關的消除形式是投影，它們選擇一對中的第一個和第二個分量。無限產品或單位類型僅由沒有值的唯一「空元組」組成，並且沒有相關的消除形式。

總結

薩姆類型表達的數據結構的變體之間的選擇。有時他們被稱爲「聯合類型」（如C）。許多語言沒有和類型的概念。

PFPL，CH 15：

大多數數據結構包括替代品，如一個 葉並以樹的內部節點時，或在一個 片抽象語法的最外形式的選擇之間的區別。重要的是，選擇決定了價值的結構 。例如，節點有孩子，但葉子沒有，所以第一個。這些概念用總和類型表示，特別是二進制數 總和，它提供了兩種選擇和零計數總和，它提供了一個沒有東西的選擇。

遞歸類型

隨着產品和總和，我們可以引入遞歸，所以一個類型可被定義（部分地）在其本身而言。很好的例子包括樹和列表。

data List a = Empty | a : List a 

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

資金，產品和遞歸的代數

給一個類型，比如說Int，我們就可以開始建立的，描述數據結構的代數表達式的符號：

一個孤獨的變量：

Int

一個produc兩種類型（表示一對）的T：

Int * Bool

兩種類型（表示兩種類型之間的選擇）的總和：

Int + Bool

而一些常量：

1 + Int

其中1是單位類型()。

一旦你可以用這種方式描述類型，你可以免費獲得一些很酷的功能。首先，用於描述數據類型的簡明表示法，其次是從其他代數轉移的結果（例如differentiation works on data structures）。

實例

單位類型，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
• 快速介紹alge數據類型的胸罩，http://blog.lab49.com/archives/3011（鏈接似乎是死）
• 物種和函子類型，噢，我的！布倫特Yorgey，http://www.cis.upenn.edu/~byorgey/papers/species-pearl.pdf - 有代數的一個很好的概述，哈斯克爾的數據類型，以及來自數學的組合物種的連接。

Answer 2

他指的是功能性編程語言的標準algebraic data types。

實例：

• 如果a是A類型的，並且是b類型B的然後(a, b)是A x B類型，這是一個product type的。

• 列表類型與形式Nil或Cons x xs的值是一個sum type。

Ensō顯然比這些樹狀代數類型更重視圖。

Answer 3

已經給出了非常詳細的答案，但不知何故，他們沒有提到這個簡單的事實。

薩姆類型稱爲所以因爲數可能值的總和類型的的是兩個基本類型的值的數量的總和。 同樣，對於產品類型，可能值的數量就是產品。

這源於類型理論，將類型定義爲一組值。

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

• 布爾是一組2個的值。
• Char是一組256個值。
• MySumType是一組2 + 256值。
• MyProductType是一組2 * 256值。

現在你永遠不會忘記哪個是哪個。

Answer 4

從Coursera課程的講義，由大學提供的「編程語言」。華盛頓州：

「爲什麼是積和？它與布爾代數有關，其中0爲假，1爲真，並且像乘法和或加法一樣工作。」