Haskells algebraische Datentypen

StackOverflow https://stackoverflow.com/questions/16770

Frage

Ich versuche, alle Konzepte von Haskell vollständig zu verstehen.

Inwiefern ähneln algebraische Datentypen generischen Typen, z. B. in C# und Java?Und wie unterscheiden sie sich?Was ist überhaupt so algebraisch an ihnen?

Ich bin mit der universellen Algebra und ihren Ringen und Feldern vertraut, habe aber nur eine vage Vorstellung davon, wie Haskells Typen funktionieren.

War es hilfreich?

Lösung

„Algebraische Datentypen“ in Haskell-Unterstützung vollständiger parametrischer Polymorphismus, was der technisch korrektere Name für Generika ist, als einfaches Beispiel der Listendatentyp:

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

Ist äquivalent (so weit wie möglich und ohne Berücksichtigung nicht strenger Bewertungen usw.) zu

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

Natürlich erlaubt das Typsystem von Haskell mehr ...interessante Verwendung von Typparametern, aber dies ist nur ein einfaches Beispiel.Was den Namen „Algebraischer Typ“ angeht, war ich mir ehrlich gesagt nie ganz sicher, warum sie so benannt wurden, sondern bin davon ausgegangen, dass dies auf die mathematischen Grundlagen des Typsystems zurückzuführen ist.ICH glauben dass der Grund auf die theoretische Definition eines ADT als „Produkt einer Reihe von Konstruktoren“ zurückzuführen ist. Allerdings ist es schon ein paar Jahre her, seit ich die Universität verlassen habe, sodass ich mich nicht mehr an die Einzelheiten erinnern kann.

[Bearbeiten:Vielen Dank an Chris Conway für den Hinweis auf meinen dummen Fehler. ADT sind natürlich Summentypen, die Konstruktoren stellen das Produkt/Tupel von Feldern bereit.]

Andere Tipps

Haskells algebraische Datentypen werden so genannt, weil sie einem entsprechen Anfangsalgebra in der Kategorientheorie, die uns einige Gesetze, einige Operationen und einige Symbole zur Manipulation liefert.Wir können sogar die algebraische Notation zur Beschreibung regulärer Datenstrukturen verwenden, wobei:

  • + repräsentiert Summentypen (disjunkte Vereinigungen, z.B. Either).
  • • repräsentiert Produkttypen (z.B.Strukturen oder Tupel)
  • X für den Singleton-Typ (z.B. data X a = X a)
  • 1 für den Einheitentyp ()
  • Und μ für den am wenigsten festen Punkt (z.B.rekursive Typen), normalerweise implizit.

mit etwas zusätzlicher Notation:

  • X² für X•X

Tatsächlich könnte man (in Anlehnung an Brent Yorgey) sagen, dass ein Haskell-Datentyp regulär ist, wenn er durch ausgedrückt werden kann 1, X, +, •, und ein kleinster Fixpunkt.

Mit dieser Notation können wir viele reguläre Datenstrukturen prägnant beschreiben:

  • Einheiten: data () = ()

    1

  • Optionen: data Maybe a = Nothing | Just a

    1 + X

  • Listen: data [a] = [] | a : [a]

    L = 1+X•L

  • Binärbäume: data BTree a = Empty | Node a (BTree a) (BTree a)

    B = 1 + X•B²

Andere Operationen gelten (entnommen aus Brent Yorgeys Artikel, aufgeführt in den Referenzen):

  • Erweiterung:Das Entfalten des Fixpunkts kann hilfreich sein, um über Listen nachzudenken. L = 1 + X + X² + X³ + ... (d. h. Listen sind entweder leer oder haben ein Element oder zwei Elemente oder drei oder ...)

  • Komposition, ◦, gegebene Typen F Und G, die Zusammensetzung F ◦ G ist ein Typ, der „F-Strukturen aus G-Strukturen“ aufbaut (z. B. R = X • (L ◦ R) ,Wo L ist Listen, ist ein Rosenbaum.

  • Differenzierung, die Ableitung eines Datentyps D (angegeben als D'), ist der Typ von D-Strukturen mit einem einzelnen „Loch“, d. h. einem bestimmten Ort, der keine Daten enthält.Das erfüllt erstaunlicherweise die gleichen Regeln wie für die Differentiation in der Analysis:

    1′ = 0

    X′ = 1

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

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

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

Verweise:

In Universelle Algebra ein Algebra besteht aus einigen Elementensätzen (denken Sie an jeden Satz als Wertesatz eines Typs) und einige Operationen, die Elemente zu Elementen abbilden.

Angenommen, Sie haben eine Art "Listenelemente" und eine Art von "Listen".Als Operationen haben Sie die "leere Liste", die eine 0-Argument-Funktion ist, die eine "Liste" zurückgibt, und eine "Nachteile", die zwei Argumente einnimmt, ein "Listenelement" und eine "Liste" und eine "Liste erstellen ".

Zu diesem Zeitpunkt gibt es viele Algebren, die der Beschreibung entsprechen, da zwei unerwünschte Dinge passieren können:

  • Das "Liste" -Set könnten Elemente geben, die nicht aus der "leeren Liste" und dem "Cons Operation", dem sogenannten "Junk", erstellt werden können.Dies können Listen sein, die von einem Element aus dem Himmel oder Schleifen ohne Anfang oder unendlichen Listen stammen.

  • Die Ergebnisse von "Nachteilen", die auf verschiedene Argumente angewendet werden, könnten gleich sein, z. B.Ein Element in eine nicht leere Liste zu richten, könnte der leeren Liste entsprechen.Dies wird manchmal als „Verwirrung“ bezeichnet.

Eine Algebra, die keine dieser unerwünschten Eigenschaften aufweist, heißtanfänglich, und das ist die beabsichtigte Bedeutung des abstrakten Datentyps.

Der Name initial ergibt sich aus der Eigenschaft, dass genau ein Homomorphismus von der anfänglichen Algebra zu einer bestimmten Algebra besteht.Im Wesentlichen können Sie den Wert einer Liste bewerten, indem Sie die Operationen in der anderen Algebra anwenden, und das Ergebnis ist gut definiert.

Bei polymorphen Typen wird es komplizierter ...

Ein einfacher Grund, warum sie algebraisch genannt werden;Es gibt sowohl Summentypen (logische Disjunktion) als auch Produkttypen (logische Konjunktion).Ein Summentyp ist eine diskriminierte Vereinigung, z. B.:

data Bool = False | True

Ein Produkttyp ist ein Typ mit mehreren Parametern:

data Pair a b = Pair a b

In O'Caml wird „Produkt“ expliziter gemacht:

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

Die Datentypen von Haskell werden aufgrund ihrer Verbindung zu „algebraisch“ genannt kategoriale Anfangsalgebren.Aber darin liegt der Wahnsinn.

@olliej:ADTs sind eigentlich „Summen“-Typen.Tupel sind Produkte.

@Timbo:

Sie haben im Grunde Recht damit, dass es sich um eine Art abstrakte Tree-Klasse mit drei abgeleiteten Klassen (Empty, Leaf und Node) handelt, aber Sie müssten auch die Garantie erzwingen, dass jemand, der Ihre Tree-Klasse verwendet, niemals neue abgeleitete Klassen hinzufügen kann , da die Strategie für die Verwendung des Datentyps „Tree“ darin besteht, Code zu schreiben, der zur Laufzeit basierend auf dem Typ jedes Elements im Baum wechselt (und das Hinzufügen neuer abgeleiteter Typen den vorhandenen Code zerstören würde).Sie können sich vorstellen, dass dies in C# oder C++ unangenehm wird, aber in Haskell, ML und OCaml ist dies von zentraler Bedeutung für das Sprachdesign und die Syntax, sodass der Codierungsstil dies durch Mustervergleich viel bequemer unterstützt.

ADT (Summentypen) ähneln ebenfalls getaggt mit Gewerkschaften oder Variantentypen in C oder C++.

alte Frage, aber niemand hat die Nullbarkeit erwähnt, was ein wichtiger Aspekt algebraischer Datentypen ist, vielleicht der wichtigste Aspekt.Da es sich bei jedem Wert meist um eine der Alternativen handelt, ist ein umfassender fallbasierter Mustervergleich möglich.

Für mich sah das Konzept der algebraischen Datentypen von Haskell immer wie Polymorphismus in OO-Sprachen wie C# aus.

Schauen Sie sich das Beispiel von an http://en.wikipedia.org/wiki/Algebraic_data_types:

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

Dies könnte in C# als TreeNode-Basisklasse implementiert werden, mit einer abgeleiteten Leaf-Klasse und einer abgeleiteten TreeNodeWithChildren-Klasse und, wenn Sie möchten, sogar einer abgeleiteten EmptyNode-Klasse.

(OK, ich weiß, niemand würde das jemals tun, aber zumindest könnte man es tun.)

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top