代数的データ型とは? わかりやすく解説

代数的データ型

出典: フリー百科事典『ウィキペディア(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」の記事における「代数的データ型」の解説

Haskellデータ型には代数的データ型と呼ばれるC言語などでいう構造体列挙体の性質兼ね備えたものが用いられる次の例は二つInt型の値をフィールドに持つ二次元座標、Point2D 型を定義したもので、これは代数的データ型の構造体的な性質を示す。先頭トークンdata」は代数的データ型の宣言であることを示す予約語である。ここで最初の Point2D はデータ型名を表し次の Point2D はデータコンストラクタ名を示す。 data Point2D = Point2D Int Intorigin :: Point2Dorigin = Point2D 0 0 -- データコンストラクタは関数のように適用できる データコンストラクタは値を定義するための特殊な関数といえる。データコンストラクタは後述するパターンマッチによって値を取り出す際にも用いられる次の例はトランプ4つスーツを示す Suit 型を定義したのであるSpadeHeartClubDiamond4つのデータコンストラクタが定義されており、Suit 型の式は SpadeHeartClubDiamondいずれかの値をとる。 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」の概要を参照ください。

ウィキペディア小見出し辞書の「代数的データ型」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



固有名詞の分類


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「代数的データ型」の関連用語

代数的データ型のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



代数的データ型のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの代数的データ型 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、WikipediaのHaskell (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS