💎代数的なデータ構造(ADT)と抽象データ型(ADT) AST

2022年8月31日 18:31

代数的データ型とは、和と積からなるデータ型である。和は選択式、積は表形式

「代数的データ構造」という用語は、その構造が数学の代数学、特に集合論と関連していることから来ています。ここでの「代数的」という言葉は、これらのデータ構造が、集合間の関係や操作を表現する代数学の原理に従っていることを指します。

1. **積の型（Product Types）**:
- 積の型は数学の直積（Cartesian Product）に似ています。直積は、複数の集合の要素の組み合わせを表します。同様に、積の型は複数の値を一つの構造に組み合わせることで、それぞれの値が異なる型を持つことができます。

2. **和の型（Sum Types）**:
- 和の型は数学の和集合（Union）に類似しています。和集合は複数の集合の要素をすべて含む集合です。和の型では、複数の異なる型のいずれか一つの値を持つことができ、これにより異なる可能性のある型の組み合わせを表現しています。

このように、代数的データ構造は、それぞれの構造が数学的な概念と密接に関連しているため、「代数的」と呼ばれます。プログラミングにおいて、これらの概念を用いることで、より明確で安全なコードの構築が可能になります。

代数的データ型の一般的なクラスは、積型（すなわちタプルおよびレコード）と和型（すなわちタグ付きまたは不連続の共用体、共積型または変量型）の2つである

https://en.wikipedia.org/wiki/Algebraic_data_type

直積・構造体・タプル・レコード・テーブル

積型のすべての可能な値の集合は、そのフィールド型のすべての可能な値の集合の集合論的積、すなわちデカルト積である。

直和、共用体、UNION、バリアント、列挙

和型の値は通常，バリアントと呼ばれるいくつかのクラスにグループ化される．バリアント型の値は通常、コンストラクタと呼ばれる準機能的な実体で作成される

コンピュータサイエンスでは、タグ付き結合は、バリアント、バリアントレコード、選択型、判別型結合、非接合型結合、合計型、コプロダクトとも呼ばれ、複数の異なるが固定した型を取りうる値を保持するために使われるデータ構造である。一度に使用できる型は1つだけであり、タグフィールドはどれが使用されているかを明示的に示す。

https://en.wikipedia.org/wiki/Tagged_union

タグ付き結合は、最も単純な自己記述型データ形式と見なすことができます。タグ付き組合のタグは、最も単純な種類のメタデータと見なすことができます。
和の型のすべての可能な値の集合は、そのバリアントのすべての可能な値の集合の集合論的な和、すなわち離接結合（the disjoint union）である

Tagged union（またはdiscriminated union, variant, sum type, algebraic data typeなどとも呼ばれる）は、複数の異なる型のいずれか一つの値を取ることができるデータ構造です。各値はタグ（またはディスクリミナント）として知られる特定の型と関連付けられており、このタグを使用してunionの現在の型を識別することができます。

以下は、TypeScriptでのtagged unionの例です：

type Shape = 
    { kind: "circle"; radius: number } 
  | { kind: "square"; sideLength: number }
  | { kind: "rectangle"; width: number; height: number };

function area(s: Shape): number {
    switch (s.kind) {
        case "circle":
            return Math.PI * s.radius * s.radius;
        case "square":
            return s.sideLength * s.sideLength;
        case "rectangle":
            return s.width * s.height;
    }
}

上記の例では、`Shape`型は3つの異なる形状を持つことができ、それぞれの形状は`kind`というタグを持っています。`area`関数は、このタグを使用してどの形状の面積を計算するかを判断します。

Tagged unionは、特定の値が限られたいくつかの異なる型のうちの1つであることを表現するときに非常に便利です。多くの関数型プログラミング言語や新しい言語（例: Rust, TypeScript, Haskellなど）では、この概念は非常に一般的です。

交わりを持たない和 (disjoint union): その族に属する部分集合のどの二つも互いに素 (pairwise disjoint) であるときの、通常の合併。

代数的データ型は、1970年代にエジンバラ大学で開発された小型の関数型プログラミング言語Hopeに導入された

https://ja.wikipedia.org/wiki/%E9%9D%9E%E4%BA%A4%E5%92%8C

Hope言語

Hopeは1970年代にエジンバラ大学で開発された小型の関数型プログラミング言語である[1][2]。 MirandaやHaskellよりも古く、同じく同大学で開発されたMLと同時期である。HopeはRod BurstallとJohn Darlingtonがプログラム変換の研究で開発した単純な関数型言語NPL[3]から派生した[4]。 NPLとHopeはコールバイパターン評価と代数的データ型を最初に備えた言語として注目されている

https://en.wikipedia.org/wiki/Hope_(programming_language)

Hope言語で階乗プログラム

Hopeのパターンマッチは常に、より具体的なパターンをより具体的でないパターンよりも優先させるため、節の順序を変更してもプログラムの意味は変わりません。Hopeでは明示的な型宣言が必要です。Hopeには型推論アルゴリズムを使用するオプションはありません。 Hopeはタプルとリストという2つの組み込みデータ構造を提供します。

片方向リスト（和型）

代数的データ型の最も一般的な例として、単一連結リスト(片方向リスト
)がある。リスト型は和の型で，空のリストを表すNilと，新しい要素xとリストxsを組み合わせて新しいリストを作るCons x xsという2つのバリエーションがある

それぞれのデータ型には、コンストラクタと呼ばれる識別子が関連付けられており、これはデータの種類を表すタグのようなものと見なすことができます。

形式的には、抽象データ型は「論理的な振る舞いが値の集合と操作の集合によって定義されるオブジェクトのクラス」[1]と定義できる。これは、数学における代数的構造に類似している。動作」の意味は著者によって異なり、動作の形式的仕様の主なものは公理的（代数的）仕様と抽象モデルの2種類であり、これらはそれぞれ抽象機械の公理的意味論と演算的意味論に相当する[2]。また、計算複雑度（「コスト」）を、時間（計算操作）と空間（値の表現）の両側面から記述する著者もいる。実際には、抽象化が完全ではないため、多くの一般的なデータ型はADTではなく、ユーザは表現に起因する算術オーバーフローなどの問題に注意しなければならない。例えば、整数は固定幅の値（32ビットまたは64ビットの2進数）として格納されることが多いため、最大値を超えると整数のオーバーフローが発生する。

https://en.wikipedia.org/wiki/Abstract_data_type

例えば，整数は抽象データ型であり，値 ..., -2, -1, 0, 1, 2, ... と，加算，減算，乗算，除算，および大なり小なりなどの演算によって定義され，コンピュータが整数をどう表現するかとは関係なく，（整数分割に注意して）身近な数学に従って振る舞わせることができます。

お願い致します