Algebraic data typeとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Algebraic data typeの意味・解説 

代数的データ型

(Algebraic data type から転送)

出典: フリー百科事典『ウィキペディア(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)

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

カテゴリ


「Algebraic data type」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


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

辞書ショートカット

すべての辞書の索引

「Algebraic data type」の関連用語

Algebraic data typeのお隣キーワード
検索ランキング

   

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



Algebraic data typeのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの代数的データ型 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS