DseWiki: AlgebraischeTypen

Veränderung (letzte Änderung) (keine anderen Diffs, Normalansicht)

Verändert: 1c1,65

Beschreibe hier die neue Seite.

(von SprachePerl)

Algebraische Typen sind die Mechanismen, mit denen man aus primitiven Datentypen neue definiert. In Sprachen wie Haskell oder ML sind die grundlegenden Mittel dafür:

* Disjunkte Summen. Pascal-Programmierer nennen sie "tagged Unions". Hier ein Datum, das wahlweise eine Ganzzahl oder eine Gleitkommazahl enthalten kann:

data IntOrFloat? = AnInt? Int | AFloat Float

* Produkte. Pascal-Programmierer nennen sie Records. Hier ein Paar aus zwei Ganzzahlen:

data TwoInts? = Two Int Int

* Funktionen. Nicht ganz so wichtig, und wenn man nicht funktionales Programmieren gewöhnt ist, sieht man auch nicht, wozu das gut sein soll. Nützlich sind sie trotzdem. Hier der "Stringtransformer" aus der Haskell-Prelude:

type ShowS? = String -> String

Defintionen dürfen rekursiv sein, und in modernen Sprachen mit Typvariablen parametrisiert werden. So sehen dann Listen und binäre Suchbäume aus:

data List element = Cons element (List element) | Nil
data Tree key = Node (Tree key) key (Tree key) | Leaf

Erzeugt werden solche Daten durch Anwendung der Konstruktoren auf geeignete Argumente. Das ist beispielsweise eine Liste von zwei Ganzzahlen:

Cons 1 (Cons 2 Nil)

Zerlegt werden sie in Haskell oder ML durch PatternMatching. So definiert man etwa eine Funktion, die das erste Element einer Liste ermittelt:

head (Cons x ys) = x
head Nil = error "head of empty list"

Sprachen wie C, Pascal, Java haben natürlich ihren eigenen Ersatz. Jedoch muss Rekursion über Pointer oder Referenzen explizit gemacht werden und die Zerlegung von Unions (so es welche gibt) ist immer etwas unsicher, weil nicht sichergestellt ist, dass nicht auf einen gerade undefinierten Zweig einer Union zugegriffen wird.

Die Vorteile von algebraischen Typen und Pattern Matching liegen auf der Hand:

* keine Gefahr, undefinierte Daten anzufassen
* keine Alternative kann übersehen werden (ohne eine Compilerwarnung zu provozieren)

...obwohl ich das Gewicht nicht verstehe, das du den Unions gibst. -- HelmutLeitner

Nur in Verbindung mit Pattern Matching. Betrachten wir eine Funktion, die ein Ergebnis liefern kann oder auch nicht, nämlich die Lösung einer quadratischen Gleichung. Die hat entweder keine Lösung oder eine oder zwei. Wie implementiert man das? In C vermutlich, indem man sich die Anzahl der Lösungen als Ergebnis geben läßt und die Ergebnisse selbst in zwei referenzierten Variablen ablegen läßt.

int solve_quadratic( double a, double b, double c, double *x1, double *x2 ) ;

Mit alg. Summen läßt man sich das Ergebnis einfach geben wie es ist:

data Solution = None | One Double | Two Double Double
solve_quadratic :: Double -> Double -> Double -> Solution

...und es besteht keine Gefahr, eine "Lösung" anzufassen, die gar nicht berechnet wurde.

Oder wir betrachten eine Funktion, die fehlschlagen kann, weil irgendwas nicht ist, wie es sein sollte (ExceptionHandling? sozusagen). Die kann dann ein Ergebnis oder einen Fehler liefern.

data Either a b = Left a | Right b
openFile :: FilePath? -> Either Error Handle

Praktischerweise ist es unmöglich, die Fehlerbehandlung zu vergessen. Um nämlich an das Handle zu kommen, muss man auf den Konstruktor Right matchen, und das geht nicht, wenn es in Wirklichkeit einen Fehler gab.

case openFile "foo" of
Right hdl -> hPutStr hdl "bar"
Left err -> print "the sky is falling!"

(von SprachePerl)

Algebraische Typen sind die Mechanismen, mit denen man aus primitiven Datentypen neue definiert. In Sprachen wie Haskell oder ML sind die grundlegenden Mittel dafür:

Disjunkte Summen. Pascal-Programmierer nennen sie "tagged Unions". Hier ein Datum, das wahlweise eine Ganzzahl oder eine Gleitkommazahl enthalten kann:

  data IntOrFloat? = AnInt? Int | AFloat Float

Produkte. Pascal-Programmierer nennen sie Records. Hier ein Paar aus zwei Ganzzahlen:

  data TwoInts? = Two Int Int

Funktionen. Nicht ganz so wichtig, und wenn man nicht funktionales Programmieren gewöhnt ist, sieht man auch nicht, wozu das gut sein soll. Nützlich sind sie trotzdem. Hier der "Stringtransformer" aus der Haskell-Prelude:

  type ShowS? = String -> String

Defintionen dürfen rekursiv sein, und in modernen Sprachen mit Typvariablen parametrisiert werden. So sehen dann Listen und binäre Suchbäume aus:

  data List element = Cons element (List element) | Nil
  data Tree key = Node (Tree key) key (Tree key) | Leaf

Erzeugt werden solche Daten durch Anwendung der Konstruktoren auf geeignete Argumente. Das ist beispielsweise eine Liste von zwei Ganzzahlen:

  Cons 1 (Cons 2 Nil)

Zerlegt werden sie in Haskell oder ML durch PatternMatching. So definiert man etwa eine Funktion, die das erste Element einer Liste ermittelt:

  head (Cons x ys) = x
  head Nil         = error "head of empty list"

Sprachen wie C, Pascal, Java haben natürlich ihren eigenen Ersatz. Jedoch muss Rekursion über Pointer oder Referenzen explizit gemacht werden und die Zerlegung von Unions (so es welche gibt) ist immer etwas unsicher, weil nicht sichergestellt ist, dass nicht auf einen gerade undefinierten Zweig einer Union zugegriffen wird.

Die Vorteile von algebraischen Typen und Pattern Matching liegen auf der Hand:

keine Gefahr, undefinierte Daten anzufassen
keine Alternative kann übersehen werden (ohne eine Compilerwarnung zu provozieren)

...obwohl ich das Gewicht nicht verstehe, das du den Unions gibst. -- HelmutLeitner

Nur in Verbindung mit Pattern Matching. Betrachten wir eine Funktion, die ein Ergebnis liefern kann oder auch nicht, nämlich die Lösung einer quadratischen Gleichung. Die hat entweder keine Lösung oder eine oder zwei. Wie implementiert man das? In C vermutlich, indem man sich die Anzahl der Lösungen als Ergebnis geben läßt und die Ergebnisse selbst in zwei referenzierten Variablen ablegen läßt.

  int solve_quadratic( double a, double b, double c, double *x1, double *x2 ) ;

Mit alg. Summen läßt man sich das Ergebnis einfach geben wie es ist:

  data Solution = None | One Double | Two Double Double
  solve_quadratic :: Double -> Double -> Double -> Solution

...und es besteht keine Gefahr, eine "Lösung" anzufassen, die gar nicht berechnet wurde.

Oder wir betrachten eine Funktion, die fehlschlagen kann, weil irgendwas nicht ist, wie es sein sollte (ExceptionHandling? sozusagen). Die kann dann ein Ergebnis oder einen Fehler liefern.

  data Either a b = Left a | Right b
  openFile :: FilePath? -> Either Error Handle

Praktischerweise ist es unmöglich, die Fehlerbehandlung zu vergessen. Um nämlich an das Handle zu kommen, muss man auf den Konstruktor Right matchen, und das geht nicht, wenn es in Wirklichkeit einen Fehler gab.

case openFile "foo" of Right hdl -> hPutStr hdl "bar" Left err -> print "the sky is falling!"