代数的データ型
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/02/21 14:04 UTC 版)
代数的データ型(だいすうてきデータがた、英: algebraic data type)とはプログラミング、特に関数型プログラミングや型システムにおいて使われるデータ型である。それぞれの代数的データ型の値には、1個以上のコンストラクタがあり、各コンストラクタには0個以上の引数がある。
代数的データ型の値(データ)の感覚的な説明としては、引数で与えられた他のデータ型の値を、コンストラクタで包んだようなもの、である。コンストラクタに引数がある代数データ型は複合型(他のデータ型を組み合わせて形成する型)である。
概要
Haskellにおける、葉に整数型の値を持つ(分岐は部分木しか持たない)、二分木の例で説明する。以下のようなdata宣言で、データ型を宣言する。
data Node = Leaf Integer | Branch Node Node
deriving (Show) -- 表示させて確認するために付加してあるもので、必須ではない。
この宣言で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))
中のデータにアクセスするにはパターンマッチングを使う。ここで定義した型の木の深さを返す関数の例で次に示す。
depth tree = case tree of
Leaf _ -> 1
Branch a b -> 1 + max (depth a) (depth b)
応用
基本的な代数データ型としては、多くの関数型言語において、言語組み込みのリスト型が用意されており、空リストのためのコンストラクタに相当するリテラルと、追加したい要素と残りのリストを引数に取るコンストラクタ(Lispのen:cons)に相当する、中置記法風のコンストラクタ( ":" など)が言語組み込みで用意されている。
代数的データ型の特殊な例として、直積型(1つのコンストラクタだけを持つ)と列挙型(引数なしの多くのコンストラクタを持つ)がある。
前述の二分木の例において、コンストラクタLeafは Integer -> Node という型を、コンストラクタBranchは Node -> Node -> Node という型を持つ。型のみを見た場合、関数と同じ型をしている。しかし、関数とは違いコンストラクタは単にそこにあるだけのものであり、評価(実行)されるものではなく、オブジェクト指向言語におけるコンストラクタとは異なる。式として見た場合、関数に引数を適用する式は簡約可能だが、コンストラクタによる式は全体としてはそれ以上簡約できない、値をあらわす式である。
関数型言語で抽象データ型を実現する手法のひとつに、モジュールシステムによるスコープ制限を利用して、コンストラクタを掩蔽し、型のみを公開する、という手法がある。データコンストラクタそのものの代わりに、相当する引数をとって、目的の型の値を返すような、コンストラクタを抽象化した関数を定義し、そちらの関数を公開する。この関数が、オブジェクト指向言語におけるコンストラクタに相当する。
他の言語での例
OCamlではヴァリアント型と言い、前述の二分木と同等のデータ型は、次のように書く。
type node = Leaf of int | Branch of node * node
また、伝統的な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では次のように書く。
domains
tree =
empty();
leaf(integer Leaf);
node(tree Left, tree Right).
この例では、leafとnodeの他に、空の木を示すemptyがある。
理論
集合論において代数的データ型と等価なものとして直和がある。この集合の各元はタグ(コンストラクタと等価)とそのタグに対応する型のオブジェクト(コンストラクタの引数と等価)で構成される。
一般に代数的データ型は直積型の総和であり、再帰的に定義されることもある。各コンストラクタは直積型のタグとなって他と区別されるか、1つしかコンストラクタがない場合は、そのデータ型自体が直積型となる。さらにコンストラクタの引数の型が直積型の要素となる。引数のないコンストラクタは空に対応する。データ型が再帰的であるなら、その直積型の総和は再帰データ型となり、各コンストラクタによって再帰データ型が構成される。
例えば、以下のような Haskell のデータ型
data List a = Nil | Cons a (List a)
を型理論的に表すと次のようになる。
代数的データ型
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/11/20 02:06 UTC 版)
Haskell のデータ型には代数的データ型と呼ばれる、C言語などでいう構造体や列挙体の性質を兼ね備えたものが用いられる。次の例は二つのInt型の値をフィールドに持つ二次元の座標、Point2D 型を定義したもので、これは代数的データ型の構造体的な性質を示す。先頭のトークン「data」は代数的データ型の宣言であることを示す予約語である。ここで最初の Point2D はデータ型名を表し、次の Point2D はデータコンストラクタ名を示す。 data Point2D = Point2D Int Intorigin :: Point2Dorigin = Point2D 0 0 -- データコンストラクタは関数のように適用できる データコンストラクタは値を定義するための特殊な関数といえる。データコンストラクタは後述するパターンマッチによって値を取り出す際にも用いられる。 次の例はトランプの4つのスーツを示す Suit 型を定義したものである。Spade、Heart、Club、Diamond の4つのデータコンストラクタが定義されており、Suit 型の式は Spade、Heart、Club、Diamond のいずれかの値をとる。 data Suit = Spade | Heart | Club | Diamond 次の例は String 型の値を格納する二分木の型である。Leaf(葉)は String 型の値を持ち、Branch(枝)は Leaf もしくは Branch である Tree 型の変数を二つ持つ。これは代数的データ型の構造体的な性質と列挙体的な性質の両方が現れている。 data Tree = Leaf String | Branch Tree Treeorganisms :: Treeorganisms = Branch animals plants -- Branch (Branch (Branch (Leaf "Lion") (Leaf "Tiger")) (Leaf "Wolf")) (Leaf "Cherry")animals = Branch cats (Leaf "Wolf")cats = Branch (Leaf "Lion") (Leaf "Tiger")plants = Leaf "Cherry" GADTと呼ばれる機能を使うと、コンストラクタの型を明示してデータ型を定義することもできる。 {-# LANGUAGE GADTs #-}data Maledata Femaledata Person s where Adam :: Person Male Eve :: Person Female Child :: Person Male -> Person Female -> Int -> Person a
※この「代数的データ型」の解説は、「Haskell」の解説の一部です。
「代数的データ型」を含む「Haskell」の記事については、「Haskell」の概要を参照ください。
固有名詞の分類
- 代数的データ型のページへのリンク