62

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

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

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

4

8 に答える 8

103
于 2011-05-06T21:20:55.787 に答える
23

Haskell の "Algebraic Data Types" は完全なパラメトリック ポリモーフィズムをサポートしています。これはジェネリックのより技術的に正しい名前です。リスト データ型の簡単な例として:

 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 はもちろん合計型であり、フィールドの積/タプルを提供するコンストラクターです]

于 2008-08-19T19:46:24.647 に答える
20

普遍代数では 、代数はいくつかの要素のセット (各セットを型の値のセットと考えてください) と、要素を要素にマッピングするいくつかの操作で構成されます。

たとえば、「リスト要素」のタイプと「リスト」のタイプがあるとします。操作として、「リスト」を返す引数なしの関数である「空リスト」と、「リスト要素」と「リスト」の 2 つの引数を取り、「リスト」を生成する「cons」関数があります。 "。

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

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

  • 異なる引数に適用された "cons" の結果は等しくなる可能性があります。たとえば、要素を空でないリストにコンシングすると、空のリストと等しくなる可能性があります。これは「混乱」と呼ばれることもあります。

これらの望ましくない特性のどちらも持たない代数は initialと呼ばれ、これが抽象データ型の意図した意味です。

初期という名前は、初期代数から任意の代数への準同型が 1 つだけ存在するという性質に由来します。基本的に、リストの値は他の代数に演算を適用することで評価でき、結果は明確に定義されています。

多相型の場合はより複雑になります...

于 2009-03-13T21:23:55.290 に答える
12

それらが代数的と呼ばれる単純な理由。合計 (論理和) 型と積 (論理積) 型の両方があります。合計型は判別共用体です。たとえば、次のようになります。

data Bool = False | True

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

data Pair a b = Pair a b

O'Caml では、「製品」がより明確にされています。

type 'a 'b pair = Pair of 'a * 'b
于 2009-03-16T01:28:07.177 に答える
9

Haskellのデータ型は、カテゴリの始代数との関係から「代数」と呼ばれます。しかし、そのように狂気があります。

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

于 2008-08-19T20:53:36.477 に答える
3

@ティンボ：

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

ADT (合計型) も、C または C++のタグ付き共用体またはバリアント型のようなものです。

于 2008-08-30T07:21:17.733 に答える
2

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

于 2008-12-19T22:49:23.787 に答える
0

私にとって、Haskell の代数データ型の概念は、C# のようなオブジェクト指向言語では常にポリモーフィズムのように見えました。

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

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

これは、派生 Leaf クラスと派生 TreeNodeWithChildren クラスを使用して、C# で TreeNode 基本クラスとして実装できます。また、派生 EmptyNode クラスが必要な場合もあります。

（わかりました、誰もそれをやろうとはしませんが、少なくともあなたはできるでしょう。）

于 2008-08-19T19:58:06.400 に答える