代数的データ型のソースを表示

'''代数的データ型'''（だいすうてきデータがた、{{lang-en-short|algebraic data type}}）とは[[プログラミング (コンピュータ)|プログラミング]]、特に[[関数型言語|関数型プログラミング]]や[[型システム]]において使われる[[データ型]]である。それぞれの代数的データ型の[[値 (情報工学)|値]]には、1個以上の[[コンストラクタ]]があり、各コンストラクタには0個以上の[[引数]]がある。

代数的データ型の値（データ）の感覚的な説明としては、引数で与えられた他のデータ型の値を、コンストラクタで包んだようなもの、である。コンストラクタに引数がある代数データ型は複合型（他のデータ型を組み合わせて形成する型）である。

== 概要 ==
[[Haskell]]における、葉に整数型の値を持つ（分岐は部分木しか持たない）、[[二分木]]の例で説明する。以下のようなdata宣言で、データ型を宣言する。

<syntaxhighlight lang="haskell">
data Node = Leaf Integer | Branch Node Node
  deriving (Show)  -- 表示させて確認するために付加してあるもので、必須ではない。
</syntaxhighlight>

この宣言でNodeという名前の型を宣言している（Haskellでは型名の先頭は大文字でなければならない）。縦棒（"|"）で区切って、各コンストラクタによる形を並べる。LeafとBranchはコンストラクタ（データコンストラクタ）である。コンストラクタLeafは1個のIntegerを引数として取り、Branchは2個のNodeを引数として取る（[[再帰データ型]]の例にもなっている）。Haskellではコンストラクタの名前も、先頭は大文字でなければならない（ここでは避けたが、型とコンストラクタに同じ名前を使っても構わない）。

Haskellインタプリタghciで、この型の値を入力し表示させた例を示す。

 *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))

中のデータにアクセスするには[[パターンマッチング]]を使う。ここで定義した型の木の深さを返す関数の例で次に示す。

<syntaxhighlight lang="haskell">
depth tree = case tree of
  Leaf _     -> 1
  Branch a b -> 1 + max (depth a) (depth b)
</syntaxhighlight>

== 応用 ==
基本的な代数データ型としては、多くの関数型言語において、言語組み込みのリスト型が用意されており、空リストのためのコンストラクタに相当する[[リテラル]]と、追加したい要素と残りのリストを引数に取るコンストラクタ（Lispの[[:en:cons]]）に相当する、[[中置記法]]風のコンストラクタ（ ":" など）が言語組み込みで用意されている。

代数的データ型の特殊な例として、直積型（1つのコンストラクタだけを持つ）と列挙型（引数なしの多くのコンストラクタを持つ）がある。

前述の二分木の例において、コンストラクタLeafは Integer -&gt; Node という型を、コンストラクタBranchは Node -&gt; Node -&gt; Node という型を持つ。型のみを見た場合、関数と同じ型をしている。しかし、関数とは違いコンストラクタは単にそこにあるだけのものであり、評価（実行）されるものではなく、オブジェクト指向言語におけるコンストラクタとは異なる。式として見た場合、関数に引数を適用する式は簡約可能だが、コンストラクタによる式は全体としてはそれ以上簡約できない、値をあらわす式である。

関数型言語で[[抽象データ型]]を実現する手法のひとつに、モジュールシステムによるスコープ制限を利用して、コンストラクタを掩蔽し、型のみを公開する、という手法がある。データコンストラクタそのものの代わりに、相当する引数をとって、目的の型の値を返すような、コンストラクタを抽象化した関数を定義し、そちらの関数を公開する。この関数が、オブジェクト指向言語におけるコンストラクタに相当する。

== 他の言語での例 ==
[[OCaml]]ではヴァリアント型と言い、前述の二分木と同等のデータ型は、次のように書く。

<syntaxhighlight lang="ocaml">
 type node = Leaf of int | Branch of node * node
</syntaxhighlight>

また、伝統的な[[ML (プログラミング言語)|ML]]ではdatatypeというキーワードを使う。いずれも、ofの後に1個しか型を指定できないので、Branchのように組み込みの直積型である[[タプル]]を併用する必要がある。MLでもコンストラクタの先頭は大文字だが、型名の先頭は小文字である。

Haskellの場合と同様にして、インタプリタ上で値を作る例と深さを返す関数の例を示す。

 # 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]]では次のように書く。

<syntaxhighlight lang="visualprolog">
 domains
 tree =
 empty();
 leaf(integer Leaf);
 node(tree Left, tree Right).
</syntaxhighlight>

この例では、leafとnodeの他に、空の木を示すemptyがある。

== 理論 ==
[[集合論]]において代数的データ型と等価なものとして[[直和#集合の直和|直和]]がある。この集合の各元はタグ（コンストラクタと等価）とそのタグに対応する型のオブジェクト（コンストラクタの引数と等価）で構成される。

一般に代数的データ型は直積型の総和であり、再帰的に定義されることもある。各コンストラクタは直積型のタグとなって他と区別されるか、1つしかコンストラクタがない場合は、そのデータ型自体が直積型となる。さらにコンストラクタの引数の型が直積型の要素となる。引数のないコンストラクタは空に対応する。データ型が再帰的であるなら、その直積型の総和は[[再帰データ型]]となり、各コンストラクタによって再帰データ型が構成される。

例えば、以下のような Haskell のデータ型

<syntaxhighlight lang="haskell">
  data List a = Nil | Cons a (List a)
</syntaxhighlight>

を[[型理論]]的に表すと次のようになる。

{{Indent|<math>\lambda \alpha. \mu \beta. 1 + \alpha \times \beta</math>}}

コンストラクタは次のようになる。
{{Indent|
<math>\mathrm{nil}_\alpha = \mathrm{roll}\ (\mathrm{inl}\ \langle\rangle)</math><br />
<math>\mathrm{cons}_\alpha\ x\ l = \mathrm{roll}\ (\mathrm{inr}\ \langle x, l\rangle)</math>
}}
この Haskell の List 型を型理論の別の形式で表すと、次のようになる。

{{Indent|<math>\mu \phi. \lambda a. 1 + \alpha \times \phi\ \alpha</math>}}

<math>\mu</math> と <math>\lambda</math> が2つの定義で順序が入れ替わっている点に注意されたい。前者の形式は再帰型を本体とする型関数の定義であり、後者は型の再帰関数定義である。型変数 <math>\phi</math> は、これが <math>\beta</math> のような基本型ではなく関数型であることを示している（<math>\phi</math> はギリシャ文字で "f" に相当する）。また、型本体の中の引数型 <math>\alpha</math> に関数 <math>\phi</math> を適用しなければならない。

List の例の用途から考えると、これら2つの定式化に大きな違いはないが、後者の形式は「入れ子データ型; nested data type」と呼ばれる表現を可能とする。入れ子データ型とは、オリジナルとパラメータ的に異なる再帰型を派生させるものである。詳しくは、 Richard Bird、Lambert Meertens、Ross Paterson らの研究を参照されたい。

== 参考文献 ==
* [http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?algebraic+data+type Algebraic data type] in The Free On-line Dictionary of Computing, Editor Denis Howe.

{{FOLDOC}}
{{データ型}}
{{DEFAULTSORT:たいすうてきてえたかた}}
[[Category:データ型]]
[[Category:関数型プログラミング]]