代数的データ型

代数的データ型とは

代数的データ型（Algebraic Data Type, ADT）は、プログラミング、特に関数型プログラミングや型システムにおいて利用されるデータ型です。これは、一つ以上のコンストラクタを持ち、各コンストラクタはゼロ個以上の引数を取ることができます。代数的データ型の値は、コンストラクタによって他のデータ型の値を包み込むようにして生成されます。コンストラクタが引数を取る場合、それは複合型とみなされます。

概要

例として、Haskellにおける二分木を考えてみましょう。この二分木は、葉に整数型の値を持ち、分岐は部分木のみを持ちます。以下のように`data`宣言を用いてデータ型を定義します。

haskell
data Node = Leaf Integer | Branch Node Node


この宣言では、`Node`という名前の型を定義しています。`|`記号は、異なるコンストラクタの形状を区切ります。`Leaf`と`Branch`はコンストラクタです。`Leaf`コンストラクタは`Integer`型の引数を一つ取り、`Branch`コンストラクタは二つの`Node`型の引数を取ります。これは再帰データ型の例でもあります。

Haskellのインタプリタghciで、この型の値を入力して表示する例を次に示します。

haskell
Main> Leaf 1
Leaf 1
Main> Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4))
Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4))


データにアクセスするにはパターンマッチングを使用します。例えば、木の深さを返す関数は次のようになります。

haskell
depth :: Node -> Int
depth (Leaf _) = 1
depth (Branch a b) = 1 + max (depth a) (depth b)

応用

多くの関数型言語では、リスト型が組み込みで提供されています。リスト型も代数的データ型の例であり、空リストを表すコンストラクタと、要素と残りのリストを引数に取るコンストラクタを持ちます。代数的データ型の特殊な例として、直積型（一つのコンストラクタのみを持つ）や列挙型（引数なしの複数のコンストラクタを持つ）が挙げられます。

上記の二分木の例では、コンストラクタ`Leaf`は`Integer -> Node`の型を持ち、`Branch`は`Node -> Node -> Node`の型を持ちます。型だけを見ると関数型のように見えますが、コンストラクタは値を構築するためのものであり、関数のように評価されるものではありません。これはオブジェクト指向言語のコンストラクタとは異なります。

関数型言語では、モジュールシステムを用いてコンストラクタを隠蔽し、型のみを公開することで抽象データ型を実現できます。コンストラクタの代わりに、対応する引数を取り目的の型の値を返す関数を公開することができます。この関数が、オブジェクト指向言語のコンストラクタに相当します。

他の言語での例

OCamlでは、ヴァリアント型を使って同様のデータ型を表現します。

ocaml
type node = Leaf of int | Branch of node * node


伝統的なMLでは`datatype`キーワードが用いられます。MLではコンストラクタは大文字で始めますが、型名は小文字で始めます。OCamlでの例を次に示します。

ocaml

Leaf 1;;

• - : node = Leaf 1

Branch (Branch (Leaf 1, Leaf 2), Branch (Leaf 3, Leaf 4));;

• - : node = Branch (Branch (Leaf 1, Leaf 2), Branch (Leaf 3, Leaf 4))

let rec depth tree = match tree with
| Leaf _ -> 1
| Branch (a, b) -> 1 + max (depth a) (depth b)


Visual Prologでは、以下のように記述できます。

prolog
domain
tree = empty; leaf(integer); node(tree, tree).


この例では、空の木を表す`empty`もコンストラクタとして定義されています。

理論

集合論において、代数的データ型は直和に対応します。直和の各要素は、タグ（コンストラクタに相当）と、そのタグに対応する型のオブジェクト（コンストラクタの引数に相当）で構成されます。一般的に、代数的データ型は直積型の総和であり、再帰的に定義されることもあります。各コンストラクタは、直積型のタグとして機能し、他と区別されます。

例えば、Haskellのデータ型

haskell
data List a = Nil | Cons a (List a)


は、型理論的に次のように表現できます。


List α = μϕ. 1 + α × ϕ


コンストラクタは次のように表現できます。


Nil : List α
Cons : α → List α → List α


この`List`型を別の形式で表現すると、次のようになります。


μ(λϕ. 1 + α × ϕ)


`μ`と`λ`の順序が入れ替わっていることに注意してください。前者は再帰型を本体とする型関数の定義であり、後者は型の再帰関数定義です。

型変数`ϕ`は、これが基本型ではなく関数型であることを示しています。また、引数型`α`に関数`ϕ`を適用する必要があることに注意してください。

これらの2つの定式化には大きな違いはありませんが、後者の形式は「入れ子データ型」を可能にします。入れ子データ型とは、オリジナルのデータ型とパラメータ的に異なる再帰型を派生させるものです。

まとめ

代数的データ型は、関数型プログラミングにおいて非常に重要な概念であり、データの構造を明確に表現し、安全なデータ操作を可能にします。その柔軟性と表現力により、複雑なデータ構造を扱いやすくし、プログラムの信頼性を向上させることができます。

もう一度検索