代数データ型

コンピュータプログラミング、特に関数型プログラミングと型理論において、代数データ型( ADT ) は複合データ型の一種、つまり他の型を組み合わせて形成されるデータ型です。

代数型の一般的なクラスは、積型（タプル、レコード）と和型（タグ付きまたは分離した和、コプロダクト型、バリアント型）の2つです。^[1]

積型の値には通常、フィールドと呼ばれる複数の値が含まれます。その型のすべての値は、同じフィールド型の組み合わせを持ちます。積型のすべての可能な値の集合は、そのフィールド型のすべての可能な値の集合の集合論的積、 つまり直積です。

直和型の値は、通常、バリアントと呼ばれるいくつかのクラスにグループ化されます。バリアント型の値は、通常、コンストラクターと呼ばれる準機能エンティティを使用して作成されます。各バリアントには独自のコンストラクターがあり、指定された数の引数と指定された型を受け取ります。直和型の可能なすべての値の集合は、そのバリアントの可能なすべての値の集合の集合論的な和、つまり互いに素な和集合です。列挙型は直和型の特殊なケースで、コンストラクターは引数を受け取らず、各コンストラクターに正確に 1 つの値が定義されます。

代数型の値はパターン マッチングを使用して分析され、コンストラクタまたはフィールド名によって値が識別され、含まれるデータが抽出されます。

代数的データ型は、1970年代にエディンバラ大学で開発された小さな関数型プログラミング言語であるHopeで導入されました。^[2]

代数データ型の最も一般的な例の 1 つは、単方向リンク リストです。リスト型は、Nil空のリストと、新しい要素xとリストxsを組み合わせて新しいリストを作成する 2 つのバリエーションを持つ合計型です。以下は、 Haskellで単方向リンク リストを宣言する方法の例です。 Cons x xs

データリストa = Nil | Cons a (リストa )         

または

データ[] a = [] | a : [ a ]        

Consはconstructの省略形です。多くの言語では、このように定義されたリストに対して特別な構文を持っています。たとえば、Haskell とML では、それぞれ に 、に[]を使用し、リスト全体には角括弧を使用します。したがって、通常は Haskell ではまたはと記述され、 ML ではまたはと記述されます。 Nil:::ConsCons 1 (Cons 2 (Cons 3 Nil))1:2:3:[][1,2,3]1::2::3::[][1,2,3]

もう少し複雑な例として、バイナリツリーは次のように Haskell で実装できます。

データツリー=空|リーフInt |ノードIntツリーツリー   
            
              

または

データBinaryTree a = BTNil | BTNode a ( BinaryTree a ) ( BinaryTree a )    
                        

ここで、Emptyは空のツリーを表し、Leafはリーフ ノードを表し、Nodeデータはブランチに編成されます。

代数データ型をサポートするほとんどの言語では、パラメトリック型を定義することができます。例はこの記事の後半で示します。

関数に多少似ていますが、データ コンストラクターは適切な型の引数に適用され、型コンストラクターが属するデータ型のインスタンスを生成します。たとえば、データ コンストラクターはLeaf論理的には関数でありInt -> Tree、つまり、引数として整数を与えると、Leaf型の値が生成されます。 は型自体の引数を 2 つ取るTreeため、データ型は再帰的です。 NodeTree

代数データ型の操作は、パターン マッチングを使用して引数を取得することで定義できます。たとえば、TreeHaskell で次のように表される a の深さを見つける関数を考えてみましょう。

深さ:: Tree -> Int深さ空= 0深さ(葉n ) = 1深さ(ノードn l r ) = 1 +最大(深さl ) (深さr )    
   
    
            

したがって、 から は、、のいずれかを使用して構築できTree、すべてのケースを処理するには、 がそれぞれいずれかに一致している必要があります。 の場合、パターンはサブツリーと を抽出し、さらに処理します。 depthEmptyLeafNodeNodelr

代数データ型は抽象構文の実装に非常に適しています。たとえば、次の代数データ型は数値式を表す単純な言語を記述します。

データ式=数値Int |加算式式|減算式式|乗算式式|除算式式    
                   
                   
                   
                   

このようなデータ型の要素は、 のような形式になりますMult (Add (Number 4) (Minus (Number 0) (Number 1))) (Number 2)。

この言語の評価関数を書くのは簡単な作業ですが、より複雑な変換も実行可能になります。たとえば、コンパイラの最適化パスは、抽象式を入力として受け取り、最適化された形式を返す関数として記述できます。

代数データ型は、いくつかの種類のものの 1 つである値を表すために使用されます。それぞれの種類のものは、コンストラクタと呼ばれる識別子に関連付けられており、その種類のデータのタグと考えることができます。各コンストラクタは、異なる種類のデータを運ぶことができます。

たとえば、Tree上記のバイナリの例を考えると、コンストラクターはデータを持たない場合 (例: Empty)、1 つのデータを持つ場合 (例: にはLeaf1 つの Int 値がある)、または複数のデータを持つ場合 (例: にはNode2 つのTree値がある) があります。

Treeこの代数データ型の値を使用して何かを行うには、パターン マッチングと呼ばれるプロセスを使用して分解します。これには、一連のパターンとデータのマッチングが含まれます。上記の例の関数は、引数を 3 つのパターンとパターン マッチングします。関数が呼び出されると、引数に一致する最初のパターンが検索され、パターン内で見つかった変数バインディングが実行され、パターンに対応する式が評価されます。 depth

上記の各パターンは、このデータ型の可能な値の構造に似た形式になっています。最初のパターンは、単にコンストラクターの値と一致します。2Empty番目のパターンは、コンストラクターの値と一致しますLeaf。パターンは再帰的であるため、そのコンストラクターに関連付けられているデータは、パターン "n" と一致します。この場合、小文字の識別子は、任意の値と一致するパターンを表し、その名前の変数にバインドされます。この場合、変数 " n" は、データ型に格納されている整数値にバインドされ、式の評価に使用されます。

この例のパターンの再帰は単純ですが、より複雑な再帰パターンは次のようになります。

Node (Node (Leaf 4) x) (Node y (Node Empty z))

数層深い再帰パターンは、例えば、数層深い色を調べる必要があるケースを含む 赤黒木のバランスをとる場合に使用されます。

上記の例は、操作的には次の疑似コードと同等です。

switch  on  ( data .コンストラクタ) 
  case  Empty : 
    return  0 
  case  Leaf : 
    let  n  =  data . field1 
    return  1 
  case  Node : 
    let  l  =  data . field1 
    let  r  =  data . field2 
    return  1  +  max  ( depth  l )  ( depth  r )

代数データ型の利点は、上記の疑似コードと同等のパターン マッチング コードを比較することで強調できます。

まず、型安全性があります。上記の擬似コードの例では、プログラマーはアクセスしないように注意する必要があります。フィールド2コンストラクタが の場合Leaf。また、フィールド1Leafと では異なりますNode。Leaf では中級しかしNodeの場合は木型システムでは、従来のレコードデータ構造に対して静的型を安全に割り当てることが困難です。ただし、パターン マッチングでは、このような問題は発生しません。抽出された各値の型は、関連するコンストラクターによって宣言された型に基づきます。抽出できる値の数は、コンストラクターに基づいてわかります。

第二に、パターン マッチングでは、コンパイラはすべてのケースが処理されることを確認するために網羅性チェックを実行します。上記のdepth関数のケースの 1 つが欠落している場合、コンパイラは警告を発します。網羅性チェックは単純なパターンでは簡単に思えるかもしれませんが、複雑な再帰パターンが多数ある場合、平均的な人間 (または、任意のネストされた if-else 構造をチェックする必要がある場合はコンパイラ) にとってすぐに難しい作業になります。同様に、決して一致しないパターン (つまり、以前のパターンで既にカバーされている) が存在する場合があります。コンパイラは、推論のエラーを示している可能性があるため、これらをチェックして警告を発することもできます。

代数データ型のパターン マッチングを正規表現の文字列パターン マッチングと混同しないでください。両者の目的は似ていますが (特定の制約に一致するデータの一部を抽出する)、実装は大きく異なります。代数データ型のパターン マッチングは、文字列の文字シーケンスではなく、オブジェクトの構造プロパティに一致します。

一般的な代数的データ型は、積型の可能な限り再帰的な和型です。各コンストラクタは積型にタグを付けて他の積型と区別します。コンストラクタが 1 つしかない場合は、データ型は積型です。さらに、コンストラクタのパラメータ型は積型の因数です。パラメータなしのコンストラクタは空の積に対応します。データ型が再帰的である場合、積の和全体が再帰型でラップされ、各コンストラクタもデータ型を再帰型にロールします。

たとえば、Haskell データ型:

データリストa = Nil | Cons a (リストa )         

は、型理論では コンストラクタやと同様に 表現されます。 ${\displaystyle \lambda \alpha .\mu \beta .1+\alpha \times \beta }$${\displaystyle \mathrm {nil} _{\alpha }=\mathrm {roll} \ (\mathrm {inl} \ \langle \rangle )}$${\displaystyle \mathrm {cons} _{\alpha }\ x\ l=\mathrm {roll} \ (\mathrm {inr} \ \langle x,l\rangle )}$

Haskell の List データ型は、型理論ではわずかに異なる形式で表現することもできます。つまり、 です。 (と の構成が元の形式と逆になっていることに注意してください。) 元の形式は、本体が再帰型である型関数を指定していました。改訂版では、型の再帰関数を指定します。( はギリシャ文字のfに似ているため、型変数は、のような基本型ではなく関数を示すために使用されます。) 関数は、型の本体で引数の 型にも適用する必要があります。${\displaystyle \mu \phi .\lambda \alpha .1+\alpha \times \phi \ \alpha }$${\displaystyle \mu }$${\displaystyle \lambda }$${\displaystyle \phi }$${\displaystyle \beta }$${\displaystyle \phi }$${\displaystyle \phi }$${\displaystyle \alpha }$

リストの例では、これら 2 つの定式化に大きな違いはありませんが、2 番目の形式では、いわゆるネストされたデータ型、つまり再帰型が元の型とパラメータ的に異なるデータ型を表現できます。(ネストされたデータ型の詳細については、Richard Bird、Lambert Meertens、および Ross Paterson の著作を参照してください。)

集合論では、和型に相当するものは、タグ（コンストラクタに相当）とタグに対応する型のオブジェクト（コンストラクタ引数に相当）のペアを要素とする集合である、互いに素な和集合である。 ^[3]

多くのプログラミング言語では、次のような代数データ型が第一級の概念として組み込まれています。

• 不連続和集合
• 一般化された代数データ型
• 初期代数
• 商型
• タグ付きユニオン
• 型理論
• 訪問者パターン