Die Wahrheitswerte sind vordefiniert.
---------------------------------------------------------------------- > data Bool = False | True ----------------------------------------------------------------------
Fallunterscheidungen können vielfältig programmiert werden: mit
----------------------------------------------------------------------
if <expr> then <expr> else <expr>
----------------------------------------------------------------------
mit Wächtern ... (später mehr dazu).
Aufgabe 1. Definiere die logische Konjunktion `&&' und die Disjunktion `||'! Ist der Ausdruck `n /= 0 && 1 / n > eps' sinnvoll?
Aufgabe 2. Definiere die Funktion `elem :: (Eq a) => a -> [a] -> Bool'? Der Aufruf `elem a x' ergibt `True', falls das Element `a' in der Liste `x' enthalten ist. Sonst `False'.
Der Typ `Char' umfaßt die ASCII-Zeichen. Zeichen werden `wie gewohnt' notiert: `'a'', `'\n'', `'\BEL'' etc. (siehe @S 2.5).
Zeichenketten sind Listen von Zeichen.
---------------------------------------------------------------------- > type String = [Char] ----------------------------------------------------------------------
Für Zeichenketten gibt es die `übliche' abkürzende Notation: `"ha"' statt `'h':'a':[]'.
Haskell verfügt über eine große Zahl numerischer Typen:
Die arithmetischen (`+', `-', `*' etc.) und zahlentheoretischen Funktionen (`log', `exp' etc.) sind überladen (später mehr zu diesem Thema).
---------------------------------------------------------------------- > fac :: (Integral a) => a -> a > fac n | n <= 0 = 1 > | otherwise = n * fac (n - 1) ----------------------------------------------------------------------
Tupel beliebiger Stelligkeit sind vordefiniert.
---------------------------------------------------------------------- > data () = () -- das leere Tupel > data (a, b) = (a, b) -- Paare > data (a, b, c) = (a, b, c) -- Tripel > ... ----------------------------------------------------------------------
Beachte: für Tupel (z.B. `(1, 'a', True)') und Tupeltypen (z.B. `(Int, Char, Bool)') wird die gleiche Syntax verwendet.
Tupel werden benutzt, um eine feste Zahl von Werten unterschiedlichen Typs zusammenzufassen.
Listen stellen -- wie gesagt -- die wichtigste Datenstruktur in Haskell dar.
---------------------------------------------------------------------- > data [a] = [] | a : [a] ----------------------------------------------------------------------
Listen werden benutzt, um eine beliebige Zahl von Werten gleichen Typs zusammenzufassen.
Es gibt -- wie gesagt -- Myriaden vordefinierter Funktionen (siehe `PreludeList'). Eine Auswahl:
---------------------------------------------------------------------- > head :: [a] -> a > tail :: [a] -> [a] > (++) :: [a] -> [a] -> [a] > (\\) :: (Eq a) => [a] -> [a] -> [a] > length :: [a] -> Int > (!!) :: (Integral a) => [b] -> a -> b > take, drop :: (Integral a) => a -> [b] -> [a] > lines, words :: String -> [String] > unlines, unwords :: [String] -> String > and, or :: [Bool] -> Bool > sum, product :: (Num a) => [a] -> a > elem, notElem :: (Eq a) => a -> [a] -> Bool > concat :: [[a]] -> [a] ----------------------------------------------------------------------
Um Listen zu konstruieren, gibt es vielfältige Möglichkeiten. Arithmetische Folgen können z.B. wie folgt notiert werden.
Um Funktionen auf Listen zu definieren, haben wir bisher rekursive Gleichungen verwendet. Einfacher und lesbarer sind in vielen Fällen Listenbeschreibungen.
---------------------------------------------------------------------- > elem a x = or [ a==b | b<-x ] > concat xs = [ a | x<-xs, a<-x ] ----------------------------------------------------------------------
Naive Definition von Quicksort.
---------------------------------------------------------------------- > qsort [] = [] > qsort (a:x) = qsort [ b | b <- x, b <= a ] > ++ [a] > ++ qsort [ b | b <- x, b > a ] ----------------------------------------------------------------------
Mathematiker. Die Syntax von Listenbeschreibungen ist eng an die Notation von Mengen (z.B. ` { n | n<-N, n>=7 }') angelehnt. Im Unterschied zu Mengen spielt die Reihenfolge eine Rolle und es können Duplikate auftreten.
Beispiel: `perms x' berechnet die Liste aller Permutationen von `x'.
---------------------------------------------------------------------- > perms :: [a] -> [[a]] > perms [] = [[]] > perms x = [ a:y' | (a, y)<-remove x, y'<-perms y ] > > remove :: [a] -> [(a,[a])] > remove [] = [] > remove (a:x) = (a, x) : [ (b, a:y) | (b, y)<-remove x ] ----------------------------------------------------------------------
Aufgabe 3. Zur Abschreckung: Formuliere `perms' und `remove' ohne Listenbeschreibungen zu verwenden.
Das bekannte n-Damen-Problem läßt sich wie folgt lösen: `queens n' berechnet die Liste aller Lösungen.
---------------------------------------------------------------------- > queens n = place n [] [] [1 .. n] > > place c d1 d2 rs > | c == 0 = [[]] > | otherwise = [ q:qs > | (q, rs')<-remove rs, > (q-c) `notElem` d1, > (q+c) `notElem` d2, > qs<-place (c-1) ((q-c):d1) ((q+c):d2) rs'] ----------------------------------------------------------------------
Beachte: wird mit `queens 8!!0' nur auf die erste Lösung zugegriffen, werden die übrigen nicht generiert (lazy evaluation).
Listenbeschreibungen haben die Form
----------------------------------------------------------------------
[ <exp> | <qual1>, ... , <qualn> ]
----------------------------------------------------------------------
----------------------------------------------------------------------
<qual> --> <pat> <- <exp> Generator
| <exp> Wächter
----------------------------------------------------------------------
Für den Generator `p <- e' muß gelten: Wenn `p' vom Typ `t' ist, muß `e' vom Typ `[t]' sein. Generatoren führen Variablen ein, die `weiter rechts' oder im Kopf verwendet werden können. Wächter, das sind Boolesche Ausdrücke, schränken die Belegungen von Variablen ein.
C-Programmierer. Der Ausdruck `[ i*j | i<-[0..9], j<-[i..9] ]' entspricht zwei ineinander geschachtelten Schleifen.
for (int i=0; i<=9; i++)
for (int j=i; j<=9; j++)
printf("%d\n", i*j);
Als funktionale Sprache bietet Haskell die Möglichkeit, Funktionen durch Ausdrücke zu bezeichnen (d.h. ohne eine Definition vorzunehmen).
----------------------------------------------------------------------
\ <pat1> ... <patn> -> <exp>
----------------------------------------------------------------------
Ist `pi' vom Typ `ti' und `e' vom Typ `t', so besitzt der Ausdruck `\ p1 ... pn -> e' den Typ `t1 -> t2 -> ... -> tn -> t'.
Die Anwendung einer Funktion auf Argumente wird ohne Syntax notiert.
----------------------------------------------------------------------
<exp> <exp1> ... <expn>
----------------------------------------------------------------------
Hat `e' den Typ `t1 -> t2 -> ... -> tn -> t' und `ei' den Typ `ti', so besitzt `e e1 ... en' den Typ `t'.
Haskell kennt nur einstellige Funktionen.
---------------------------------------------------------------------- > addInt :: Int -> Int -> Int > addInt a b = a + b ----------------------------------------------------------------------
Der Typausdruck `Int -> Int -> Int' kürzt `Int -> (Int -> Int)', d.h., `->' assoziert von rechts. `addInt' erwartet demnach als Argument eine ganze Zahl und gibt eine Funktion zurück!
---------------------------------------------------------------------- > addInt' :: (Int, Int) -> Int > addInt' (a, b) = a + b ----------------------------------------------------------------------
`addInt'' erwartet als Argument ein Paar. Sei `dup a = (a,a)' gegeben, dann ist `addInt' (dup 5)' ein gültiger Ausdruck.
Funktionen des Typs `t1 -> t2 -> ... -> tn -> t' heißen gestaffelt (oder curryfiziert: aha, daher der Namen Haskell). Gestaffelte Funktionen sind im allgemeinen flexibler (und effizienter!) als Funktionen, die auf Tupeln arbeiten. Betrachten wir
---------------------------------------------------------------------- > lookupWithDefault :: Ord a => Dict a b -> b -> a -> b ----------------------------------------------------------------------
aus Aufgabe 6. Versorgt man diese Funktion `peu a peu' mit Argumenten, so erhält man folgende Ableger:
Elemente eines Datentyps können mit Hilfe von `case' analysiert werden. Statt
---------------------------------------------------------------------- > elem a [] = False > elem a (b:x) = a==b || elem a x ----------------------------------------------------------------------
kann `elem' auch (weniger elegant) mit Hilfe von `case' definiert werden.
---------------------------------------------------------------------- > elem = \a y -> case y of > [] -> False > b:x -> a==b || elem a x ----------------------------------------------------------------------
Ein `case'-Ausdruck bietet sich an, wenn das Ergebnis eines Funktionsaufrufs weiterverarbeitet werden soll.
Funktionen können mit Hilfe mehrerer Gleichungen definiert werden. Eine Funktionsdefinition hat die folgende syntaktische Form.
----------------------------------------------------------------------
f <pat11> ... <pat1k> <match1>
...
f <patn1> ... <patnk> <matchn>
----------------------------------------------------------------------
wobei `<match>' eine der beiden folgenden Formen hat.
----------------------------------------------------------------------
= <exp> where { <decl1>; ... ; <decln> }
----------------------------------------------------------------------
----------------------------------------------------------------------
| <guard1> = <exp1>
...
| <guardm> = <expm>
where { <decl1>; ... ; <decln> }
----------------------------------------------------------------------
Mit `where' werden lokale Definitionen eingeführt (später mehr dazu). Die Wächter sind Boolesche Ausdrücke, die über die Anwendung einer Gleichung wachen.
Beispiel: eine endrekursive Variante von Quicksort.
---------------------------------------------------------------------- > qsort :: Ord a => [a] -> [a] > qsort [] = [] > qsort [a] = [a] > qsort (a:x) = partition [] [] x > where > partition l r [] = qsort l ++ a : qsort r > partition l r (b:y) > | b <= a = partition (b:l) r y > | otherwise = partition l (b:r) y ----------------------------------------------------------------------
Laut Syntax werden einzelne Definitionen durch ``;'' getrennt.
----------------------------------------------------------------------
... where { <decl1>; ... ; <decln> }
----------------------------------------------------------------------
Wir haben bisher weder geschweifte Klammern noch ein Semikolon verwendet. Die sogenannte Abseitsregel erlaubt es, Definitionen `ohne syntaktischen' Ballast zu notieren.
Folgt dem `where' (bzw. `let' oder `of') keine offene Klammer `}', so tritt die Abseitsregel in Kraft: Die Einrückung der nächsten lexikalischen Einheit wird vermerkt. Mit den folgenden Zeilen wird wie folgt verfahren:
Muster dienen sowohl zur Unterscheidung verschiedener Fälle als auch zur Benennung von Komponenten eines Wertes.
---------------------------------------------------------------------- > head (a:x) = a ----------------------------------------------------------------------
Die Gleichung ist nur anwendbar, wenn der aktuelle Parameter die Form `e1:e2' hat (ggf. muß der Parameter reduziert werden). In diesem Fall wird `a' an den Listenkopf `e1' und `x' an den Listenrest `e2' gebunden.
Muster werden von links nach rechts und Gleichungen von oben nach unten abgearbeitet. Somit spielt unter Umständen die Reihenfole von Gleichungen eine Rolle.
---------------------------------------------------------------------- > take (n+1) (a:x) = a : take n x > take _ _ = [] ----------------------------------------------------------------------
Ein guter Programmierer `;-)' versucht, dies so weit wie möglich zu vermeiden.
Muster haben die folgende Form (leicht vereinfacht).
----------------------------------------------------------------------
<pat> --> <var> [ @ <pat> ] geschachteltes Muster
| <con> <pat1> ... <patn> Konstruktoranwendung
| [ - ] <integer> Konstante
| <var> + <integer> Nachfolgermuster
| _ anonyme Variable
| ( <pat1>, ..., <patn> ) Tupelmuster
| [ <pat1>, ..., <patn> ] Listenmuster
----------------------------------------------------------------------
Ein Muster der Form `x + k' paßt auf den Wert `n', falls `n >= k' und bindet `x' an `n-k'.
Wertedefinitionen haben die folgende Form.
----------------------------------------------------------------------
<pat> | <guard1> = <exp1>
...
| <guardm> = <expm>
where { <decl1>; ... ; <decln> }
----------------------------------------------------------------------
Im Gegensatz zu Funktionsdefinitionen bindet eine Wertedefinition unter Umständen mehrere Bezeichner.
---------------------------------------------------------------------- > qsort :: Ord a => [a] -> [a] > qsort [] = [] > qsort (a:x) = qsort l ++ a : qsort r > where (l, r) = partition (>= a) x ----------------------------------------------------------------------
Wertedefinitionen werden häufig verwendet, um strukturierte Rückgabewerte zu verarbeiten.
Beispiel: Die Funktion `build' überführt eine Liste in einen vollständigen balancierten Binärbaum.
---------------------------------------------------------------------- > build :: [a] -> BinTree a > build x = fst (buildn (length x) x) > > buildn :: Int -> [a] -> (BinTree a, [a]) > buildn 0 x = (Empty, x) > buildn (n+1) x = (Node l a r, z) > where m = n `div` 2 > (l, a:y) = buildn m x > (r, z) = buildn (n - m) y ----------------------------------------------------------------------
Beachte: die Reihenfolge der lokalen Bindungen spielt keine Rolle. Die Auswertungsreihenfolge wird allein durch die Datenabhängigkeiten bestimmt.
----------------------------------------------------------------------
...
where m = n `div` 2
(l, a:y) = buildn m x
(r, z) = buildn (n - m) y
----------------------------------------------------------------------
Beachte: Wertebindungen können auch fehlschlagen: Bei der Auswertung von
----------------------------------------------------------------------
buildn 4 [1]
----------------------------------------------------------------------
tritt ein Fehlschlag auf: `(l, a:y)' paßt nicht auf `(Node Empty 1 Empty, [])'. Der Zugriff auf eine der Variablen `l', `a' oder `y' führt zum Programmabbruch.
Mit `let' und `where' werden lokale Definitionen eingheführt. Nur Typdeklarationen (`f :: t'), Funktions- und Wertedefinitionen dürfen lokal verwendet werden, keine Typdefinitionen (`data', `type').
Unterschiede zwischen `let' und `where':
----------------------------------------------------------------------
| g1 = e1
...
| gm = gi
where { <decls> }
----------------------------------------------------------------------
erstreckt sich auf die `ei' und die `gi'.
C-Programmierer. Die Sichtbarkeitsregeln entsprechen denen in blockstrukturierten Sprachen.
Go to the first, previous, next, last section, table of contents.