Haskell の代数データ型

Question

私は Haskell の概念をすべて完全に理解しようとしています。

代数データ型は、C# や Java などのジェネリック型とどのような点で似ていますか?そして、それらはどのように違うのでしょうか?そもそも、それらの何がそんなに代数的なのでしょうか?

私は普遍代数とその環と体には精通していますが、Haskell の型がどのように機能するかについては漠然としか知りません。

Answer 1

Haskell サポートの「代数データ型」 フルパラメトリックポリモーフィズム, これは、ジェネリックのより技術的に正しい名前です。簡単な例として、リスト データ型を示します。

 data List a = Cons a (List a) | Nil

(可能な限り、非厳密な評価などを無視して) と同等です。

 class List<a> {
     class Cons : List<a> {
         a head;
         List<a> tail;
     }
     class Nil : List<a> {}
 }

もちろん、Haskell の型システムではさらに多くのことが可能です...型パラメータの興味深い使い方ですが、これは単なる例にすぎません。「代数型」という名前に関しては、正直なところ、その名前が付けられた正確な理由はまったくわかりませんが、型システムの数学的基礎によるものだと考えています。私 信じる その理由は、ADT の理論的定義が「一連のコンストラクターの生成物」であることに帰着しますが、大学を辞めてから数年が経ったので、詳細はもう思い出せません。

[編集：私の愚かな間違いを指摘してくれた Chris Conway に感謝します。ADT はもちろん合計型であり、フィールドの積/タプルを提供するコンストラクターです。]

Answer 2

ハスケルの 代数データ型 に対応するため、そのように名付けられています。 初期代数 圏論では、操作すべき法則、演算、記号が与えられます。通常のデータ構造を記述するために代数表記を使用することもあります。

• + 和の型を表します (素の共用体、例: Either).
• • 製品タイプを表します (例:構造体またはタプル）
• X シングルトンタイプの場合 (例: data X a = X a)
• 1 ユニットタイプの場合 ()
• そして μ 最小不動点の場合 (例:再帰型)、通常は暗黙的です。

いくつかの追加の注記を付けて:

• X² のために X•X

実際、（Brent Yorgey に従って）次のように表現できる場合、Haskell データ型は正規であると言えるかもしれません。 1, X, +, •, 、最小不動点。

この表記法を使用すると、多くの通常のデータ構造を簡潔に記述することができます。

• 単位: data () = ()

  1

• オプション: data Maybe a = Nothing | Just a

  1 + X

• リスト: data [a] = [] | a : [a]

  L = 1+X•L

• 二分木: data BTree a = Empty | Node a (BTree a) (BTree a)

  B = 1 + X•B²

他の操作も当てはまります (Brent Yorgey の論文から引用、参考文献に記載):

• 拡大：固定点を展開すると、リストについて考えるのに役立ちます。 L = 1 + X + X² + X³ + ... (つまり、リストが空であるか、1 つの要素、2 つの要素、3 つの要素、または...) を持っています。

• 構成、 ◦, 、与えられた型 F そして G, 、 構図 F ◦ G 「G 構造から作られた F 構造」を構築するタイプです (例: R = X • (L ◦ R) 、どこ L はリスト、はバラの木です。

• データ型 D の派生である微分 (D' として与えられる) は、単一の「穴」、つまりデータを含まない識別された位置を持つ D 構造のタイプです。これは驚くべきことに、微積分の微分と同じ規則を満たします。

  1′ = 0

  X′ = 1

  (F + G)′ = F' + G′

  (F • G)′ = F • G′ + F′ • G

  (F ◦ G)′ = (F′ ◦ G) • G′

---

参考文献:

• 種と関数と型, 、オーマイ!、ブレント A.ヨーギー、Haskell’10、2010 年 9 月 30 日、米国メリーランド州ボルチモア
• 私の左側にはピエロ、右側にはジョーカー (データ構造の分析), 、コナー・マクブライド POPL 2008

Answer 3

で 普遍代数 の 代数 一部の要素のセット（各セットをタイプの値のセットと考えてください）と要素にマッピングされるいくつかの操作で構成されています。

たとえば、「リスト要素」のタイプと「リスト」のタイプがあるとします。操作として、「空のリスト」があります。これは、「リスト」を返す0次の関数と、「リスト要素」と「リスト」の2つの引数を取得し、「リスト」を作成する「Cons」関数です。 「。

この時点で、2つの望ましくないことが起こる可能性があるため、説明に合う多くの代数があります。

• 「リスト」セットには、「空のリスト」と「Cons操作」、いわゆる「ジャンク」から構築できない要素があります。これは、空から落ちた要素から始まるリスト、または始まりのないループ、または無限のリストです。

• 異なる引数に適用される「Cons」の結果は等しい可能性があります。空白のないリストに要素を考慮すると、空のリストに等しい場合があります。これは「混乱」と呼ばれることもあります。

これらの望ましくない性質のどちらも持たない代数はと呼ばれますイニシャル, 、これが抽象データ型の本来の意味です。

最初の名前は、初期代数から特定の代数にちょうど1つの同性愛があるという特性から派生しています。基本的に、他の代数に操作を適用することにより、リストの値を評価でき、結果は明確に定義されています。

多態性型の場合はさらに複雑になります...

Answer 4

それらが代数的と呼ばれる単純な理由。和 (論理和) タイプと積 (論理積) タイプの両方があります。sum タイプは判別共用体です。例:

data Bool = False | True

製品タイプは、複数のパラメータを持つタイプです。

data Pair a b = Pair a b

O'Caml では、「製品」がより明確になります。

type 'a 'b pair = Pair of 'a * 'b

Answer 5

Haskell のデータ型は、次のものとの関連性から「代数的」と呼ばれます。 カテゴリ初期代数. 。しかし、その先には狂気がある。

@olliej:ADT は実際には「合計」型です。タプルは製品です。

Answer 6

@ティンボ:

3 つの派生クラス (Empty、Leaf、Node) を持つ抽象 Tree クラスのようなものであるという点は基本的に正しいですが、Tree クラスを使用する人が新しい派生クラスを決して追加できないという保証も強制する必要があります。なぜなら、Tree データ型を使用する戦略は、ツリー内の各要素の型に基づいて実行時に切り替わるコードを記述することだからです (新しい派生型を追加すると、既存のコードが壊れてしまいます)。C# や C++ ではこれが厄介になることは想像できますが、Haskell、ML、OCaml では、これが言語設計と構文の中心となるため、コーディング スタイルはパターン マッチングを通じて、より便利な方法でこれをサポートします。

ADT (合計型) も似たものです タグ付きユニオン または バリアント型 C または C++ で。

Answer 7

古い質問ですが、代数データ型の重要な側面、おそらく最も重要な側面である null 可能性については誰も言及していません。各値のほとんどは代替の 1 つであるため、網羅的な大文字と小文字に基づくパターン マッチングが可能です。

Answer 8

私にとって、Haskell の代数データ型の概念は常に C# などの OO 言語のポリモーフィズムのように見えました。

の例を見てください。 http://en.wikipedia.org/wiki/Algebraic_data_types:

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

これは、派生 Leaf クラスと派生 TreeNodeWithChildren クラスを使用して、TreeNode 基本クラスとして C# で実装できます。必要に応じて、派生 EmptyNode クラスも実装できます。

（わかりました、誰もそんなことはしませんが、少なくともあなたにはそれができます。）