Neue Typen werden mittels einer Datentypdefinition eingeführt.
----------------------------------------------------------------------
data T a1 ... ak = C1 t11 ... t1m1
| ...
| Cn tn1 ... tnmn
----------------------------------------------------------------------
Die `Ci' heißen Konstruktoren: mit Ihrer Hilfe werden Elemente des Datentyps `T' konstruiert. Die `ai' sind die Typparameter des Datentyps `T'.
Mit Ausnahme von Funktionen können alle vordefinierte Typen als Datentypen definiert werden.
---------------------------------------------------------------------- > data Bool = False | True > data Char = '\NUL' | ... | '\255' > data Int = -65532 | ... | -1 | 0 | ... | 65532 > data () = () -- das leere Tupel > data (a, b) = (a, b) -- Paare > data (a, b, c) = (a, b, c) -- Tripel > data [a] = [] | a : [a] ----------------------------------------------------------------------
Die Typen `Integer', `Float' und `Double' sind schwieriger zu realisieren.
Aufgabe 1. Überlege, wie der Typ `Integer', ganze Zahlen mit beliebiger Genauigkeit, dargestellt werden kann!
Datentypen subsumieren Aufzählungstypen.
---------------------------------------------------------------------- > data Color = Red | Green | Blue ----------------------------------------------------------------------
Sie umfassen Tupeltypen: Jeder Datentyp mit einem Konstruktor heißt Tupeltyp.
---------------------------------------------------------------------- > data Point = Point Int Int ----------------------------------------------------------------------
Sie verallgemeinern Vereinigungstypen.
---------------------------------------------------------------------- > data Maybe a = Nothing | Just a > data Either a b = Left a | Right b ----------------------------------------------------------------------
Datentypen können parametrisiert werden und sie dürfen rekursiv definiert sein.
Aufgabe 2. Wie können Bäume mit einem beliebigen Verzweigungsgrad definiert werden?
Konstruktoren werden in Mustern verwendet, um Funktionen auf den neu ein geführten Datentypen zu definieren:
Die Fallunterscheidung wird durch die Datentypdefinition diktiert. [In den meisten Fällen jedenfalls.]
Also: 3 Konstruktoren bedingen 3 Gleichungen bzw. 3 Fälle; rekursive Datentypdefinitionen führen zu rekursiven Funktionsdefinitionen.
Auch Korrektheitsbeweise orientieren sich an der Datentypdefinition.
Der Nachweis der Korrektheit erfolgt induktiv über die Struktur des Datentyps. [In vielen Fällen.]
Also: nicht rekursive Konstruktoren ergeben Basisfälle, rekursive Konstruktoren werden induktiv behandelt.
Mit Hilfe der vordefinierten Datentypen `Maybe' und `Either' lassen sich `Ausnahmen' programmieren (später mehr dazu). Zum Beispiel: die Suche nach einem Element ist erfolgreich oder schlägt fehl.
---------------------------------------------------------------------- > lookup :: (Ord a) => Tree (a, b) -> a -> Maybe b > lookup Empty b = Nothing > lookup (Node l (a, v) r) b > | b < a = lookup l b > | b == a = Just v > | b > a = lookup r b > > > lookupWithDefault :: (Ord a) => Tree (a, b) -> b -> a -> b > lookupWithDefault t def b > = case lookup t b of > Nothing -> def > Just v -> v ----------------------------------------------------------------------
Mit Hilfe von Typsynonymen können Namen für Typausdrücke eingeführt werden.
---------------------------------------------------------------------- type T a1 ... ak = t ----------------------------------------------------------------------
Typsynonyme werden verwendet, um `große' Typausdrücke abzukürzen und um die Lesbarkeit des Programms durch Verwendung aussagekräftiger Typnamen zu erhöhen.
---------------------------------------------------------------------- > type String = [Char] > type Filename = String > type Set a = [a] > type Dict a b = Tree (a, b) ----------------------------------------------------------------------
Beachte: Im Gegensatz zu Datentypdefinitionen dürfen Typsynonyme nicht rekursiv definiert werden.
Namen zu erfinden ist schwer!
Typklassen erlauben es, den gleichen Namen für syntaktisch verschiedene, aber semantisch ähnliche Funktionen zu verwenden. Kandidaten für überladene Funktionen:
Beachte: `(<=)' ist für verschiedene Typen, z.B. `Int' und `[Char]', unterschiedlich definiert.
Überladene Funktionen kommen meist in Gruppen. Eine Typklasse deklariert eine solche Gruppe als überladen.
---------------------------------------------------------------------- > class Eq a where > (==) :: a -> a -> Bool > (/=) :: a -> a -> Bool ----------------------------------------------------------------------
Lies: der Typ `a' ist eine Instanz der Typklasse `Ord', wenn auf `a' die Operationen `(==)' und `(/=)' definiert sind.
Typklassen schränken die Gültigkeit eines Typs ein.
---------------------------------------------------------------------- > elem :: (Eq a) => a -> a -> Bool ----------------------------------------------------------------------
Lies: für alle Typen `a', auf denen die Gleichheit definiert ist, ist `a -> a -> Bool' ein gültiger Typ von `elem'.
Typklassen können als Prädikate auf oder Eigenschaften von Typen aufgefaßt werden, daher die Schreibweise.
Die Zugehörigkeit eines Typs zu einer Typklasse wird explizit durch eine Instanzdeklaration angegeben.
---------------------------------------------------------------------- > instance Eq Int where > m == n = intEq m n > m /= n = not (m == n) ----------------------------------------------------------------------
`intEq' ist die primitive Funktion, die zwei ganze Zahlen auf Gleichkeit testet.
---------------------------------------------------------------------- > instance (Eq a) => Eq (Tree a) where > Empty == Empty = True > Node l1 a1 r1 == Node l2 a2 r2 = l1 == l2 && a1 == a2 > && r1 == r2 > _ == _ = False > t /= u = not (t == u) ----------------------------------------------------------------------
D.h., `Tree a' ist eine Instanz von `Eq', wenn `a' eine Instanz von `Eq' ist.
Operationen können in einer Klassendeklaration für alle Instanzen definiert werden.
---------------------------------------------------------------------- > class Eq a where > (==), (/=) :: a -> a -> Bool > x /= y = not (x == y) ----------------------------------------------------------------------
Falls in einer Instanzdeklaration `/=' nicht spezifiziert wird, verwendet der Übersetzer die Definition aus der Typklasse.
---------------------------------------------------------------------- > instance Eq Int where > m == n = intEq m n ----------------------------------------------------------------------
Typklassen können sich auf Oberklassen abstützen. Beispiel: Die Vergleichsoperationen `<', `<=' etc. sind nur sinnvoll auf Typen, die auch `==' zur Verfügung stellen.
---------------------------------------------------------------------- > class (Eq a) => Ord a where > (<), (<=), (>=), (>) :: a -> a -> Bool > x < y = x <= y && x /= y > x >= y = y <= x > x > y = y < x ----------------------------------------------------------------------
Aufgabe 3. Vergleiche Haskells Typklassen mit dem Klassenkonzept objektorientierter Sprachen.
Die Standardklassen von Haskell sind wie folgt organisiert.
Eq
/ \
/ \
Ord \ Text
/ \ \ /
/ \ \ /
/ Enum Num
/ \ / \
Ix \ / \
\ Real Fractional
\ / \ / \
\ / \ / \
Integral RealFrac Floating
\ /
\ /
RealFloat
`Eq' und `Ord' haben wir schon kennengelernt; mit `Enum', `Text' und den numerischen Klassen `Num', `Real' etc. beschäftigen wir uns im folgenden.
Die arithmetischen Folgen sind Abkürzungen für:
---------------------------------------------------------------------- > [ n .. ] = enumFrom n -- Pseudocode > [ n, m .. ] = enumFromThen n m > [ n .. m ] = enumFromTo n m > [ n, n' .. m ] = enumFromThenTo n n' m ----------------------------------------------------------------------
Die Typklasse `Enum' ermöglicht es, diese Funktionen zu überladen.
---------------------------------------------------------------------- > class (Ord a) => Enum a where > enumFrom :: a -> [a] > enumFromThen :: a -> a -> [a] > enumFromTo :: a -> a -> [a] > enumFromThenTo :: a -> a -> a -> [a] > enumFromTo n m = takeWhile (<= m) (enumFrom n) > enumFromThenTo n n' m > = takeWhile (if n' >= n then (<= m) else (>= m)) > (enumFromThen n n') ----------------------------------------------------------------------
Die Klasse `Text' stellt Funktionen zur Verfügung, um Werte `ein-' und `auszugeben'.
---------------------------------------------------------------------- > show :: (Text a) => a -> String > read :: (Text a) => String -> a ----------------------------------------------------------------------
Alle vordefinierten Typen sind Instanzen der Typklasse `Text'. Wir haben bei der Programmierung des `interaktiven Wörterbuchs' Gebrauch von `show' und `read' gemacht.
---------------------------------------------------------------------- > ... readFile fname >>= \cnts -> > ... read cnts ... > ... writeFile fname (show dict) ----------------------------------------------------------------------
`show' realisiert einen `Pretty Printer', `read' einen Parser.
Wie programmiere ich einen `Pretty Printer'? Beispiel: Ausgabe von Bäumen.
---------------------------------------------------------------------- > data Tree lab = Empty | Node (Tree lab) lab (Tree lab) ----------------------------------------------------------------------
`showTree' führt im Prinzip einen Inorder-Durchlauf durch.
---------------------------------------------------------------------- > showTree :: (Text a) => Tree a -> String > showTree Empty = "Empty" > showTree (Node l a r) = "(Node " > ++ showTree l ++ " " > ++ show a ++ " " > ++ showTree r ++ ")" ----------------------------------------------------------------------
Problem: Die Laufzeit von `showTree' wächst quadratisch zur Baumgröße.
---------------------------------------------------------------------- > lefty 0 = Empty > lefty (n+1) = Node (lefty n) n Empty ----------------------------------------------------------------------
Die Verwendung von `++' verursacht die Laufzeitprobleme. Lösung: Wir programmieren eine Funktion, die einen Baum ausgibt und an das Ergebnis eine Zeichenkette anhängt. Spezifikation:
---------------------------------------------------------------------- > showsTree t x = showTree t ++ x -- Spezifikation ----------------------------------------------------------------------
Aus der Spezifikation läßt sich die Implementierung einfach ableiten `;-)'.
----------------------------------------------------------------------
> showsTree :: (Text a) => Tree a -> String -> String
> showsTree Empty x = "Empty" ++ x
> showsTree (Node l a r) x
> = "(Node "
> ++ showsTree l (" "
> ++ shows a (" "
> ++ showsTree r (")" ++ x)))
> showTree :: (Text a) => Tree a -> String
> showTree t = showsTree t ""
----------------------------------------------------------------------
`showsTree' läßt sich noch eleganter notieren.
---------------------------------------------------------------------- > type ShowS = String -> String > > showsTree :: (Text a) => Tree a -> ShowS > showsTree Empty = showString "Empty" > showsTree (Node l a r) > = showString "(Node " > . showsTree l . showChar ' ' > . shows a . showChar ' ' > . showsTree r . showChar ')' > > showChar = (:) > showString = (++) ----------------------------------------------------------------------
C-Programmierer. Lies `showfoo' als `printf' und ``.'' als ``;''.
Einige Klammern in der Ausgabe können eingespart werden ...
----------------------------------------------------------------------
> showTree :: (Text a) => Tree a -> String
> showTree t = showsTreePrec 0 t ""
>
> showsTreePrec :: (Text a) => Int -> Tree a -> ShowS
> showsTreePrec d Empty = showString "Empty"
> showsTreePrec d (Node l a r)
> = showParen (d >= 10) (
> showString "Node "
> . showsTreePrec 10 l . showChar ' '
> . showsPrec 10 a . showChar ' '
> . showsTreePrec 10 r)
>
> showParen :: Bool -> ShowS -> ShowS
> showParen False p = p
> showParen True p = showChar '(' . p . showChar ')'
----------------------------------------------------------------------
Die erste Hälfte der Typklasse `Text' lautet wie folgt:
---------------------------------------------------------------------- > class Text a where > showsPrec :: Int -> a -> ShowS > showList :: [a] -> ShowS > > showList [] = showString "[]" > showList (x:xs) = showChar '[' . shows x . showl xs > where > showl [] = showChar ']' > showl (x:xs) = showChar ',' . shows x . showl xs ----------------------------------------------------------------------
Aufgabe 4. Warum enthält die Typklasse `Text' zusätzlich die Funktion `showList'?
Wie programmiere ich einen Parser? Beispiel: Eingabe von Bäumen.
---------------------------------------------------------------------- > type ReadS a = String -> [(a, String)] ----------------------------------------------------------------------
Ein Parser überführt ein Anfangsstück seiner Eingabe in einen `semantischen' Wert, der zusammen mit der restlichen Eingabe zurückgegeben wird. `ReadS' beschreibt nicht-deterministische Parser: Die Liste aller Möglichkeiten, Teile der Eingabe zu parsen, wird ermittelt.
----------------------------------------------------------------------
(reads :: ReadS Int) "5 hamburger"
=> [(5," hamburger")]
----------------------------------------------------------------------
Ein Parser für die lexikalische Analyse ist vordefiniert.
---------------------------------------------------------------------- > lex :: ReadS String ----------------------------------------------------------------------
`lex' ermittelt die nächste lexikalische Einheit (`token').
Ein Parser für Binärbäume läßt sich einfach mit Hilfe von Listenbeschreibungen notieren.
----------------------------------------------------------------------
> readsTree :: (Text a) => ReadS (Tree a)
> readsTree s = [ (Empty, x) | ("Empty", x) <- lex s ]
> ++ [ (Node l a r, y)
> | ("(", t) <- lex s,
> ("Node", u) <- lex t,
> (l, v) <- readsTree u,
> (a, w) <- reads v,
> (r, x) <- readsTree w,
> (")", y) <- lex x ]
----------------------------------------------------------------------
Mit optionalen Klammern ...
----------------------------------------------------------------------
> readsTreePrec :: (Text a) => Int -> ReadS (Tree a)
> readsTreePrec d s = readParen False readEmpty s
> ++ readParen (d >= 10) readNode s
> where
> readEmpty s = [ (Empty, x) | ("Empty", x) <- lex s ]
> readNode s = [ (Node l a r, x)
> | ("Node", u) <- lex t,
> (l, v) <- readsTreePrec 10 u,
> (a, w) <- reads v,
> (r, x) <- readsTreePrec 10 w ]
> readParen :: Bool -> ReadS a -> ReadS a
> readParen b g = if b then mandatory else optional
> where optional r = g r ++ mandatory r
> mandatory r = [ (x,u) | ("(", s) <- lex r,
> (x, t) <- optional s,
> (")", u) <- lex t ]
----------------------------------------------------------------------
Die zweite Hälfte der Typklasse `Text' lautet wie folgt:
----------------------------------------------------------------------
> class Text a where
> readsPrec :: Int -> ReadS a
> readList :: ReadS [a]
>
> readList = readParen False (\s ->
> [ pr | ("[", t) <- lex s,
> pr <- readl t ])
> where
> readl s = [ ([], t) | ("]", t) <- lex s ]
> ++ [ (x:xs, u) | (x, t) <- reads s,
> (xs, u) <- readl' t ]
> readl' s = [ ([], t) | ("]", t) <- lex s]
> ++ [ (x:xs,v) | (",", t) <- lex s,
> (x, u) <- reads t,
> (xs, v) <- readl' u ]
----------------------------------------------------------------------
Instanzen der Typklassen `Eq', `Ord', `Enum' und `Text' können vom Übersetzer automatisch erzeugt werden.
---------------------------------------------------------------------- > data Tree lab = Empty | Node (Tree lab) lab (Tree lab) > deriving (Eq, Ord, Text) ----------------------------------------------------------------------
Mit dem Zusatz `deriving' lassen sich folgende kanonische Instanzen ableiten.
Den größten Teil der Klassenhierarchie machen numerische Klassen aus. Wie erklären sich die Klassen und ihre Anordnung?
Die numerischen Standardklassen von Haskell sind wie folgt organisiert.
Num
/ \
/ \
Real Fractional
/ \ / \
/ \ / \
Integral RealFrac Floating
[Int, Integer] [Ratio a] [Complex a]
\ /
\ /
RealFloat
[Float, Double]
In der Typklasse `Num' sind die arithmetischen Grundoperationen zusammengefaßt, die allen numerischen Typen gemeinsam sind.
---------------------------------------------------------------------- > class (Eq a, Text a) => Num a where > (+), (-), (*) :: a -> a -> a > negate :: a -> a > abs, signum :: a -> a > fromInteger :: Integer -> a ----------------------------------------------------------------------
Beachte: `-x*y' ist äquivalent zu `negate (x*y)'.
Für die Definition der übrigen Klassen sei auf den Haskell Report verwiesen (@S 6.8).
Der Typ der rationalen Zahlen ist abstrakt (später mehr zu abstrakten Typen).
---------------------------------------------------------------------- > data Integral a => Ratio a > type Rational = Ratio Integer ----------------------------------------------------------------------
Rationale Zahlen werden mit `%' konstruiert. Zähler und Nenner einer rationalen Zahl erhält man mit `numerator' und `denominator'.
---------------------------------------------------------------------- > (%) :: Integral a => a -> a -> Ratio a > numerator :: Integral a => Ratio a -> a > denominator :: Integral a => Ratio a -> a ----------------------------------------------------------------------
Beachte: rationale Zahlen werden automatisch gekürzt. Aus diesem Grund ist `numerator (x%y)' im allgemeinen nicht gleich `x'.
Wie notiere ich Elemente der numerischen Typen? Anders gefragt: Welchen Typ haben die Literale `27' oder `3.1415'?
Lösung: das Literal `27' ist eine Abkürzung für `fromInteger (27::Integer)' und das Literal `3.1415' für `fromRational (3.1415::Rational)'.
---------------------------------------------------------------------- > fromInteger :: (Num a) => Integer -> a > fromRational :: (Fractional a) => Rational -> a ----------------------------------------------------------------------
Das heißt, die numerischen Literale sind implizit überladen. Vorteil: Sie können für alle numerischen Typen verwendet werden.
Aufgabe 5. Warum wird `3.1415' als rationale Zahl interpretiert und nicht als Fließkommazahl?
Komplexe Zahlen sind wie folgt definiert.
---------------------------------------------------------------------- > data RealFloat a => Complex a = a :+ a ----------------------------------------------------------------------
Die komplexe Zahl `a+bi' wird als `a:+b' notiert. Der Konstruktor `:+' kann wie üblich als Muster verwendet werden.
---------------------------------------------------------------------- > conjugate :: RealFloat a => Complex a -> Complex a > conjugate (x :+ y) = x :+ (-y) ----------------------------------------------------------------------
Überladene Funktionen lassen sich nicht immer eindeutig auflösen.
---------------------------------------------------------------------- > pyth :: Floating a => a -> a -> a > pyth x y = sqrt (x^2 + y^2) ----------------------------------------------------------------------
Die Funktion `(^)' hat den Typ `(Num a, Integral b) => a -> b -> a', `2' hat den Typ `Num a => a'; somit erhält `x^2' den Typ `(Num a, Integral b) => a'.
Problem: Welcher Typ soll für `b' gewählt werden? `Int' oder `Integer'?
Lösung: für numerische Typen kann das mit Hilfe einer `default' Deklaration festgelegt werden.
---------------------------------------------------------------------- > default (Int, Double) ----------------------------------------------------------------------
Der erste Typ, der `paßt', wird genommen.
Das Problem tritt nicht nur bei numerischen Funktionen auf.
---------------------------------------------------------------------- > whoops :: String -> String > whoops x = show (read x) ----------------------------------------------------------------------
Die Funktion `read' hat den Typ `Text a => String -> a', die Funktion `show' hat den Typ `Text a => a -> String'; somit erhält `show (read x)' den Typ `Text a => String -> String'.
Problem: Welcher Typ soll für `a' gewählt werden? Alle Instanzen von `Text' sind möglich!
Lösung: In diesen Fällen muß der Typ explizit angegeben werden.
---------------------------------------------------------------------- > whoops :: String -> String > whoops x = show (read x::[Int]) ----------------------------------------------------------------------
Go to the first, previous, next, last section, table of contents.