代數數據類型

在計算機編程中，特別是函數式編程和類型理論中，代數數據類型（ADT）是一種復合類型，即由其他類型組合而成的類型。

兩類常見的代數類型是乘積類型（即圖元和記錄）和總和類型（即標記的或不相交的聯合體、共產品類型或變體類型）。一個產品類型的值通常包含幾個值，稱為字段。該類型的所有值都有相同的字段類型組合。一個乘積類型的所有可能值的集合是其字段類型的所有可能值的集合的集合論乘積，即笛卡爾乘積。一個總和類型的值通常被分組為幾個類別，稱為變體。

一個變體類型的值通常是用一個叫做構造器的準功能實體創建的。每個變體都有自己的構造函數，它接受指定數量的參數，并具有指定的類型。和類型的所有可能值的集合是其變體的所有可能值的集合的集合論之和，即不相連的聯合。枚舉類型是和類型的一個特例，其中構造函數不需要參數，因為每個構造函數只定義一個值。

代數類型的值是用模式匹配來分析的，它通過構造函數或字段名來識別一個值，并提取它所包含的數據。

代數數據類型是在Hope中引入的，Hope是20世紀70年代在愛丁堡大學開發的一種小型函數式編程語言。

代數數據類型最常見的例子之一是單鏈表。列表類型是一種和類型，有兩個變體，Nil表示空列表，Consxxs表示新元素x與列表xs的組合，以創建一個新列表。下面是一個用Haskell聲明單鏈表的例子。Cons是construct的縮寫。

許多語言對以這種方式定義的列表有特殊的語法。例如，Haskell和ML分別用[]表示無，用:或:表示Cons，用方括號表示整個列表。所以Cons1(Cons2(Cons3Nil))在Haskell中通常寫成1:2:3:[]或[1,2,3]，或者在ML中寫成1::2::3:[]或[1,2,3]。對于一個稍微復雜的例子，二叉樹可以在Haskell中實現如下。這里，Empty代表一棵空樹，Leaf包含一段數據，Node將數據組織成分支。

在大多數支持代數數據類型的語言中，都可以定義參數化類型。本文后面會給出一些例子。

與函數有點類似，數據構造函數被應用于適當類型的參數，產生一個類型構造函數所屬的數據類型的實例。例如，數據構造函數Leaf在邏輯上是一個Int->Tree的函數，意味著給Leaf一個整數作為參數會產生一個Tree類型的值。

由于Node需要兩個Tree類型本身的參數，該數據類型是遞歸的。對代數數據類型的操作可以通過使用模式匹配來檢索參數來定義。

例如，考慮一個查找Tree深度的函數，這里用Haskell給出。因此，給定深度的Tree可以使用Empty、Leaf或Node中的任何一種來構造，并且必須分別匹配其中的任何一種來處理所有情況。

在Node的情況下，該模式會提取子樹l和r進行進一步處理。代數數據類型非常適用于實現抽象語法。例如，下面的代數數據類型描述了一種代表數字表達的簡單語言。為這種語言編寫一個評估函數是一個簡單的練習；然而，更復雜的轉換也變得可行。

例如，編譯器中的優化通道可以寫成一個函數，將抽象表達式作為輸入，并返回一個優化形式。

發生的情況是，有一個數據類型，它可以是幾種類型的事物之一。每種類型的事物都與一個叫做構造函數的標識符相關聯，它可以被看作是該種數據的一種標簽。

每個構造函數可以攜帶不同類型的數據。一個構造函數可以不攜帶任何數據（例如，上面的例子中的Empty），或者攜帶一個數據（例如，"Leaf"有一個Int值），或者攜帶多個數據（例如，"Node"有兩個Tree值）。